This Course Will Cover The Complexity of Satisfaction Constraints Problems From Several Perspectives# Schaefer S Theorem, Which Classifies Constraint Satisfaction Problems Over Binary Variables Into Two Types# Solvable in Polynomial Time, And Np-hard. Tight Hardness of Approximation Results For Several Problems# Max-3lin, Max-3sat, Max-cut , Introduction to Proof Complexity, And Lower Bounds On Refuting Random Instances of Sat. Learning Outcomes# at The End of The Course The Students Will Be Able To# 1. Define The Central Concept Constraint Satisfaction Problem . 2. Distinguish Between Csps Which Are Solvable Efficiently and Those Which Are Hard. 3. Know Basic Techniques in Approximation Algorithms, and Be Able To Apply Them to New Problems. 4. Know Basic Techniques in Hardness of Approximation, and Be Able To Apply Them to New Problems. 5. Know Basic Concepts in Proof Complexity, and The Connection to Sat Solving. 6. Know Basic Techniques in Resolution Lower Bounds, and Be Able To Apply Them to New Problems.

Faculty: Computer Science
|Undergraduate Studies |Graduate Studies
Pre-required courses

(94412 - Probability (advanced) and 234247 - Algorithms 1 and 236343 - Theory of Computation)