Satisfiability Theory

Algorithms and Applications (Seminar)

In Brief: Whether a particular circuit is capable of outputting "1" is the "most basic" NP-Complete problem, called circuit-satisfiability. All other NP-Complete problems are usually reductions "from" this problem. In this seminar, we will see algorithms for and applications of the "satisfiability" problems.

• People interesting in theory of CS
• People who took DAA or complexity classes and have the heart for more theoretical work
• People interested in applications of satisfiability problems, especially to AI or formal verification / automatic proof techniques
• People wishing to continue into Abhishek's third lecture series on really advanced topics in computability and complexity.
• Anybody else who is interested

Teacher's Introduction: Abhishek Rathod did his B.E. in CS from VIT. He was a research trainee at the Computational Mathematics Laboratory (CML) at TIFR from July 2003 to June 2004. He unofficially continues to work at the same place, but is currently also pursuing his own theoreitcal interests. His research interests are complexity theory, optimization theory and combinatorics.

Course Topics: Satisfiability problems, standard algorithms, applications to AI and formal verification, propositional proof complexity, the threshold phenomenon.

Prerequisites: Introduction to Complexity Classes

Advanced Courses: Abhishek is hoping to take a third lecture series on really advanced stuff.