Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution

By Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan. 2009

88 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistical Learning Theory, Algorithms & Complexity

How researchers see this paper

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

In Artificial Intelligence

In Computational Theory and Mathematics

In Statistical Learning Theory

In Algorithms & Complexity

Citations in the corpus

Generalization and Equilibrium in Generative Adversarial Nets (GANs) (2017, neutral): “We note that similar results have been shown before in study of pseudorandomness [Trevisan et al., 2009] and model criticism [Gretton et al., 2012].”
Learning DNF Expressions from Fourier Spectrum (2012, methodology): “This idea is based on Impagliazzo’s (1995) argument in the context of hardcore set construction, and is also the basis for the algorithm of Trevisan et al. (2009).”
Learning geometric concepts with nasty noise (2017, methodology): “Given this fact, we leverage known algorithmic techniques [9, 36] that allow us to efficiently find an accurate proper hypothesis with approximately these Chow parameters.”
Non interactive simulation of correlated distributions is decidable (2017, methodology): “While these iterative algorithms have recently been used to prove structural results in complexity theory [DDFS14, LRS15, TTV09], since our algorithm is in the multidimensional setting, it is somewhat more delicate than these applications.”
A relative Szemerédi theorem (2013, methodology): “This is a strengthening of an earlier theorem used by Tao in his proof that the Gaussian primes contain arbitrarily shaped constellations and, by standard arguments, allows us to deduce the relative Szemerédi theorem.”
Iterative Constructions and Private Data Release (2011, methodology): “We also use the fact that the proof extends to more general settings, as was noted by [TTV09].”
Multicalibration: Calibration for the (Computationally-Identifiable) Masses (2018, methodology): “Our algorithmic result for multicalibration bears similarity to works from the online learning literature (Blum & Mansour, 2007; Khot & Ponnuswami, 2008; Trevisan et al., 2009).”