Topics in Algorithms - Random Satisfiability (semester 2011B)

Tel Aviv University

Course description:

 

Instructor: Benny Applebaum

When and where: Sunday 3-5pm, Engineering Studies - Classrooms Lecture Room 3

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, Presentations]

 

Course Plan:

Below is a very tentative course plan. There are likely to be significant changes to this plan as the semester goes on.

  1. Overview: Constraint satisfaction problems, SAT and the P vs. NP problem, Random SAT, (slides).
  2. The simple story of 2SAT - efficient algorithms, and threshold phenomena. 
  3. The Unit Clause heuristic, analysis via differential equations. Basic notation and probability.  
  4. The Pure Literal heuristic viewed as a (trivial) Message Passing Algorithm. 
  5. Random Walk over 2-SAT and 3-SAT 
  6. When and why heuristics fail? 
    • Lower bounds on DPLLs via Resolution
    • The geometry of solutions
  7. Algorithms for Planted 3-SAT
  8. Fast Cryptography 
    • Goldreich's function, The MST/ABW generators, Hardness for DPLLs, Amplification theorems, One-wayness implies pseudorandomness 
  9. Fast error correcting codes
    • LDPCs, iterative decoding, Spielman's linear-time encodable and decodable codes 
  10. Refuting 3SAT: Feige's assumption and its applications

 

Assignments:


 

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)
  2. Asymptotic Analysis of algorithms can be found in any standard textbook (E.g., Introduction to Algorithms, Cormen-Leiserson-Rivest -Stein - also in hebrew) 
  3. 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
 


Presentations:


Each pair of students should give a 30 minute presentation of a paper related to the course subject. In addition, you should hand out a short (2-3) pages summary of the presentation.
The subject of presentation should be coordinated with me, and you are strongly advised to meet me before the actual presentation to make sure that you are in the right direction.
Here is a list of papers from which you can choose. Starred (*) papers are more challneging.