Topics in Algorithms - Random Satisfiability (semester 2014B)

Tel Aviv University

Course description:

 

Instructor: Benny Applebaum

When and where: Tuesday 3-5pm, Engineering Studies - Wolfson Lecture Room 118

TAU code: 0510-7410

Office Hours: can be coordinated by email .

Mailing List:  http://listserv.tau.ac.il/archives/0510-7410-01.html

Brief description: 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.

 

Evaluation (grade): Homework (20%) and a final exam (80%). There may be an option to skip the exam and prepare a project instead.

[Plan, Assignemnts, Related Material]

---

 

Course Plan:

Below is a very tentative course plan. There are likely to be significant changes to this plan as the semester goes on.
WARNING: THE FOLLOWING SCRIBE NOTES HAVE ONLY BEEN LIGHTLY EDITED AND MAY CONTAIN ERRORS. 

1. Overview: Constraint satisfaction problems, SAT and the P vs. NP problem, Random SAT, Approximation via Conditional Expectation (slides).
• See also: Two surveys by Flaxman and by Achlioptas.
  
2. The simple story of 2SAT - efficient algorithms, and threshold phenomena. Class notes (pdf, tex)
   
• See also: Chapter 10 of [MM].
3. The Unit Clause heuristic, analysis via differential equations. Basic notation and probability.
   
• Summary Class notes (pdf)
• See also: Lower bounds for random 3-SAT via differential equations by Achlioptas.
4. The Pure Literal heuristic viewed as a (trivial) Message Passing Algorithm. Class notes (pdf)
• See also: Luby, Mitzenmacher and Shokrollahi and the original analysis (based on differential equations) by Broder, Frieze and Upfal.  
5. Random Walk over 2-SAT and 3-SAT 
• See also: Constructive proof of the local lemma (slides)
  
• See also: Ben-Sasson and Alekhnovich
6. Fast error correcting codes
   
   • LDPCs, iterative decoding, Spielman's linear-time encodable/decodable codes, funtain codes
     
   • See Madhu Sudan's notes (here and here)
     
7. Local Cryptography
   
• Goldreich's function, Dichotomy for eps-biased generators
  
•  Hardness for DPLLs, Amplification theorems, One-wayness implies pseudorandomness
8. When and why heuristics fail? 
• Lower bounds on DPLLs via Resolution
• The geometry of solution
9. Algorithms for Planted 3-SAT
• Flaxman's algorithm, Random Walk (Vilenchik-Feige), Warning Propagation  (Vilenchik-Feige-Mossel)
10. Refuting 3SAT: Feige's assumption and its applications

---

 

Assignments:

• Ex1 Due April 1st. 
• Ex2 Due May 13th.

---

 

Related material:

 

Basic Background:

1. Basic probability (Dana Ron's summary, Bshouty's summary,  for more comprehensive background see Sections A.2 of Arora-Barak book)
1. Asymptotic Analysis of algorithms can be found in any standard textbook (E.g., Introduction to Algorithms, Cormen-Leiserson-Rivest -Stein - also in hebrew) 
1. Basic background on combinatorics can be found in the appendix of Introduction to Algorithms

Relevant textbooks:

1. [MM] Information, Physics, and Computation by Marc Mézard and Andrea Montanari
   

 

---