Dor Minzer

activity

20242026

collaborators

16 papers

math.CO2026

A Counting Lemma for Somewhat Restricted 3-APs

Amey Bhangale, Subhash Khot, Yang P. Liu +1

For a prime $p \geq 3$ , a somewhat restricted $3$ -AP in $F_{p}^{n}$ is a triplet $(x, x + a, x + 2 a)$ , where $x \in F_{p}^{n}$ and $a \in {0, 1, 2}^{n}$ . We prove a counting lemma fo…

cs.CC2026

An FKN Theorem for the Binary Grassmann Scheme

Yuval Filmus, Anqi Li, Dor Minzer

A classical theorem due to Friedgut, Kalai and Naor asserts that if a function $f : {0, 1}^{n} \to {- 1, 1}$ close to a degree $1$ function, then either $f$ or $- f$ is close to ei…

cs.CC2026

On Approximability of Satisfiable k-CSPs: V

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], w…

cs.CC2026

Near Optimal Alphabet-Soundness Tradeoff PCPs

Dor Minzer, Kai Zhe Zheng

We show that for all $ε > 0$ , for sufficiently large $q \in N$ power of $2$ , for all $I^´ > 0$ , it is NP-hard to distinguish whether a given $2$ -Prover- $1$ -Round projec…

cs.CC2026

Near-Optimal Space Lower Bounds for Streaming CSPs

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 fix…

cs.CC2026

A Dichotomy Theorem for Multi-Pass Streaming CSPs

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…