Title: A new line of attack on the dichotomy conjecture 

Speaker: Mario Szegedy, Rutgers 


Abstract: 


The well known dichotomy conjecture of Feder and Vardi states that

for every finite family Gamma of constraints CSP(Gamma) is either

polynomially solvable or NP-hard. Bulatov and Jeavons reformulated

this conjecture in terms of the properties of Pol(Gamma),

where the latter is the collection of those $n$-ary

operations (n= 1,2,...) that keep all constraints in Gamma

invariant. We show that their algebraic condition boils down to

whether there are arbitrarily resilient functions in Pol(Gamma).

Equivalently, we can express this in the terms of the PCP theory:

CSP(Gamma) is NP-hard iff all long code tests created from

Gamma that passes with zero error admits only

juntas. Then, using this characterization and a result

of Dinur, Friedgut and Regev, we give an entirely new and

transparent proof to the Hell-Nesetril theorem, which states

that for a simple, connected and undirected graph H, the problem

CSP(H) is NP-hard if and only if H is non-bipartite.



We also introduce another notion of resilience (we call it strong

resilience), and we use it in the investigation of CSP problems

that 'do not have the ability to count.' The complexity of this class

is unknown. Several authors conjectured that CSP problems without

the ability to count have bounded width, or equivalently, that they can be

characterized by existential k-pebble games. The resolution of this

conjecture would be a major step towards the resolution of the dichotomy

conjecture. We show that CSP problems without the ability to count are exactly

the ones with strongly resilient term operations, which might give a handier

tool to attack the conjecture than the known algebraic characterizations.

Finally, we show that a yet stronger notion of resilience, when the term operation is

asymptotically constant, allows us to characterize the class of width one CSPs.



What emerges from our research, is that certain important algebraic conditions

that are usually expressed via identities have equivalent analytic definitions that rely on

asymptotic properties of term operations.



Joint work with Gabor Kun.