"Lower bounds for the dense model theorem and computational entropy"
Sam McGuire (UCSD)
Monday, March 1st 2021, 2-3pm
Abstract:
Abstract: We study the computational complexity of the dense model theorem, a generic pseudorandomness result with applications to diverse areas of math and TCS such as number theory, graph theory and hardness amplification. The dense model theorem can be phrased as an equivalence between different natural definitions of computational entropy describing the “ostensible” entropy of a random variable. This perspective is relevant to further applications of the dense model theorem in, for example, cryptography and differential privacy. This talk will discuss recent work where we construct simple situations in which the dense model theorem is false. As a byproduct, the corresponding notions of computational entropy are shown to be distinct and, in particular, reductions between certain notions of computational entropy have necessary computational overheads. Additionally, these can be used to construct functions for which the hardcore lemma, a fundamental tool in circuit complexity, is false. Based on joint work with Russell Impagliazzo appearing in ITCS21.