IC Colloquium: Between Worst-Case and Average-Case Analysis: Algorithms and Applications
Par : Peter Manohar - Institute for Advanced Study
IC Faculty candidate
Abstract
The classic study of algorithms focuses on understanding the behavior of algorithms on either worst-case or average-case inputs. Both of these models have well-established drawbacks: the worst-case model is overly pessimistic in assuming that the input is adversarially chosen, while the average-case model is overly optimistic in assuming that the input is drawn from an idealized distribution.
A natural method to overcome both these issues is to study algorithms for "semirandom" inputs --- inputs drawn from distributions with a hybrid of worst-case and average-case structure. In this talk, I will discuss my work on designing algorithms for semirandom constraint satisfaction problems (such as 3-SAT), and explain how my algorithmic tools have led to surprising progress on decades-old problems in coding theory, extremal combinatorics, and more.
Bio
Peter Manohar is a postdoctoral researcher at the Institute for Advanced Study. He received his PhD in Computer Science from Carnegie Mellon University in 2024, advised by Venkatesan Guruswami and Pravesh K. Kothari, and his B.S. in EECS from UC Berkeley in 2019.
His research interests span several areas of theoretical computer science, including beyond worst-case analysis of algorithms, spectral algorithms, coding theory, and extremal combinatorics, and his work has been featured in the Communications of the ACM Research Highlights and Quanta Magazine.
More information
IC Faculty candidate
Abstract
The classic study of algorithms focuses on understanding the behavior of algorithms on either worst-case or average-case inputs. Both of these models have well-established drawbacks: the worst-case model is overly pessimistic in assuming that the input is adversarially chosen, while the average-case model is overly optimistic in assuming that the input is drawn from an idealized distribution.
A natural method to overcome both these issues is to study algorithms for "semirandom" inputs --- inputs drawn from distributions with a hybrid of worst-case and average-case structure. In this talk, I will discuss my work on designing algorithms for semirandom constraint satisfaction problems (such as 3-SAT), and explain how my algorithmic tools have led to surprising progress on decades-old problems in coding theory, extremal combinatorics, and more.
Bio
Peter Manohar is a postdoctoral researcher at the Institute for Advanced Study. He received his PhD in Computer Science from Carnegie Mellon University in 2024, advised by Venkatesan Guruswami and Pravesh K. Kothari, and his B.S. in EECS from UC Berkeley in 2019.
His research interests span several areas of theoretical computer science, including beyond worst-case analysis of algorithms, spectral algorithms, coding theory, and extremal combinatorics, and his work has been featured in the Communications of the ACM Research Highlights and Quanta Magazine.
More information
Practical information
- General public
- Free
Contact
- Host: Michael Kapralov