20 citations · 33 across the 25 of their papers we have counts for
29 papers · 1 filter
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…
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…
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…
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…
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…