8 citations · 22 across the 12 of their papers we have counts for
16 papers
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…
Quasirandom groups enjoy interleaved mixing
Harm Derksen, Emanuele Viola
Let be a group such that any non-trivial representation has dimension at least . Let and be distributions over…
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…
How to Store a Random Walk
Emanuele Viola, Omri Weinstein, Huacheng Yu
Motivated by storage applications, we study the following data structure problem: An encoder wishes to store a collection of jointly-distributed files $\overline{X}:=(X_1,X_2,\ldot…