20 citations · 58 across the 39 of their papers we have counts for
7 papers · 1 filter
A Distance Amplification Lemma for Monotonicity
Dor Minzer
We show a procedure that, given oracle access to a function , produces oracle access to a function such that if i…
3-Query RLDCs are Strictly Stronger than 3-Query LDCs
Tom Gur, Dor Minzer, Guy Weissenberg +1
We construct -query relaxed locally decodable codes (RLDCs) with constant alphabet size and length for -bit messages. Combined with the lower bound of $\tild…
An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
Amey Bhangale, Mark Braverman, Subhash Khot +3
Let be a -player game with value , whose query distribution is such that no marginal on players admits a non-trivial Abelian embedding. We show that for…
Near Optimal Hardness of Approximating -CSP
Dor Minzer, Kai Zhe Zheng
We show that for every and , for large enough alphabet , given a -CSP with alphabet size , it is NP-hard to distinguish between the case th…
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…
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…
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 in some fixed order, and its goal is to approximate the size of the l…