Opening Hardness of Random 3XOR and 3Sat
Hardness of Random 3XOR and 3Sat
- Length
- 23 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Sparse LPN problem and random 3XOR
Random 3XOR and random 3-Sat are the average-case counterparts of worst-case hardness results for constraint satisfaction problems. O'Donnell starts from sparse learning parity with noise, where noisy parity equations on random triples of variables form puzzles that appear hard on average. Håstad's 1999 theorem follows: distinguishing nearly satisfiable Max-3XOR systems from those barely better than random is NP-hard. Random 3-Sat comes next, with its sharp transition from satisfiable to unsatisfiable at clause density . Feige's Hypothesis, that no polynomial-time algorithm refutes random 3-Sat at constant density, closes the session and yields hardness of learning DNF formulas and noisy halfspaces. The material assumes NP-completeness, reductions, CSPs and some exposure to semidefinite programming.

Your comment is kept while you sign up.Sign in
O'Donnell sets Håstad's 1999 3XOR hardness theorem beside sparse LPN and Feige's random 3-Sat hypothesis.
Random 3XOR and random 3-Sat are the average-case counterparts of worst-case hardness results for constraint satisfaction problems. O'Donnell starts from sparse learning parity with noise, where noisy parity equations on random triples of variables form puzzles that appear hard on average. Håstad's 1999 theorem follows: distinguishing nearly satisfiable Max-3XOR systems from those barely better than random is NP-hard. Random 3-Sat comes next, with its sharp transition from satisfiable to unsatisfiable at clause density . Feige's Hypothesis, that no polynomial-time algorithm refutes random 3-Sat at constant density, closes the session and yields hardness of learning DNF formulas and noisy halfspaces. The material assumes NP-completeness, reductions, CSPs and some exposure to semidefinite programming.
Applebaum
Hastad, TSSV
Karpinski - Lampis - Schüid 2013
Ding, Sly, Sun 2014
Barak et al. 03
Daniely and Shalev-Shwartz 16
This lecture
Lecture 83 of 89 of A Theorist's Toolkit.
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.