40 citations · 222 across the 36 of their papers we have counts for
Showing 2008Show all
2 papers · 1 filter
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…