Dor Minzer

activity

20192026

most citedGlobal hypercontractivity and its applications

20 citations · 58 across the 39 of their papers we have counts for

collaborators

51 papers

cs.CC2026

Improved Multilayered PCPs and Hypergraph Vertex Cover

Karthik C. S., Dor Minzer

We present two elementary constructions of multilayered PCPs that improve upon prior constructions in two ways. Specifically, we give one construction of quasi-linear size, and ano…

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

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

The Lens of Abelian Embeddings

Dor Minzer

We discuss a recent line of research investigating inverse theorems with respect to general k-wise correlations, and explain how such correlations arise in different contexts in ma…

cs.CC2025

A Distance Amplification Lemma for Monotonicity

Dor Minzer

We show a procedure that, given oracle access to a function $f : {0, 1}^{n} \to {0, 1}$ , produces oracle access to a function $f^{'} : {0, 1}^{n^{'}} \to {0, 1}$ such that if $f$ i…

cs.CC2025

3-Query RLDCs are Strictly Stronger than 3-Query LDCs

Tom Gur, Dor Minzer, Guy Weissenberg +1

We construct $3$ -query relaxed locally decodable codes (RLDCs) with constant alphabet size and length $O ~ (k^{2})$ for $k$ -bit messages. Combined with the lower bound of $\tild…

cs.CC2025

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems

Amey Bhangale, Mark Braverman, Subhash Khot +3

Let $G$ be a $k$ -player game with value $< 1$ , whose query distribution is such that no marginal on $k - 1$ players admits a non-trivial Abelian embedding. We show that for…

cs.CC2025

Near Optimal Hardness of Approximating $k$ -CSP

Dor Minzer, Kai Zhe Zheng

We show that for every $k \in N$ and $ε > 0$ , for large enough alphabet $R$ , given a $k$ -CSP with alphabet size $R$ , it is NP-hard to distinguish between the case th…

cs.CC2025

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…

cs.CC2025★ 1 cited

Improved Round-by-round Soundness IOPs via Reed-Muller Codes

Dor Minzer, Kai Zhe Zheng

We give an IOPP (interactive oracle proof of proximity) for trivariate Reed-Muller codes that achieves the best known query complexity in some range of security parameters. Specifi…

cs.DS2025

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut

Yumou Fei, Dor Minzer, Shuo Wang

In the Max-Cut problem in the streaming model, an algorithm is given the edges of an unknown graph $G = (V, E)$ in some fixed order, and its goal is to approximate the size of the l…

cs.DC2024

Constant Degree Networks for Almost-Everywhere Reliable Transmission

Mitali Bafna, Dor Minzer

In the almost-everywhere reliable message transmission problem, introduced by [Dwork, Pippenger, Peleg, Upfal'86], the goal is to design a sparse communication network $G$ that sup…

math.CO2024★ 1 cited

Reasonable Bounds for Combinatorial Lines of Length Three

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

We prove that any subset $A \subseteq [3]^{n}$ with $3^{- n} ∣ A ∣ \geq (lo g lo g lo g lo g n)^{- c}$ contains a combinatorial line of length $3$ , i.e., $x, y, z \in A$ , not all equal, with…

cs.CC2024★ 1 cited

On Approximability of Satisfiable $k$ -CSPs: VII

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

Let $Σ_{1}, \dots, Σ_{k}$ be finite alphabets, and let $μ$ be a distribution over $Σ_{1} \times \dots \times Σ_{k}$ in which the probability of each atom is at least $α$ . We prove that if $…

cs.CC2024★ 1 cited

On Approximability of Satisfiable $k$ -CSPs: VI

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

We prove local and global inverse theorems for general $3$ -wise correlations over pairwise-connected distributions. Let $μ$ be a distribution over $Σ \times Γ \times Φ$ such that the…

cs.CC2024

Parallel Repetition for $3$ -Player XOR Games

Amey Bhangale, Mark Braverman, Subhash Khot +2

In a $3$ - $XOR$ game $G$ , the verifier samples a challenge $(x, y, z) \sim μ$ where $μ$ is a probability distribution over $Σ \times Γ \times Φ$ , and a map $t\colon Σ\ti…

cs.CC2024★ 2 cited

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.CC2024★ 2 cited

Quasi-Linear Size PCPs with Small Soundness from HDX

Mitali Bafna, Dor Minzer, Nikhil Vyas

We construct 2-query, quasi-linear size probabilistically checkable proofs (PCPs) with arbitrarily small constant soundness, improving upon Dinur's 2-query quasi-linear size PCPs w…

cs.CC2024

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 $δ > 0$ , it is NP-hard to distinguish whether a given $2$ -Prover- $1$ -Round project…

math.CO2024

A Dense Model Theorem for the Boolean Slice

Gil Kalai, Noam Lifshitz, Dor Minzer +1

The (low soundness) linearity testing problem for the middle slice of the Boolean cube is as follows. Let $ε > 0$ and $f$ be a function on the middle slice on the Boolean c…

cs.CC2024★ 2 cited

Constant Degree Direct Product Testers with Small Soundness

Mitali Bafna, Noam Lifshitz, Dor Minzer

Let $X$ be a $d$ -dimensional simplicial complex. A function $F : X (k) \to {0, 1}^{k}$ is said to be a direct product function if there exists a function $f : X (1) \to {0, 1}$ …

math.CO2024

Product Mixing in Compact Lie Groups

David Ellis, Guy Kindler, Noam Lifshitz +1

If $G$ is a group, we say a subset $S$ of $G$ is product-free if the equation $x y = z$ has no solutions with $x, y, z \in S$ . For $D \in N$ , a group $G$ is said to be $D$ -quas…

cs.CC2023

Parallel Repetition of k-Player Projection Games

Amey Bhangale, Mark Braverman, Subhash Khot +2

We study parallel repetition of k-player games where the constraints satisfy the projection property. We prove exponential decay in the value of a parallel repetition of projection…

Improved Multilayered PCPs and Hypergraph Vertex Cover

A Counting Lemma for Somewhat Restricted 3-APs

An FKN Theorem for the Binary Grassmann Scheme

Near-Optimal Space Lower Bounds for Streaming CSPs

The Lens of Abelian Embeddings

A Distance Amplification Lemma for Monotonicity

3-Query RLDCs are Strictly Stronger than 3-Query LDCs

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems

Near Optimal Hardness of Approximating k-CSP

A Dichotomy Theorem for Multi-Pass Streaming CSPs

Improved Round-by-round Soundness IOPs via Reed-Muller Codes

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut

Constant Degree Networks for Almost-Everywhere Reliable Transmission

Reasonable Bounds for Combinatorial Lines of Length Three

On Approximability of Satisfiable k-CSPs: VII

On Approximability of Satisfiable k-CSPs: VI

Parallel Repetition for 3-Player XOR Games

On Approximability of Satisfiable k-CSPs: V

Quasi-Linear Size PCPs with Small Soundness from HDX

Near Optimal Alphabet-Soundness Tradeoff PCPs

A Dense Model Theorem for the Boolean Slice

Constant Degree Direct Product Testers with Small Soundness

Product Mixing in Compact Lie Groups

Parallel Repetition of k-Player Projection Games

Near Optimal Hardness of Approximating $k$ -CSP

On Approximability of Satisfiable $k$ -CSPs: VII

On Approximability of Satisfiable $k$ -CSPs: VI

Parallel Repetition for $3$ -Player XOR Games