Algorithms - Random Satisfiability
When and where: Tuesday 3-5pm, Engineering
Studies - Wolfson Lecture
TAU code: 0510-7410
can be coordinated by email .
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.
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
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.
The simple story of 2SAT - efficient
algorithms, and threshold phenomena. Class notes (pdf, tex)
- Overview: Constraint satisfaction
problems, SAT and the P vs. NP problem, Random SAT,
Approximation via Conditional Expectation (slides).
The Unit Clause heuristic,
analysis via differential equations. Basic notation
The Pure Literal
heuristic viewed as a (trivial) Message Passing Algorithm. Class
Random Walk over
2-SAT and 3-SAT
- LDPCs, iterative decoding, Spielman's linear-time
encodable/decodable codes, funtain codes
- See Madhu Sudan's notes (here
for eps-biased generators
When and why
bounds on DPLLs via Resolution
for Planted 3-SAT
Feige's assumption and
Due April 1st.
Due May 13th.
Ron's summary, Bshouty's
summary, for more comprehensive
background see Sections
A.2 of Arora-Barak
to Algorithms, Cormen-Leiserson-Rivest -Stein -
also in hebrew)
background on combinatorics can be found in the
appendix of Introduction
- [MM] Information,
Physics, and Computation by Marc Mézard and Andrea