Random Satisfiability.
Constraint satisfaction problems (CSP) play an important role in various fields including computer science, electrical engineering, math, and statistical physics. The course will be devoted to the study of randomly generated CSP instances and the performance of different algorithms on them. In particular, we will analyze heuristics such as DPLLs, local search, message-passing algorithms, and possibly others. We will also relate these results to questions in cryptography, combinatorial optimization, and error-correcting codes. Most of the material will be based on articles that will be distributed to the students.
General Information:
Constraint satisfaction problems (CSP) play an important role in various fields including computer science, electrical engineering, math, and
statistical physics. The course will be devoted to the study of randomly generated CSP instances and the performance of different algorithms on them.
In particular, we will analyze heuristics such as DPLLs, local search, message-passing algorithms, and possibly others. We will also relate these
results to questions in cryptography, combinatorial optimization, and error-correcting codes. Most of the material will be based on articles that will
be distributed to the students. During the course, we will present research questions suitable for projects or MSc and PhD theses.
Prerequisites: Students are expected to be familiar with algorithms, and to have basic background in probability theory and combinatorics.
Detailed Syllabus:
- Overview: Constraint satisfaction problems, SAT and the P vs. NP problem, Random SAT, (slides).
- The simple story of 2SAT - efficient algorithms, and threshold phenomena.
- The Unit Clause heuristic, analysis via differential equations. Basic notation and probability.
- The Pure Literal heuristic viewed as a (trivial) Message Passing Algorithm.
- Random Walk over 2-SAT and 3-SAT
- When and why heuristics fail? Lower bounds on DPLLs via Resolution, The geometry of solutions
- Algorithms for Planted 3-SAT: Flaxman's algorithm, Random Walk (Vilenchik-Feige), Warning Propagation (Vilenchik-Feige-Mossel)
- Fast Cryptography: Goldreich's function, The MST/ABW generators, Hardness for DPLLs, Amplification theorems, One-wayness implies pseudorandomness
- Fast error correcting codes: LDPCs, iterative decoding, Spielman's linear-time encodable and decodable codes
- Refuting 3SAT: Feige's assumption and its applications
