Dor Minzer

Amey Bhangale, Subhash Khot, Dor Minzer

We propose a framework of algorithm vs. hardness for all Max-CSPs and demonstrate it for a large class of predicates. This framework extends the work of Raghavendra [STOC, 2008], who showed a similar result for almost satisfiable Max-CSPs. Our framework is based on a new hybrid approximation algorithm, which uses a combination of the Gaussian elimination technique (i.e., solving a system of linear equations over an Abelian group) and the semidefinite programming relaxation. We complement our algorithm with a matching dictator vs. quasirandom test that has perfect completeness. The analysis of our dictator vs. quasirandom test is based on a novel invariance principle, which we call the mixed invariance principle. Our mixed invariance principle is an extension of the invariance principle of Mossel, O'Donnell and Oleszkiewicz [Annals of Mathematics, 2010] which plays a crucial role in Raghavendra's work. The mixed invariance principle allows one to relate 3-wise correlations over discrete probability spaces with expectations over spaces that are a mixture of Guassian spaces and Abelian groups, and may be of independent interest.

Dor Minzer, Kai Zhe Zheng

We show that for all $\varepsilon>0$, for sufficiently large $q\in\mathbb{N}$ power of $2$, for all $δ>0$, it is NP-hard to distinguish whether a given $2$-Prover-$1$-Round projection game with alphabet size $q$ has value at least $1-δ$, or value at most $1/q^{1-\varepsilon}$. This establishes a nearly optimal alphabet-to-soundness tradeoff for $2$-query PCPs with alphabet size $q$, improving upon a result of [Chan, Journal of the ACM 2016]. Our result has the following implications: 1) Near optimal hardness for Quadratic Programming: it is NP-hard to approximate the value of a given Boolean Quadratic Program within factor $(\log n)^{1 - o(1)}$ under quasi-polynomial time reductions. This improves upon a result of [Khot, Safra, ToC 2013] and nearly matches the performance of the best known algorithms due to [Megretski, IWOTA 2000], [Nemirovski, Roos, Terlaky, Mathematical Programming 1999] and [Charikar, Wirth, FOCS 2004] that achieve $O(\log n)$ approximation ratio. 2) Bounded degree $2$-CSPs: under randomized reductions, for sufficiently large $d>0$, it is NP-hard to approximate the value of $2$-CSPs in which each variable appears in at most $d$ constraints within factor $(1-o(1))\frac{d}{2}$, improving upon a result of [Lee, Manurangsi, ITCS 2024]. 3) Improved hardness results for connectivity problems: using results of [Laekhanukit, SODA 2014] and [Manurangsi, Inf. Process. Lett., 2019], we deduce improved hardness results for the Rooted $k$-Connectivity Problem, the Vertex-Connectivity Survivable Network Design Problem and the Vertex-Connectivity $k$-Route Cut Problem.

Yumou Fei, Dor Minzer, Shuo Wang

We show a dichotomy result for $p$-pass streaming algorithms for all CSPs and for up to polynomially many passes. More precisely, we prove that for any arity parameter $k$, finite alphabet $Σ$, collection $\mathcal{F}$ of $k$-ary predicates over $Σ$ and any $c\in (0,1)$, there exists $0<s\leq c$ such that: 1. For any $\varepsilon>0$ there is a constant pass, $O_{\varepsilon}(\log n)$-space randomized streaming algorithm solving the promise problem $\text{MaxCSP}(\mathcal{F})[c,s-\varepsilon]$. That is, the algorithm accepts inputs with value at least $c$ with probability at least $2/3$, and rejects inputs with value at most $s-\varepsilon$ with probability at least $2/3$. 2. For all $\varepsilon>0$, any $p$-pass (even randomized) streaming algorithm that solves the promise problem $\text{MaxCSP}(\mathcal{F})[c,s+\varepsilon]$ must use $Ω_{\varepsilon}(n^{1/3}/p)$ space. Our approximation algorithm is based on a certain linear-programming relaxation of the CSP and on a distributed algorithm that approximates its value. This part builds on the works [Yoshida, STOC 2011] and [Saxena, Singer, Sudan, Velusamy, SODA 2025]. For our hardness result we show how to translate an integrality gap of the linear program into a family of hard instances, which we then analyze via studying a related communication complexity problem. That analysis is based on discrete Fourier analysis and builds on a prior work of the authors and on the work [Chou, Golovnev, Sudan, Velusamy, J.ACM 2024].

Yumou Fei, Dor Minzer, Shuo Wang

In a streaming constraint satisfaction problem (streaming CSP), a $p$-pass algorithm receives the constraints of an instance sequentially, making $p$ passes over the input in a fixed order, with the goal of approximating the maximum fraction of satisfiable constraints. We show near optimal space lower bounds for streaming CSPs, improving upon prior works. (1) Fei, Minzer and Wang (\textit{STOC 2026}) showed that for any CSP, the basic linear program defines a threshold $α_{\mathrm{LP}}\in [0,1]$ such that, for any $\varepsilon > 0$, an $(α_{\mathrm{LP}} - \varepsilon)$-approximation can be achieved using constant passes and polylogarithmic space, whereas achieving $(α_{\mathrm{LP}} + \varepsilon)$-approximation requires $Ω(n^{1/3}/p)$ space. We improve this lower bound to $Ω(\sqrt{n}/p)$, which is nearly tight for a gap version of the problem. (2) For $p=o(\log n)$, we further strengthen the lower bound to $Ω(n\cdot2^{-O_{\varepsilon}(p)})$. Combined with existing algorithmic results, this shows that $α_{\mathrm{LP}}$ is not only the limit of multi-pass polylogarithmic-space algorithms, but also the limit of single-pass sublinear-space algorithms on bounded-degree instances. (3) For certain CSPs, we show that there exists $α< 1$ such that achieving an $α$-approximation requires $Ω(n/p)$ space. Our proofs are Fourier analytic, building on the techniques of Fei, Minzer and Wang (\textit{STOC 2026}) and the Fourier-$\ell_1$-based lower bound method of Kapralov and Krachun (\textit{STOC 2019}).