Opening Beyond Worst-Case Analysis
Beyond Worst-Case Analysis
- Length
- 1 h 21 min
- Level
- Undergraduate
- Recorded
- Carnegie Mellon University2017
Chapter 1 of 9: Overview of worst-case analysis
Sets Håstad's 7/8 hardness for E3-SAT beside random assignments, then states Feige's Hypothesis on 3-SAT refuters.
Computational complexity theory addresses the limitations of worst-case analysis by exploring randomized models, approximation algorithms, and average-case hardness assumptions. Assuming P does not equal NP restricts the existence of universal polynomial-time algorithms, prompting weaker algorithmic goals or stronger hypotheses such as the Exponential Time Hypothesis. The lecture examines Håstad's optimal hardness result for E3-SAT using indicator random variables and linearity of expectation to analyze random assignments. It then evaluates Min-Bisection and the limitations of standard reductions in preserving approximation ratios. Finally, it explores random 3-SAT clause densities and Feige's Hypothesis regarding delta 3-SAT refuters.
Computational complexity theory addresses the limitations of worst-case analysis by exploring randomized models, approximation algorithms, and average-case hardness assumptions. Assuming P does not equal NP restricts the existence of universal polynomial-time algorithms, prompting weaker algorithmic goals or stronger hypotheses such as the Exponential Time Hypothesis. The lecture examines Håstad's optimal hardness result for E3-SAT using indicator random variables and linearity of expectation to analyze random assignments. It then evaluates Min-Bisection and the limitations of standard reductions in preserving approximation ratios. Finally, it explores random 3-SAT clause densities and Feige's Hypothesis regarding delta 3-SAT refuters.
Håstad '99
Hastad 99
Feige's Hypothesis
This lecture
Lecture 26 of 28 of Undergraduate Complexity Theory.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in