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.
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.
Assignments:
Related material:
Basic Background:
Relevant textbooks: