Emanuele Viola
YOU?
Author Swipe
View article: Communication complexity of pointer chasing via the fixed-set lemma
Communication complexity of pointer chasing via the fixed-set lemma Open
I give a simple proof of a tight communication lower bound for pointer chasing.
View article: Pseudorandom bits for non-commutative programs
Pseudorandom bits for non-commutative programs Open
We obtain new explicit pseudorandom generators for several computational models involving groups. Our main results are as follows: 1. We consider read-once group-products over a finite group $G$, i.e., tests of the form $\prod_{i=1}^n g_i^…
View article: Boosting uniformity in quasirandom groups: fast and simple
Boosting uniformity in quasirandom groups: fast and simple Open
We study the communication complexity of multiplying $k\times t$ elements from the group $H=\text{SL}(2,q)$ in the number-on-forehead model with $k$ parties. We prove a lower bound of $(t\log H)/c^{k}$. This is an exponential improvement o…
View article: Pseudorandomness, symmetry, smoothing: II
Pseudorandomness, symmetry, smoothing: II Open
We prove several new results on the Hamming weight of bounded uniform and small-bias distributions. We exhibit bounded-uniform distributions whose weight is anti-concentrated, matching existing concentration inequalities. This construction…
View article: Resilient functions: Optimized, simplified, and generalized
Resilient functions: Optimized, simplified, and generalized Open
An $n$-bit boolean function is resilient to coalitions of size $q$ if any fixed set of $q$ bits is unlikely to influence the function when the other $n-q$ bits are chosen uniformly. We give explicit constructions of depth-$3$ circuits that…
View article: Pseudorandomness, symmetry, smoothing: I
Pseudorandomness, symmetry, smoothing: I Open
We prove several new results about bounded uniform and small-bias distributions. A main message is that, small-bias, even perturbed with noise, does not fool several classes of tests better than bounded uniformity. We prove this for thresh…
View article: On correlation bounds against polynomials
On correlation bounds against polynomials Open
We study the fundamental challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over $\mathbb{F}_{2}$. Our main contributions include: 1. In STOC 2020, CHHLZ introduced a new technique to prove c…
View article: Quasirandom groups enjoy interleaved mixing
Quasirandom groups enjoy interleaved mixing Open
Let $G$ be a group such that any non-trivial representation has dimension at least $d$. Let $X=(X_{1},X_{2},\ldots,X_{t})$ and $Y=(Y_{1},Y_{2},\ldots,Y_{t})$ be distributions over $G^{t}$. Suppose that $X$ is independent from $Y$. We show …
View article: Mixing in Non-Quasirandom Groups
Mixing in Non-Quasirandom Groups Open
We initiate a systematic study of mixing in non-quasirandom groups. Let A and B be two independent, high-entropy distributions over a group G. We show that the product distribution AB is statistically close to the distribution F(AB) for se…
View article: On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization
On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization Open
The hardness vs. randomness paradigm aims to explicitly construct pseudorandom generators G:{0,1}^r → {0,1}^m that fool circuits of size m, assuming the existence of explicit hard functions. A "high-end PRG" with seed length r = O(log m) (…
View article: Affine Extractors and AC0-Parity
Affine Extractors and AC0-Parity Open
We study a simple and general template for constructing affine extractors by composing a linear transformation with resilient functions. Using this we show that good affine extractors can be computed by non-explicit circuits of various typ…
View article: Fourier growth of structured $\mathbb{F}_2$-polynomials and applications
Fourier growth of structured $\mathbb{F}_2$-polynomials and applications Open
We analyze the Fourier growth, i.e. the $L_1$ Fourier weight at level $k$ (denoted $L_{1,k}$), of various well-studied classes of "structured" $\mathbb{F}_2$-polynomials. This study is motivated by applications in pseudorandomness, in part…
View article: Fourier Growth of Structured 𝔽₂-Polynomials and Applications
Fourier Growth of Structured 𝔽₂-Polynomials and Applications Open
We analyze the Fourier growth, i.e. the L₁ Fourier weight at level k (denoted L_{1,k}), of various well-studied classes of "structured" m F₂-polynomials. This study is motivated by applications in pseudorandomness, in particular recent res…
View article: Fourier conjectures, correlation bounds, and Majority *
Fourier conjectures, correlation bounds, and Majority * Open
Recently several conjectures were made regarding the Fourier spectrum of low-degree polynomials. We show that these conjectures imply new correlation bounds for functions related to Majority. Then we prove several new results on correlatio…
View article: How to Store a Random Walk
How to Store a Random Walk Open
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,\ldots, X_n) \sim μ$ which are \emph{correlated} ($H_μ(\overline…
View article: Bounded Independence versus Symmetric Tests
Bounded Independence versus Symmetric Tests Open
For a test T ⊆ {0, 1} n , define k * ( T ) to be the maximum k such that there exists a k -wise uniform distribution over {0, 1} n whose support is a subset of T . For H t = { x ∈ {0, 1} n : | ∑ i x i − n /2| ≤ t }, we prove k * ( H t ) = …
View article: Constant-Error Pseudorandomness Proofs from Hardness Require Majority
Constant-Error Pseudorandomness Proofs from Hardness Require Majority Open
Research in the 1980s and 1990s showed how to construct a pseudorandom generator from a function that is hard to compute on more than 99% of the inputs. A more recent line of works showed, however, that if the generator has small error, th…
View article: The Coin Problem for Product Tests
The Coin Problem for Product Tests Open
Let X m,ε be the distribution over m bits X 1 ,…, X m where the X i are independent and each X i equals 1 with probability (1− ε )/2 and 0 with probability (1 − ε )/2. We consider the smallest value ε * of ε such that the distributions X m…
View article: Interleaved group products
Interleaved group products Open
Let $G$ be the special linear group $\mathrm{SL}(2,q)$. We show that if $(a_1,\ldots,a_t)$ and $(b_1,\ldots,b_t)$ are sampled uniformly from large subsets $A$ and $B$ of $G^t$ then their interleaved product $a_1 b_1 a_2 b_2 \cdots a_t b_t$…
View article: Revisiting Frequency Moment Estimation in Random Order Streams
Revisiting Frequency Moment Estimation in Random Order Streams Open
We revisit one of the classic problems in the data stream literature, namely, that of estimating the frequency moments F_p for 0 < p < 2 of an underlying n-dimensional vector presented as a sequence of additive updates in a stream. It is w…
View article: Bounded Independence vs. Moduli
Bounded Independence vs. Moduli Open
Let k = k(n) be the largest integer such that there exists a k-wise uniform distribution over {0,1}^n that is supported on the set S_m := {x in {0,1}^n: sum_i x_i equiv 0 mod m}, where m is any integer. We show that Omega(n/m^2 log m) <= k…