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.