This talk by UC San Diego computer science professor Russell Impagliazzo is part of the CSE department's Theory Seminar Series for Spring 2017.
Date: April 24, 2017
Time: 2-3pm
Location: Room 4258, CSE Building
Abstract
Green and Tao ([GT04]) used the existence of a dense subset indistinguishable from the primes under certain tests from a certain class to prove the existence of arbitrarily long prime arithmetic progressions. Tao and Ziegler ([TZ06]) showed some general conditions under which such a model exists. In [RTTV08], a quantitatively improved characterization was obtained using an argument based on Nisan’s proof of the Impagliazzo hard-core set theorem ([I95]) from computational complexity. Gowers ([Gow08]) independently obtained a similar improvement. Also independently, Stefan Dziembowski and Krysztof Pietrzak (FOCS 2007) gave a similar result for a different context.
We show that the existence of dense models can be reduced directly to the improved hardcore distribution results of Holenstein ([H05]). Using Holenstein’s uniform proof of an optimal density hard-core set theorem, we show that the dense models that one derives have a canonical form, with models being (sampleable from) functions defined in terms of tests from the original class.
One can view this reduction also in the context of learning theory. Here, we get a generic way to transform a boosting algorithm for binary classifiers into an algorithm that learns to produce samples from a distribution in the style of generative adversarial networks. We can use this transformation to get formal guarantees on GAN style algorithms, such as finding the maximum entropy indistinguishable distribution.
We can also use this connection in the context of regularity lemmas, such as the Szemeredi regularity lemma for graph cuts, the Gowers algebraic regularity lemma, and the Frieze-Kannan regularity lemma, as well as generalizations. Using recursive applications of the dense model theorem, we can give quantitatively improved regularity lemmas.
This talk will just give an overview, and will avoid most technical details.
Bio: Russell Impagliazzo joined the UC San Diego faculty in 1989 after receiving his Ph.D. in mathematics from UC Berkeley. His main research interests are randomized algorithms, pseudo-random generators, the theory of cryptography, lower bounds, and proof complexity. He has been an NSF Young Investigator, a Sloan Fellow, a Fulbright Scholar, a Guggenheim Fellow, and he is currently a Simons Fellow. He is a frequent member of program committees for conferences on the theory of computing, including FOCS, STOC, Computational Complexity, and Crypto. His joint work with Kabanets and Wigderson won a Best Paper Award from the Computational Complexity Conference, and joint work with Kabanets won a Best Paper Award at STOC. His work with Hastad, Levin and Luby won an award for an Outstanding Paper from SIAM.