Dense Subsets of Pseudorandom Sets

By Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan. 2008

141 citations recorded by the source corpus.

Subfields: Algebra and Number Theory, Computational Theory and Mathematics, Discrete Mathematics and Combinatorics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algebra and Number Theory

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

Citations in the corpus

The Composition Theorem for Differential Privacy (2013, neutral): “While the state-of-the-art work [DRV10] needed recourse to sophisticated mathematical results in [RTTV08, TZ08, GT04] to derive their results, our strengthening is arrived at using relatively elementary techniques.”
Boosting and Differential Privacy (2010, background): “(This can be viewed as an information-theoretic analogue of the “dense model theorems” of [15], [25], [21], [20].”
Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution (2009, methodology): “Although non-constructivity seemed inherent in the proofs of [RTTV], [Imp2], [Gow], both of the proofs we give for our main theorem are based on proof techniques previously used for Impagliazzo’s Hardcore Lemma, namely the min-max theorem of game theory (used in Nisan’s proof) and boosting algorithm”
Computational Differential Privacy (2009, methodology): “We make use of the following lemma proved in [20]:”
On the KŁR conjecture in random graphs (2013, methodology): “The method employed by Conlon and Gowers [17] to determine probabilistic thresholds for combinatorial theorems hinges on proving a transference principle [39, 40, 71].”
Combinatorial theorems in sparse random sets (2010, result): “[44] O. Reingold, L. Trevisan, M. Tulsiani, and S. Vadhan, Dense subsets of pseudorandom sets, in Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science , IEEE Computer Society, Washington DC, 2008, pp. 76-85.”
The Complexity of Differential Privacy (2017, background): “When considering a single pair of random variables (Y,Z), the dense model theorem of [55, 100, 90] says that pseudodensity is equivalent to Y being computationally indistinguishable from a random variable Ỹ that truly has density at least ρ in Z.”
Decompositions, approximate structure, transference, and the Hahn–Banach theorem (2008, result): “A proof along similar lines has been discovered independently by Reingold, Trevisan, Tulsiani, and Vadhan [16].”
A relative Szemerédi theorem (2013, methodology): “This is also closely related to the transference theorem used by Green and Tao (see, for example, [19] or [33, 49], where it is also referred to as the dense model theorem).”
Leakage-Resilient Cryptography (2008, background): “This result (in a more general form) has independently been discovered by [34, 16].”