8 citations · 22 across the 12 of their papers we have counts for
9 papers · 1 filter
Exponential Correlation Bounds for Polynomials
Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee +3
We prove that the XOR of majorities on disjoint blocks of bits has correlation at most with every Boolean-valued degree- polynomial over an arbit…
On Hardness Assumptions Needed for "Extreme High-End'' PRGs and Fast Derandomization
Ronen Shaltiel, Emanuele Viola
The hardness vs.~randomness paradigm aims to explicitly construct pseudorandom generators that fool circuits of size , assuming the existence…
On correlation bounds against polynomials
Peter Ivanov, Liam Pavlovic, Emanuele Viola
We study the fundamental challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over . Our main contributions include: 1…
Fourier growth of structured -polynomials and applications
Jarosław Błasiok, Peter Ivanov, Yaonan Jin +3
We analyze the Fourier growth, i.e. the Fourier weight at level (denoted ), of various well-studied classes of "structured" -polynomials. This stud…
Challenges in computational lower bounds
Emanuele Viola
We draw two incomplete, biased maps of challenges in computational complexity lower bounds.
Local reductions
Hamid Jahanjou, Eric Miles, Emanuele Viola
We reduce non-deterministic time to a 3SAT instance of quasilinear size such that there is an explicit circuit that on input an in…