2 citations · 2 across the 5 of their papers we have counts for
19 papers · 1 filter
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 close to a degree function, then either or is close to ei…
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…
Near Optimal Alphabet-Soundness Tradeoff PCPs
Dor Minzer, Kai Zhe Zheng
We show that for all , for sufficiently large power of , for all , it is NP-hard to distinguish whether a given -Prover--Round projec…
Near-Optimal Space Lower Bounds for Streaming CSPs
Yumou Fei, Dor Minzer, Shuo Wang
In a streaming constraint satisfaction problem (streaming CSP), a -pass algorithm receives the constraints of an instance sequentially, making passes over the input in a fix…
A Dichotomy Theorem for Multi-Pass Streaming CSPs
Yumou Fei, Dor Minzer, Shuo Wang
We show a dichotomy result for -pass streaming algorithms for all CSPs and for up to polynomially many passes. More precisely, we prove that for any arity parameter , finite…
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…