Dor Minzer

activity

20192026

most citedGlobal hypercontractivity and its applications

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

collaborators

Showing 2026Show all

5 papers · 1 filter

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…