When and Why Do Efficient Algorithms Exist (for Constraint Satisfaction and Beyond)?
- Prelegent(ci)
- Venkatesan Guruswami
- Afiliacja
- UC Berkeley
- Język referatu
- angielski
- Termin
- 30 czerwca 2025 11:00
- Pokój
- p. 2180 (sala RW)
- Seminarium
- Kolokwium Wydziału MIM UW
Some computational problems can be solved efficiently; others seem hopelessly intractable. What accounts for this striking difference? What kind of mathematical structure—or lack thereof—permits efficient algorithms, or conversely dictates computational hardness?
Given the vast landscape of problems and algorithmic approaches, it would be simplistic to hope for a universal theory explaining the boundary between tractability and intractability. Yet, in the realm of constraint satisfaction problems (CSPs), there's a surprisingly clean and deep answer: a CSP can be solved in polynomial time if its solution space is closed under certain local operations known as polymorphisms; otherwise, it is NP-complete.
We will discuss the background on CSPs and the polymorphic approach to understanding this dichotomy. We'll illustrate the connection between polymorphisms and efficient algorithms via the simple example of graph 2-coloring, and outline a general algorithm based on symmetric polymorphisms. We will then venture into extensions of classical CSPs where the polymorphic principle appears promising—though still far from fully understood. In particular, we'll discuss promise CSPs, where one aims to satisfy a relaxed version of the constraints—a framework that encompasses problems such as approximate graph coloring.
No background beyond basic mathematical and algorithmic maturity will be assumed.
No background beyond basic mathematical and algorithmic maturity will be assumed.