Relaxations for the constraint satisfaction problem (CSP) include bounded width, linear program (LP), semidefinite program (SDP), affine integer program (AIP), and the combined LP+AIP of Brakensiek, Guruswami, Wrochna, and Živný (SICOMP 2020). Tightening relaxations systematically leads to hierarchies and stronger algorithms. For the LP+AIP hierarchy, a constant level lower bound for approximate graph coloring was given by Ciardo and Živný (STOC 2023). We prove the first linear (and hence optimal) level lower bound for LP+AIP and its stronger variant, SDP+AIP. For each hierarchy, our bound holds for random instances of a broad class of CSPs that we call 𝜏-wise neutral. We extend to other hierarchies the LP lower bound techniques in Benabbas, Georgiou, Magen and Tulsiani (ToC 2012) and Kothari, Mori, O’Donnell, and Witmer (STOC 2017), and simplify the SDP solution construction in the latter.

We give a unified way of testing and learning finite Markov chains from a single Markovian trajectory, using the idea of $k$-cover time introduced here. The $k$-cover time is the expected length of a random walk to cover every state at least $k$ times. This generalizes the notion of cover time in the literature. The error metric in the testing and learning problems is the infinity matrix norm between the transition matrices, as considered by Wolfer and Kontorovich. Specifically, we show that if we can learn or test discrete distributions using $k$ samples, then we can learn or test Markov chains using a number of samples equal to the $k$-cover time of the chain, up to constant factors. We then derive asymptotic bounds on the $k$-cover time in terms of the number of states, minimum stationary probability and the cover time of the chain. Our bounds are tight for reversible Markov chains and almost tight (up to logarithmic factors) for irreducible ones. Our results on $k$-cover time yield sample complexity bounds for a wider range of learning and testing tasks (including learning, uniformity testing, identity testing, closeness testing and their tolerant versions) over Markov chains, and can be applied to a broader family of Markov chains (irreducible and reversible ones) than previous results which only applies to ergodic ones.

Analyzing the mixing time of random walks is a well- studied problem with applications in random sampling and more recently in graph partitioning. In this work, we present new analysis of random walks and evolving sets using more combinatorial graph structures, and show some implications in approximating small-set expansion. On the other hand, we provide examples showing the limitations of using random walks and evolving sets in disproving the small-set expansion hypothesis. 1. We define a combinatorial analog of the spectral gap, and use it to prove the convergence of non- lazy random walks. A corollary is a tight lower bound on the small-set expansion of graph powers for any graph. 2. We prove that random walks converge faster when the robust vertex expansion of the graph is larger. This provides an improved analysis of the local graph partitioning algorithm using the evolving set process, and also derives an alternative proof of an improved Cheeger's inequality. 3. We give an example showing that the evolving set process fails to disprove the small-set expansion hypothesis. This refutes a conjecture of Oveis Gharan and shows the limitations of all existing local graph partitioning algorithms in approximating small-set expansion.

It is well known that Sparse PCA (Sparse Principal Component Analysis) is NP-hard to solve exactly on worst-case instances. What is the complexity of solving Sparse PCA approximately? Our contributions include: \beginenumerate \item a simple and efficient algorithm that achieves an n^-1/3-approximation; \item NP-hardness of approximation to within (1-\varepsilon), for some small constant \varepsilon > 0; \item SSE-hardness of approximation to within \em any constant factor; and \item an \exp\exp\left(Ω\left(\sqrt\log \log n\right)\right) (“quasi-quasi-polynomial”) gap for the standard semidefinite program. \endenumerate

We show optimal (up to a constant factor) NP-hardness for a maximum constraint satisfaction problem with k variables per constraint (Max- k CSP) whenever k is larger than the domain size. This follows from our main result concerning CSPs given by a predicate: A CSP is approximation resistant if its predicate contains a subgroup that is balanced pairwise independent. Our main result is analogous to Austrin and Mossel’s, bypassing their Unique-Games Conjecture assumption whenever the predicate is an abelian subgroup. Our main ingredient is a new gap-amplification technique inspired by XOR lemmas. Using this technique, we also improve the NP-hardness of approximating Independent-Set on bounded-degree graphs, Almost-Coloring, Label-Cover, and various other problems.

