15 citations · 22 across the 3 of their papers we have counts for
3 papers
cs.DS2008
Tight Bounds for Hashing Block Sources
Kai-Min Chung, Salil Vadhan
It is known that if a 2-universal hash function is applied to elements of a {\em block source} , where each item has enough min-entropy conditioned on the…
math.CO2008★ 15 cited
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…
math.CO2004★ 7 cited
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…