Fagin defined the class \(NP\) by the means of Existential Second-Order logic. Feder and Vardi expressed it (up to polynomial equivalence) by special fragments of Existential Second-Order logic (SNP), while the authors used forbidden expanded substructures (cf. lifts and shadows). Consequently, for such problems there is no dichotomy, unlike for CSPs.

We give a deterministic algorithm for solving the (1 + ε) approximate Closest Vector Problem (CVP) on any n dimensional lattice and any norm in 2O(n)(1 + 1/ε)n time and 2n poly(n) space. Our algorithm builds on the lattice point enumeration techniques of Micciancio and Voulgaris (STOC 2010) and Dadush, Peikert and Vempala (FOCS 2011), and gives an elegant, deterministic alternative to the “AKS Sieve” based algorithms for (1 + ε)-CVP (Ajtai, Kumar, and Sivakumar; STOC 2001 and CCC 2002). Furthermore, assuming the existence of a poly(n)-space and 2O(n) time algorithm for exact CVP in the l2 norm, the space complexity of our algorithm can be reduced to polynomial. Our main technical contribution is a method for “sparsifying” any input lattice while approximately maintaining its metric structure. To this end, we employ the idea of random sublattice restrictions, which was first employed by Khot (FOCS 2003) for the purpose of proving hardness for Shortest Vector Problem (SVP) under lp norms.

We say that an algorithm robustly decides a constraint satisfaction problem Π if it distinguishes at-least-(1 -ε)-satisfiable instances from less-than-(1 - r(ε))-satisfiable instances for some function r(ε) with r(ε) → 0 as ε → 0. In this paper we show that the canonical linear programming relaxation robustly decides Π if and only if Π has "width 1" (in the sense of Feder and Vardi).

The well known dichotomy conjecture of Feder and Vardi states that for every finite family Γ of constraints CSP(Γ) is either polynomially solvable or NP-hard. Bulatov and Jeavons reformulated this conjecture in terms of the properties of the algebra Pol(Γ), where the latter is the collection of those n-ary operations (n= 1,2,...) that keep all constraints in Γ invariant. We show that the algebraic condition boils down to whether there are arbitrarily resilient functions in Pol(Γ). 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 to characterize CSP problems that 'do not have the ability to count.' Very recently this class has been shown to be equivalent with the the class of bounded width problems, i.e. the class of CSPs that be described by existential k-pebble games. What emerges from our research, is that certain important algebraic conditions that are usually expressed via identities have equivalent definitions that rely on asymptotic properties of term operations. Our new notions have a potential to show hardness of CSPs (as demonstrated on the Hell-Nesetril theorem), or to prove their tractability.