We prove that for every ε>0 and predicate P:{0,1}k-> {0,1} that supports a pairwise independent distribution, there exists an instance I of the Max P constraint satisfaction problem on n variables such that no assignment can satisfy more than a ~(|P-1(1)|)/(2k)+ε fraction of I's constraints but the degree Ω(n) Sum of Squares semidefinite programming hierarchy cannot certify that I is unsatisfiable. Similar results were previously only known for weaker hierarchies.

We study the question of closeness testing for two discrete distributions. More precisely, given samples from two distributions p and q over an n-element set, we wish to distinguish whether p = q versus p is at least ∊-far from q, in either ℓ1 or ℓ2 distance. Batu et al [BFR+00, BFR+13] gave the first sub-linear time algorithms for these problems, which matched the lower bounds of [Val11] up to a logarithmic factor in n, and a polynomial factor of ∊. In this work, we present simple testers for both the ℓ1 and ℓ2 settings, with sample complexity that is information-theoretically optimal, to constant factors, both in the dependence on n, and the dependence on ∊; for the ℓ1 testing problem we establish that the sample complexity is Θ(max{n2/3/∊4/3,n1/2/∊2}).

We give a computationally efficient semi-agnostic algorithm for learning univariate probability distributions that are well approximated by piecewise polynomial density functions. Let p be an arbitrary distribution over an interval I, and suppose that p is τ-close (in total variation distance) to an unknown probability distribution q that is defined by an unknown partition of I into t intervals and t unknown degree d polynomials specifying q over each of the intervals. We give an algorithm that draws Õ(t(d + 1)/ε2) samples from p, runs in time poly(t, d + 1, 1/ε), and with high probability outputs a piecewise polynomial hypothesis distribution h that is (14τ + ε)-close to p in total variation distance. Our algorithm combines tools from real approximation theory, uniform convergence, linear programming, and dynamic programming. Its sample complexity is simultaneously near optimal in all three parameters t, d and ε; we show that even for τ = 0, any algorithm that learns an unknown t-piecewise degree-d probability distribution over I to accuracy ε must use [EQUATION] samples from the distribution, regardless of its running time.

Suppose Alice and Bob receive strings X=(X1,...,Xn) and Y=(Y1,...,Yn) each uniformly random in [s]n, but so that X and Y are correlated. For each symbol i, we have that Yi=Xiwith probability 1-ε and otherwise Yiis chosen independently and uniformly from [s]. Alice and Bob wish to use their respective strings to extract a uniformly chosen common sequence from [s]k, but without communicating. How well can they do? The trivial strategy of outputting the first k symbols yields an agreement probability of (1-ε+ε/s)k. In a recent work by Bogdanov and Mossel, it was shown that in the binary case where s=2 and k=k(ε) is large enough then it is possible to extract k bits with a better agreement probability rate. In particular, it is possible to achieve agreement probability (kε)-1/2·2-kε/(2(1-ε/2))using a random construction based on Hamming balls, and this is optimal up to lower order terms. In this paper, we consider the same problem over larger alphabet sizes s and we show that the agreement probability rate changes dramatically as the alphabet grows. In particular, we show no strategy can achieve agreement probability better than (1-ε)k(1+δ(s))kwhere δ(s)→ 0 as s→∞. We also show that Hamming ball-based constructions have much lower agreement probability rate than the trivial algorithm as s→∞. Our proofs and results are intimately related to subtle properties of hypercontractive inequalities.

We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems, polynomial-sized linear programs are exactly as powerful as programs arising from a constant number of rounds of the Sherali-Adams hierarchy. In particular, any polynomial-sized linear program for MAX CUT has an integrality gap of 1/2 and any such linear program for MAX 3-SAT has an integrality gap of 7/8.

