Symmetry in Efficient Computation with Local Constraints

Symmetry leads to efficient computation. This phenomenon has manifested itself in several research areas that have one aspect in common — namely, a model of computation with local constraints that restrict the solution space of the problem of interest. An elegant way to describe such problems is in the framework of constraint satisfaction problems (CSPs). CSPs have driven some of the most influential developments in theoretical computer science, from NP-completeness to the PCP theorem to semidefinite programming algorithms to the Unique Games Conjecture.

The mathematical structure of tractable decision CSPs, infinite-domain CSPs, optimization CSPs, and approximable CSPs is now known to be linked to certain forms of higher-order symmetries of solution spaces that are called polymorphisms and form an algebraic structure known as a (functional) clone. The Unique Games Conjecture and its connection to semidefinite programming have been extremely influential in sharpening our understanding of the approximability of CSPs, leading to a complete characterization in many cases. However, much less is known about approximability of problems that are satisfiable, even under very strong conjectural hardness assumptions. The study of random CSPs and semirandom generalizations has been a central topic of study in algorithm design, statistical physics, and proof complexity over the past three decades, and different notions of symmetry are naturally involved. Over the past two decades, many connections have been made between the complexity of CSPs and quantum information. Two central questions are the quantum PCP conjecture (about local Hamiltonians) and the quantum games PCP conjecture (about nonlocal games).

A major goal of the program is to coordinate activities among researchers from different fields and create synergy among the different areas.

Long-Term Participants (tentative): Dorit Aharonov (Hebrew University), Mitali Bafna (University of Washington), Libor Barto (Charles University), Andrei Bulatov (Simon Fraser University), Silvia Butti (King’s College London), Uriel Feige (Weizmann Institute), Martin Grohe (RWTH Aachen University), Venkatesan Guruswami (UC Berkeley), Johan Hastad (KTH), Pravesh Kothari (Princeton), Marcin Kozik (Jagiellonian University), Andrei Krokhin (Durham University), Pasin Manurangsi (Google), Dor Minzer (MIT), Cristopher Moore (Santa Fe Institute), Anand Natarajan (MIT), Jakub Oprsal (University of Birmingham), Toniann Pitassi (Columbia University), Aaron Potechin (University of Chicago), Prasad Raghavendra (UC Berkeley), William Slofstra (University of Waterloo), John Wright (UC Berkeley), Dmitriy Zhuk (Charles University), Stanislav Zivny (Oxford)