Let P:{0,1}k → {0,1} be a nontrivial k-ary predicate. Consider a random instance of the constraint satisfaction problem (P) on n variables with Δ n constraints, each being P applied to k randomly chosen literals. Provided the constraint density satisfies Δ ≫ 1, such an instance is unsatisfiable with high probability. The refutation problem is to efficiently find a proof of unsatisfiability.

We show that for any odd k and any instance I of the max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a 1/2 + Omega(1/sqrt(D)) fraction of I's constraints, where D is a bound on the number of constraints that each variable occurs in. This improves both qualitatively and quantitatively on the recent work of Farhi, Goldstone, and Gutmann (2014), which gave a quantum algorithm to find an assignment satisfying a 1/2 Omega(D^{-3/4}) fraction of the equations. For arbitrary constraint satisfaction problems, we give a similar result for "triangle-free" instances; i.e., an efficient algorithm that finds an assignment satisfying at least a mu + Omega(1/sqrt(degree)) fraction of constraints, where mu is the fraction that would be satisfied by a uniformly random assignment.

Let P be a k-ary predicate over a finite alphabet. Consider a random CSP(P) instance I over n variables with m constraints. When m ≫ n the instance will be unsatisfiable with high probability and we want to find a certificate of unsatisfiability. When P is the 3-ary OR predicate, this is the well-studied problem of refuting random 3-SAT formulas and an efficient algorithm is known only when m ≫ n3/2. Understanding the density required for refutation of other predicates is important in cryptography, proof complexity, and learning theory. Previously, it was known that for a k-ary predicate, having m ≫≫n[k/2]constraints suffices for refutation. We give a criterion for predicates that often yields efficient refutation algorithms at much lower densities. Specifically, if P fails to support a t-wise uniform distribution, then there is an efficient algorithm that refutes random CSP(P) instances whp when m ≫ nt/2. Indeed, our algorithm will “somewhat strongly” refute the instance I, certifying Opt(I) ≤ 1 - Ωk(1). If t = k then we get the strongest possible refutation, certifying Opt(I) ≤ E[P] + o(1). This last result is new even for random k-SAT. Prior work on SDP hierarchies has given some evidence that efficient refutation of random CSP(P) may be impossible when m ≫ nt/2; thus there is an indication that our algorithm's dependence on m is optimal for every P, at least in the context of SDP hierarchies. As an application of our result, we falsify assumptions used to show hardness-of-learning in recent work of Daniely, Linial, and Shalev-Shwartz.

Furthering the study of cryptography in constant parallel time, we give new evidence for the security of Gold Reich's candidate pseudorandom generator with near-optimal, polynomial stretch. Our evidence consists both of security against sub exponential-time linear attacks as well as sub exponential-time attacks using SDP hierarchies such as Sherali-Adams+ and Lasserre/Parrilo. More specifically, instantiating Gold Reich's generator with the 5-ary "Tri-Sum-And" predicate, we get a candidate 5-local PRG which is secure against both linear attacks and attacks based on the Lasserre/Parrilo SDP hierarchy. Previous works with such small locality gave polynomially less stretch and were only shown to be secure against linear attacks. Our result is essentially optimal, as known SDP/spectral techniques show the generator would not be secure if its stretch was higher by any polynomial factor. More generally, we show that (a slight variant of) Gold Reich's generator can have stretch increasing with the degree of the smallest nonzero Fourier coefficient of the predicate while resisting sub exponential-time attacks based on the Sherali-Adams+ SDP hierarchy. Again, the dependence on the degree is (potentially) optimal due to known SDP/spectral methods which succeed at any polynomially higher stretch. Finally, for a large family of predicates we also extend this result to security against the much stronger Lasserre/Parrilo SDP hierarchy.

We give a 2-approximation algorithm for the non-uniform Sparsest Cut problem that runs in time nO(k), where k is the treewidth of the graph. This improves on the previous 22k-approximation in time poly(n) 2O(k) due to Chlamtac et al. [18].