Let be a class of probability distributions over the discrete domain [n] = {1, …, n}. We show that if satisfies a rather general condition – essentially, that each distribution in can be well-approximated by a variable-width histogram with few bins – then there is a highly efficient (both in terms of running time and sample complexity) algorithm that can learn any mixture of k unknown distributions from . We analyze several natural types of distributions over [n], including log-concave, monotone hazard rate and unimodal distributions, and show that they have the required structural property of being well-approximated by a histogram with few bins. Applying our general algorithm, we obtain near-optimally efficient algorithms for all these mixture learning problems as described below. More precisely, Log-concave distributions: We learn any mixture of k log-concave distributions over [n] using k · Õ(1/ε4) samples (independent of n) and running in time Õ(k log(n)/ε4) bit-operations (note that reading a single sample from [n] takes Θ(log n) bit operations). For the special case k = 1 we give an efficient algorithm using Õ(1/ε3) samples; this generalizes the main result of [DDS12b] from the class of Poisson Binomial distributions to the much broader class of all log-concave distributions. Our upper bounds are not far from optimal since any algorithm for this learning problem requires Ω(k/ε5/2) samples. Monotone hazard rate (MHR) distributions: We learn any mixture of k MHR distributions over [n] using O(k log(n/ε)/ε4) samples and running in time Õ(k log (n)/ε4) bit-operations. Any algorithm for this learning problem must use Ω(k log(n)/ε3) samples. Unimodal distributions: We give an algorithm that learns any mixture of k unimodal distributions over [n] using O(k log(n)/ε4) samples and running in time Õ(k log2(n)/ε4) bit-operations. Any algorithm for this problem must use Ω(k log(n)/ε3) samples.

We show optimal (up to constant factor) NP-hardness for Max-k-CSP over any domain, whenever k is larger than the domain size. This follows from our main result concerning predicates over abelian groups. We show that a predicate is approximation resistant if it contains a subgroup that is balanced pairwise independent. This gives an unconditional analogue of Austrin--Mossel hardness result, bypassing the Unique-Games Conjecture for predicates with an abelian subgroup structure. Our main ingredient is a new gap-amplification technique inspired by XOR-lemmas. Using this technique, we also improve the NP-hardness of approximating Independent-Set on bounded-degree graphs, Almost-Coloring, Two-Prover-One-Round-Game, and various other problems.

We consider random instances of constraint satisfaction problems (CSPs) where each variable has domain size $O(1)$, each constraint is on $O(1)$ variables, and the constraints are chosen from a specified distribution. The number of constraints is $cn$, where $c$ is a constant. We prove that for every possible distribution, either the resolution complexity is almost surely polylogarithmic for sufficiently large $c$, or it is almost surely exponential for every $c>0$. We characterize the distributions of each type. To do so, we introduce a closure operation on constraint sets which yields the set of all constraints that, in some sense, appear implicitly in the random CSP.

We give the first tight integrality gap for Vertex Cover in the Sherali-Adams SDP system. More precisely, we show that for every \epsilon >0, the standard SDP for Vertex Cover that is strengthened with the level-6 Sherali-Adams system has integrality gap 2-\epsilon. To the best of our knowledge this is the first nontrivial tight integrality gap for the Sherali-Adams SDP hierarchy for a combinatorial problem with hard constraints. For our proof we introduce a new tool to establish Local-Global Discrepancy which uses simple facts from high-dimensional geometry. This allows us to give Sherali-Adams solutions with objective value n(1/2+o(1)) for graphs with small (2+o(1)) vector chromatic number. Since such graphs with no linear size independent sets exist, this immediately gives a tight integrality gap for the Sherali-Adams system for superconstant number of tightenings. In order to obtain a Sherali-Adams solution that also satisfies semidefinite conditions, we reduce semidefiniteness to a condition on the Taylor expansion of a reasonably simple function that we are able to establish up to constant-level SDP tightenings. We conjecture that this condition holds even for superconstant levels which would imply that in fact our solution is valid for superconstant level Sherali-Adams SDPs.

We consider random instances of constraint satisfaction problems where each variable has domain size O(1), each constraint is on O(1) variables and the constraints are chosen from a specified distribution. The number of constraints is cn where c is a constant. We prove that for every possible distribution, either the resolution complexity is almost surely polylogarithmic for sufficiently large c, or it is almost surely exponential for every c > 0. We characterize the distributions of each type. To do so, we introduce a closure operation on a set of constraints which yields the set of all constraints that, in some sense, appear implicitly in the random CSP.