15 citations · 24 across the 3 of their papers we have counts for
3 papers
New Proofs of the Green-Tao-Ziegler Dense Model Theorem: An Exposition
Omer Reingold, Luca Trevisan, Madhur Tulsiani +1
Green, Tao and Ziegler prove ``Dense Model Theorems'' of the following form: if R is a (possibly very sparse) pseudorandom subset of set X, and D is a dense subset of R, then D may…
The Player's Effect
Ronen Gradwohl, Omer Reingold, Ariel Yadin +1
In a function that takes its inputs from various players, the effect of a player measures the variation he can cause in the expectation of that function. In this paper we prove a t…
Entropy waves, the zig-zag graph product, and new constant-degree
Omer Reingold, Salil Vadhan, Avi Wigderson
The main contribution of this work is a new type of graph product, which we call the {\it zig-zag product}. Taking a product of a large graph with a small graph, the resulting grap…