Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Emanuele Viola:

TR22-148 | 11th November 2022
Peter Ivanov, Raghu Meka, Emanuele Viola

Efficient resilient functions

An $n$-bit boolean function is resilient to coalitions of size $q$
if no fixed set of $q$ bits is likely to influence the value of the
function when the other $n-q$ bits are chosen uniformly at random,
even though the function is nearly balanced. We construct explicit
functions resilient to ... more >>>

TR22-142 | 3rd November 2022
Emanuele Viola

Correlation bounds against polynomials

A survey on correlation bounds against polynomials.

more >>>

TR22-132 | 18th September 2022
Harm Derksen, Emanuele Viola

Fooling polynomials using invariant theory

We revisit the problem of constructing explicit pseudorandom generators
that fool with error $\epsilon$ degree-$d$ polynomials in $n$ variables
over the field $F_q$, in the case of large $q$. Previous constructions
either have seed length at least $2^{d}\log q$, and thus are only non-trivial
when the degree is less than ... more >>>

TR22-092 | 2nd July 2022
Peter Ivanov, Liam Pavlovic, Emanuele Viola

On correlation bounds against polynomials

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 correlation bounds. Using their technique they established new correlation bounds for low-degree polynomials. They conjectured that their ... more >>>

TR22-091 | 2nd July 2022
Harm Derksen, Emanuele Viola

Quasirandom groups enjoy interleaved mixing

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 that for any $g\in G$ we have
\left|\mathbb{P}[X_{1}Y_{1}X_{2}Y_{2}\cdots X_{t}Y_{t}=g]-1/|G|\right|\le\frac{|G|^{2t-1}}{d^{t-1}}\sqrt{\mathbb{E}_{h\in G^{t}}X(h)^{2}}\sqrt{\mathbb{E}_{h\in G^{t}}Y(h)^{2}}.
Our results generalize, improve, and ... more >>>

TR21-153 | 9th November 2021
Ronen Shaltiel, Emanuele Viola

On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization

Revisions: 1

The hardness vs.~randomness paradigm aims to explicitly construct pseudorandom generators $G:\{0,1\}^r \to \{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)$ (implying BPP=P) was achieved in a seminal work of Impagliazzo and Wigderson (STOC 1997), assuming \textsc{the ... more >>>

TR21-137 | 14th September 2021
Xuangui Huang, Peter Ivanov, Emanuele Viola

Affine extractors and AC0-Parity

Revisions: 1

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 types, including AC0-Xor circuits: AC0 circuits with a layer of parity gates at the input. ... more >>>

TR21-110 | 22nd July 2021
Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco Servedio, Emanuele Viola

Fourier growth of structured $\mathbb{F}_2$-polynomials and applications

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 particular recent results and conjectures due to [CHHL19,CHLT19,CGLSS20] which show that upper bounds on Fourier growth (even at ... more >>>

TR21-073 | 3rd June 2021
Emanuele Viola

Lower bounds for samplers and data structures via the cell-probe separator

Revisions: 4

Suppose that a distribution $S$ can be approximately sampled by an
efficient cell-probe algorithm. It is shown to be possible to restrict
the input to the algorithm so that its output distribution is still
not too far from $S$, and at the same time many output coordinates
are almost pairwise ... more >>>

TR21-017 | 19th February 2021
Timothy Gowers, Emanuele Viola

Mixing in non-quasirandom groups

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 several choices of $G$ and
$F$, including:

(1) $G$ is the affine ... more >>>

TR20-193 | 29th December 2020
Xuangui Huang, Emanuele Viola

Average-case rigidity lower bounds

Revisions: 1

It is shown that there exists $f : \{0,1\}^{n/2} \times \{0,1\}^{n/2} \to \{0,1\}$ in E$^\mathbf{NP}$ such that for every $2^{n/2} \times 2^{n/2}$ matrix $M$ of rank $\le \rho$ we have $\P_{x,y}[f(x,y)\ne M_{x,y}] \ge 1/2-2^{-\Omega(k)}$, where $k \leq \Theta(\sqrt{n})$ and $\log \rho \leq \delta n/k(\log n + k)$ for a sufficiently ... more >>>

TR20-175 | 24th November 2020
Emanuele Viola

Fourier conjectures, correlation bounds, and Majority

Revisions: 2

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 correlation bounds which aim to, but don't, resolve the conjectures. In particular, we prove several new results ... more >>>

TR20-015 | 18th February 2020
Emanuele Viola

New lower bounds for probabilistic degree and AC0 with parity gates

Revisions: 5

We prove new lower bounds for computing some functions $f:\{0,1\}^{n}\to\{0,1\}$ in $E^{NP}$ by polynomials modulo $2$, constant-depth circuits with parity gates ($AC^{0}[\oplus]$), and related classes. Results include:

(1) $\Omega(n/\log^{2}n)$ lower bounds probabilistic degree. This is optimal up to a factor $O(\log^{2}n)$. The previous best lower bound was $\Omega(\sqrt{n})$ proved in ... more >>>

TR19-175 | 4th December 2019
Emanuele Viola

Matching Smolensky's correlation bound with majority

We show that there are degree-$d$ polynomials over $\mathbb{F}_{2}$ with
correlation $\Omega(d/\sqrt{n})$ with the majority function on $n$
bits. This matches the $O(d/\sqrt{n})$ bound by Smolensky.

more >>>

TR19-085 | 7th June 2019
Xuangui Huang, Emanuele Viola

Approximate Degree-Weight and Indistinguishability

Revisions: 2

We prove that the Or function on $n$ bits can be point-wise approximated with error $\eps$ by a polynomial of degree $O(k)$ and weight $2^{O(n \log (1/\eps)/k)}$, for any $k \geq \sqrt{n \log 1/\eps}$. This result is tight for all $k$. Previous results were either not tight or had $\eps ... more >>>

TR19-051 | 9th April 2019
Emanuele Viola

Pseudorandom bits and lower bounds for randomized Turing machines

We exhibit a pseudorandom generator with nearly quadratic stretch for randomized Turing machines, which have a one-way random tape and a two-way work tape. This is the first generator for this model. Its stretch is essentially the best possible given current lower bounds. We use the generator to prove a ... more >>>

TR18-209 | 8th December 2018
Emanuele Viola

AC0 unpredictability

We prove that for every distribution $D$ on $n$ bits with Shannon
entropy $\ge n-a$ at most $O(2^{d}a\log^{d+1}g)/\gamma{}^{5}$ of
the bits $D_{i}$ can be predicted with advantage $\gamma$ by an
AC$^{0}$ circuit of size $g$ and depth $d$ that is a function of
all the bits of $D$ except $D_{i}$. ... more >>>

TR18-186 | 6th November 2018
Emanuele Viola

Lower bounds for data structures with space close to maximum imply circuit lower bounds

Revisions: 1

Let $f:\{0,1\}^{n}\to\{0,1\}^{m}$ be a function computable by a circuit with
unbounded fan-in, arbitrary gates, $w$ wires and depth $d$. With
a very simple argument we show that the $m$-query problem corresponding
to $f$ has data structures with space $s=n+r$ and time $(w/r)^{d}$,
for any $r$. As a consequence, in the ... more >>>

TR18-133 | 26th July 2018
Emanuele Viola

Constant-error pseudorandomness proofs from hardness require majority

Revisions: 1

Research in the 80's and 90's 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, then the proof of correctness cannot
be ... more >>>

TR18-061 | 6th April 2018
Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola

Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs

Revisions: 5

We study how well can $q$-query decision trees distinguish between the
following two distributions: (i) $R=(R_1,\ldots,R_N)$ that are i.i.d.
variables, (ii) $X=(R|R \in A)$ where $A$ is an event s.t. $\Pr[R \in A] \ge
2^{-a}$. We prove two lemmas:

- Forbidden-set lemma: There exists $B \subseteq [N]$ of
size ... more >>>

TR18-060 | 6th April 2018
Emanuele Viola

Sampling lower bounds: boolean average-case and permutations

Revisions: 1

We show that for every small AC$^{0}$ circuit
$C:\{0,1\}^{\ell}\to\{0,1\}^{m}$ there exists a multiset $S$ of
$2^{m-m^{\Omega(1)}}$ restrictions that preserve the output distribution of
$C$ and moreover \emph{polarize min-entropy: }the restriction of $C$ to
any $r\in S$ either is constant or has polynomial min-entropy. This
structural result is then applied to ... more >>>

TR17-167 | 3rd November 2017
Chin Ho Lee, Emanuele Viola

More on bounded independence plus noise: Pseudorandom generators for read-once polynomials

Revisions: 1

We construct pseudorandom generators with improved seed length for
several classes of tests. First we consider the class of read-once
polynomials over GF(2) in $m$ variables. For error $\e$ we obtain seed
length $\tilde O (\log(m/\e)) \log(1/\e)$, where $\tilde O$ hides lower-order
terms. This is optimal up to the factor ... more >>>

TR17-166 | 3rd November 2017
Emanuele Viola

A sampling lower bound for permutations

A map $f:[n]^{\ell}\to[n]^{n}$ has locality $d$ if each output symbol
in $[n]=\{1,2,\ldots,n\}$ depends only on $d$ of the $\ell$ input
symbols in $[n]$. We show that the output distribution of a $d$-local
map has statistical distance at least $1-2\cdot\exp(-n/\log^{c^{d}}n)$
from a uniform permutation of $[n]$. This seems to be the ... more >>>

TR17-090 | 15th May 2017
Chin Ho Lee, Emanuele Viola

The coin problem for product tests

Let $X_{m, \eps}$ be the distribution over $m$ bits $(X_1, \ldots, X_m)$
where the $X_i$ are independent and each $X_i$ equals $1$ with
probability $(1+\eps)/2$ and $0$ with probability $(1-\eps)/2$. We
consider the smallest value $\eps^*$ of $\eps$ such that the distributions
$X_{m,\eps}$ and $X_{m,0}$ can be distinguished with constant
more >>>

TR16-169 | 3rd November 2016
Elad Haramaty, Chin Ho Lee, Emanuele Viola

Bounded independence plus noise fools products

Let $D$ be a $b$-wise independent distribution over
$\{0,1\}^m$. Let $E$ be the ``noise'' distribution over
$\{0,1\}^m$ where the bits are independent and each bit is 1
with probability $\eta/2$. We study which tests $f \colon
\{0,1\}^m \to [-1,1]$ are $\e$-fooled by $D+E$, i.e.,
$|\E[f(D+E)] - \E[f(U)]| \le \e$ where ... more >>>

TR16-129 | 16th August 2016
Emanuele Viola, Avi Wigderson

Local Expanders

Revisions: 1

Abstract A map $f:{0,1}^{n}\to {0,1}^{n}$ has locality t if every output bit of f depends only on t input bits. Arora, Steurer, and Wigderson (2009) ask if there exist bounded-degree expander graphs on $2^{n}$ nodes such that the neighbors of a node $x\in {0,1}^{n}$ can be computed by maps of ... more >>>

TR16-127 | 12th August 2016
Timothy Gowers, Emanuele Viola

The multiparty communication complexity of interleaved group products

Party $A_i$ of $k$ parties $A_1,\dots,A_k$ receives on
its forehead a $t$-tuple $(a_{i1},\dots,a_{it})$ of
elements from the group $G=\text{SL}(2,q)$. The parties
are promised that the interleaved product $a_{11}\dots
a_{k1}a_{12}\dots a_{k2}\dots a_{1t}\dots a_{kt}$ is
equal either to the identity $e$ or to some other fixed
element $g\in G$. Their goal is ... more >>>

TR16-102 | 4th July 2016
Ravi Boppana, Johan HÃ¥stad, Chin Ho Lee, Emanuele Viola

Bounded independence vs. moduli

Revisions: 1

Let $k=k(n)$ be the largest integer such that there
exists a $k$-wise uniform distribution over $\zo^n$ that
is supported on the set $S_m := \{x \in \zo^n : \sum_i
x_i \equiv 0 \bmod m\}$, where $m$ is any integer. We
show that $\Omega(n/m^2 \log m) \le k \le 2n/m + ... more >>>

TR15-205 | 15th December 2015
Emanuele Viola

Quadratic maps are hard to sample

This note proves the existence of a quadratic GF(2) map
$p : \{0,1\}^n \to \{0,1\}$ such that no constant-depth circuit
of size $\poly(n)$ can sample the distribution $(u,p(u))$
for uniform $u$.

more >>>

TR15-182 | 13th November 2015
Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson

Bounded Indistinguishability and the Complexity of Recovering Secrets

Revisions: 1

We say that a function $f\colon \Sigma^n \to \{0, 1\}$ is $\epsilon$-fooled by $k$-wise indistinguishability if $f$ cannot distinguish with advantage $\epsilon$ between any two distributions $\mu$ and $\nu$ over $\Sigma^n$ whose projections to any $k$ symbols are identical. We study the class of functions $f$ that are fooled by ... more >>>

TR15-044 | 2nd April 2015
Timothy Gowers, Emanuele Viola

The communication complexity of interleaved group products

Revisions: 1

Alice receives a tuple $(a_1,\ldots,a_t)$ of $t$ elements
from the group $G = \text{SL}(2,q)$. Bob similarly
receives a tuple $(b_1,\ldots,b_t)$. They are promised
that the interleaved product $\prod_{i \le t} a_i b_i$
equals to either $g$ and $h$, for two fixed elements $g,h
\in G$. Their task is to decide ... more >>>

TR15-005 | 5th January 2015
Chin Ho Lee, Emanuele Viola

Some limitations of the sum of small-bias distributions

Revisions: 1

We exhibit $\epsilon$-biased distributions $D$
on $n$ bits and functions $f\colon \{0,1\}^n
\to \{0,1\}$ such that the xor of two independent
copies ($D+D$) does not fool $f$, for any of the
following choices:

1. $\epsilon = 2^{-\Omega(n)}$ and $f$ is in P/poly;

2. $\epsilon = 2^{-\Omega(n/\log n)}$ and $f$ is ... more >>>

TR15-003 | 3rd January 2015
Oded Goldreich, Emanuele Viola, Avi Wigderson

On Randomness Extraction in AC0

We consider randomness extraction by AC0 circuits. The main parameter, $n$, is the length of the source, and all other parameters are functions of it. The additional extraction parameters are the min-entropy bound $k=k(n)$, the seed length $r=r(n)$, the output length $m=m(n)$, and the (output) deviation bound $\epsilon=\epsilon(n)$.

For $k ... more >>>

TR14-037 | 21st March 2014
Hamidreza Jahanjou, Eric Miles, Emanuele Viola

Succinct and explicit circuits for sorting and connectivity

We study which functions can be computed by efficient circuits whose gate connections are very easy to compute. We give quasilinear-size circuits for sorting whose connections can be computed by decision trees with depth logarithmic in the length of the gate description. We also show that NL has NC$^2$ circuits ... more >>>

TR14-017 | 9th February 2014
Eli Ben-Sasson, Emanuele Viola

Short PCPs with projection queries

We construct a PCP for NTIME(2$^n$) with constant
soundness, $2^n \poly(n)$ proof length, and $\poly(n)$
queries where the verifier's computation is simple: the
queries are a projection of the input randomness, and the
computation on the prover's answers is a 3CNF. The
previous upper bound for these two computations was
more >>>

TR13-119 | 2nd September 2013
Emanuele Viola

Challenges in computational lower bounds

We draw two incomplete, biased maps of challenges in
computational complexity lower bounds. Our aim is to put
these challenges in perspective, and to present some
connections which do not seem widely known.

more >>>

TR13-099 | 6th July 2013
Hamidreza Jahanjou, Eric Miles, Emanuele Viola

Local reductions

Revisions: 3

We reduce non-deterministic time $T \ge 2^n$ to a 3SAT
instance $\phi$ of size $|\phi| = T \cdot \log^{O(1)} T$
such that there is an explicit circuit $C$ that on input
an index $i$ of $\log |\phi|$ bits outputs the $i$th
clause, and each output bit of $C$ depends on ... more >>>

TR13-009 | 9th January 2013
Zahra Jafargholi, Emanuele Viola

3SUM, 3XOR, Triangles

Revisions: 1

We show that if one can solve 3SUM on a set of size $n$
in time $n^{1+\epsilon}$ then one can list $t$ triangles in a
graph with $m$ edges in time $\tilde
O(m^{1+\epsilon}t^{1/3+\epsilon'})$ for any $\epsilon' > 0$. This is a
reversal of Patrascu's reduction from 3SUM to
listing triangles ... more >>>

TR13-003 | 2nd January 2013
Eric Miles, Emanuele Viola

Shielding circuits with groups

Revisions: 2

We show how to efficiently compile any given circuit $C$
into a leakage-resistant circuit $\widehat{C}$ such that any
function on the wires of $\widehat{C}$ that leaks information
during a computation $\widehat{C}(x)$ yields advantage in
computing the product of $|\widehat{C}|^{\Omega(1)}$ elements
of the alternating group $A_u$. In combination with new
compression ... more >>>

TR12-160 | 20th November 2012
Frederic Green, Daniel Kreymer, Emanuele Viola

Block-symmetric polynomials correlate with parity better than symmetric

We show that degree-$d$ block-symmetric polynomials in
$n$ variables modulo any odd $p$ correlate with parity
exponentially better than degree-$d$ symmetric
polynomials, if $n \ge c d^2 \log d$ and $d \in [0.995
\cdot p^t - 1,p^t)$ for some $t \ge 1$. For these
infinitely many degrees, our result ... more >>>

TR12-144 | 6th November 2012
Rocco Servedio, Emanuele Viola

On a special case of rigidity

We highlight the special case of Valiant's rigidity
problem in which the low-rank matrices are truth-tables
of sparse polynomials. We show that progress on this
special case entails that Inner Product is not computable
by small $\acz$ circuits with one layer of parity gates
close to the inputs. We then ... more >>>

TR12-134 | 22nd October 2012
Alexander Razborov, Emanuele Viola

Real Advantage

Revisions: 1

We highlight the challenge of proving correlation bounds
between boolean functions and integer-valued polynomials,
where any non-boolean output counts against correlation.

We prove that integer-valued polynomials of degree $\frac 12
\log_2 \log_2 n$ have zero correlation with parity. Such a
result is false for modular and threshold polynomials.
Its proof ... more >>>

TR12-125 | 2nd October 2012
Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola

From RAM to SAT

Revisions: 1

Common presentations of the NP-completeness of SAT suffer
from two drawbacks which hinder the scope of this
flagship result. First, they do not apply to machines
equipped with random-access memory, also known as
direct-access memory, even though this feature is
critical in basic algorithms. Second, they incur a
quadratic blow-up ... more >>>

TR12-047 | 24th April 2012
Emanuele Viola

Extractors for Turing-machine sources

We obtain the first deterministic randomness extractors
for $n$-bit sources with min-entropy $\ge n^{1-\alpha}$
generated (or sampled) by single-tape Turing machines
running in time $n^{2-16 \alpha}$, for all sufficiently
small $\alpha > 0$. We also show that such machines
cannot sample a uniform $n$-bit input to the Inner
Product function ... more >>>

TR12-019 | 2nd March 2012
Eric Miles, Emanuele Viola

On the complexity of constructing pseudorandom functions (especially when they don't exist)

We study the complexity of black-box constructions of
pseudorandom functions (PRF) from one-way functions (OWF)
that are secure against non-uniform adversaries. We show
that if OWF do not exist, then given as an oracle any
(inefficient) hard-to-invert function, one can compute a
PRF in polynomial time with only $k(n)$ oracle ... more >>>

TR11-152 | 12th November 2011
Emanuele Viola

The communication complexity of addition

Suppose each of $k \le n^{o(1)}$ players holds an $n$-bit number $x_i$ in its hand. The players wish to determine if $\sum_{i \le k} x_i = s$. We give a public-coin protocol with error $1\%$ and communication $O(k \lg k)$. The communication bound is independent of $n$, and for $k ... more >>>

TR11-150 | 4th November 2011
Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates

We bound the minimum number $w$ of wires needed to compute any (asymptotically good) error-correcting code
$C:\{0,1\}^{\Omega(n)} \to \{0,1\}^n$ with minimum distance $\Omega(n)$,
using unbounded fan-in circuits of depth $d$ with arbitrary gates. Our main results are:

(1) If $d=2$ then $w = \Theta(n ({\log n/ \log \log n})^2)$.

(2) ... more >>>

TR11-113 | 11th August 2011
Emanuele Viola

Reducing 3XOR to listing triangles, an exposition

The 3SUM problem asks if there are three integers $a,b,c$ summing to $0$ in a given set of $n$ integers of magnitude poly($n$). Patrascu (STOC '10) reduces solving 3SUM in time $n^{2-\Omega(1)}$ to listing $m$ triangles in a graph with $m$ edges in time $m^{4/3-\Omega(1)}$.
In this note we present ... more >>>

TR11-076 | 7th May 2011
Eric Miles, Emanuele Viola

The Advanced Encryption Standard, Candidate Pseudorandom Functions, and Natural Proofs

Revisions: 1

We put forth several simple candidate pseudorandom functions f_k : {0,1}^n -> {0,1} with security (a.k.a. hardness) 2^n that are inspired by the AES block-cipher by Daemen and Rijmen (2000). The functions are computable more efficiently, and use a shorter key (a.k.a. seed) than previous
constructions. In particular, we ... more >>>

TR11-056 | 14th April 2011
Emanuele Viola

Extractors for circuit sources

We obtain the first deterministic extractors for sources generated (or sampled) by small circuits of bounded depth. Our main results are:

(1) We extract $k (k/nd)^{O(1)}$ bits with exponentially small error from $n$-bit sources of min-entropy $k$ that are generated by functions $f : \{0,1\}^\ell \to \{0,1\}^n$ where each output ... more >>>

TR11-039 | 19th March 2011
Frederic Green, Daniel Kreymer, Emanuele Viola

In Brute-Force Search of Correlation Bounds for Polynomials

We report on some initial results of a brute-force search for determining the maximum correlation between degree-$d$ polynomials modulo $p$ and the $n$-bit mod $q$ function. For various settings of the parameters $n,d,p,$ and $q$, our results indicate that symmetric polynomials yield the maximum correlation. This contrasts with the previously-analyzed ... more >>>

TR10-186 | 2nd December 2010
Bill Fefferman, Ronen Shaltiel, Chris Umans, Emanuele Viola

On beating the hybrid argument

The {\em hybrid argument}
allows one to relate
the {\em distinguishability} of a distribution (from
uniform) to the {\em
predictability} of individual bits given a prefix. The
argument incurs a loss of a factor $k$ equal to the
bit-length of the
distributions: $\epsilon$-distinguishability implies only
$\epsilon/k$-predictability. ... more >>>

TR10-175 | 14th November 2010
Emanuele Viola

Randomness buys depth for approximate counting

Revisions: 1

We show that the promise problem of distinguishing $n$-bit strings of hamming weight $\ge 1/2 + \Omega(1/\log^{d-1} n)$ from strings of weight $\le 1/2 - \Omega(1/\log^{d-1} n)$ can be solved by explicit, randomized (unbounded-fan-in) poly(n)-size depth-$d$ circuits with error $\le 1/3$, but cannot be solved by deterministic poly(n)-size depth-$(d+1)$ circuits, ... more >>>

TR10-115 | 17th July 2010
Shachar Lovett, Emanuele Viola

Bounded-depth circuits cannot sample good codes

We study a variant of the classical circuit-lower-bound problems: proving lower bounds for sampling distributions given random bits. We prove a lower bound of $1-1/n^{\Omega(1)}$ on the statistical distance between (i) the output distribution of any small constant-depth (a.k.a.~$\mathrm{AC}^0$) circuit $f : \{0,1\}^{\mathrm{poly}(n)} \to \{0,1\}^n$, and (ii) the uniform distribution ... more >>>

TR09-114 | 13th November 2009
Emanuele Viola

Are all distributions easy?

Complexity theory typically studies the complexity of computing a function $h(x) : \{0,1\}^n \to \{0,1\}^m$ of a given input $x$. We advocate the study of the complexity of generating the distribution $h(x)$ for uniform $x$, given random bits.

Our main results are:

\item There are explicit $AC^0$ circuits of ... more >>>

TR09-054 | 7th June 2009
Emanuele Viola, Emanuele Viola

Cell-Probe Lower Bounds for Prefix Sums

We prove that to store n bits x so that each
prefix-sum query Sum(i) := sum_{k < i} x_k can be answered
by non-adaptively probing q cells of log n bits, one needs
memory > n + n/log^{O(q)} n.

Our bound matches a recent upper bound of n +
n/log^{Omega(q)} ... more >>>

TR09-054 | 7th June 2009
Emanuele Viola, Emanuele Viola

Cell-Probe Lower Bounds for Prefix Sums

We prove that to store n bits x so that each
prefix-sum query Sum(i) := sum_{k < i} x_k can be answered
by non-adaptively probing q cells of log n bits, one needs
memory > n + n/log^{O(q)} n.

Our bound matches a recent upper bound of n +
n/log^{Omega(q)} ... more >>>

TR09-016 | 21st February 2009
Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola

Bounded Independence Fools Halfspaces

We show that any distribution on {-1,1}^n that is k-wise independent fools any halfspace h with error \eps for k = O(\log^2(1/\eps)/\eps^2). Up to logarithmic factors, our result matches a lower bound by Benjamini, Gurel-Gurevich, and Peled (2007) showing that k = \Omega(1/(\eps^2 \cdot \log(1/\eps))). Using standard constructions of k-wise ... more >>>

TR09-005 | 7th December 2008
Emanuele Viola

Bit-Probe Lower Bounds for Succinct Data Structures

We prove lower bounds on the redundancy necessary to
represent a set $S$ of objects using a number of bits
close to the information-theoretic minimum $\log_2 |S|$,
while answering various queries by probing few bits. Our
main results are:

\item To represent $n$ ternary values $t \in
\zot^n$ in ... more >>>

TR07-132 | 8th December 2007
Emanuele Viola

The sum of d small-bias generators fools polynomials of degree d

We prove that the sum of $d$ small-bias generators $L
: \F^s \to \F^n$ fools degree-$d$ polynomials in $n$
variables over a prime field $\F$, for any fixed
degree $d$ and field $\F$, including $\F = \F_2 =

Our result improves on both the work by Bogdanov and
Viola ... more >>>

TR07-130 | 3rd December 2007
Ronen Shaltiel, Emanuele Viola

Hardness amplification proofs require majority

Hardness amplification is the fundamental task of
converting a $\delta$-hard function $f : {0,1}^n ->
{0,1}$ into a $(1/2-\eps)$-hard function $Amp(f)$,
where $f$ is $\gamma$-hard if small circuits fail to
compute $f$ on at least a $\gamma$ fraction of the
inputs. Typically, $\eps,\delta$ are small (and
$\delta=2^{-k}$ captures the case ... more >>>

TR07-103 | 28th September 2007
Emanuele Viola

Selected Results in Additive Combinatorics: An Exposition

We give a self-contained exposition of selected results in additive
combinatorics over the group {0,1}^n. In particular, we prove the
celebrated theorems known as the Balog-Szemeredi-Gowers theorem ('94 and '98) and
Freiman-Ruzsa theorem ('73 and '99), leading to the remarkable result
by Samorodnitsky ('07) that linear transformations are efficiently ... more >>>

TR07-081 | 10th August 2007
Andrej Bogdanov, Emanuele Viola

Pseudorandom bits for polynomials

We present a new approach to constructing pseudorandom generators that fool low-degree polynomials over finite fields, based on the Gowers norm. Using this approach, we obtain the following main constructions of explicitly computable generators $G : \F^s \to \F^n$ that fool polynomials over a prime field $\F$:
\item a ... more >>>

TR07-079 | 11th August 2007
Emanuele Viola, Avi Wigderson

One-way multi-party communication lower bound for pointer jumping with applications

In this paper we study the one-way multi-party communication model,
in which every party speaks exactly once in its turn. For every
fixed $k$, we prove a tight lower bound of
$\Omega{n^{1/(k-1)}}$ on the probabilistic communication
complexity of pointer jumping in a $k$-layered tree, where the
pointers of the $i$-th ... more >>>

TR06-097 | 9th August 2006
Emanuele Viola

New correlation bounds for GF(2) polynomials using Gowers uniformity

We study the correlation between low-degree GF(2) polynomials p and explicit functions. Our main results are the following:

(I) We prove that the Mod_m unction on n bits has correlation at most exp(-Omega(n/4^d)) with any GF(2) polynomial of degree d, for any fixed odd integer m. This improves on the ... more >>>

TR05-137 | 21st November 2005
Emanuele Viola

On Probabilistic Time versus Alternating Time

We prove several new results regarding the relationship between probabilistic time, BPTime(t), and alternating time, \Sigma_{O(1)} Time(t). Our main results are the following:

1) We prove that BPTime(t) \subseteq \Sigma_3 Time(t polylog(t)). Previous results show that BPTime(t) \subseteq \Sigma_2 Time(t^2 log t) (Sipser and Gacs, STOC '83; Lautemann, IPL '83) ... more >>>

TR05-087 | 9th August 2005
Alexander Healy, Emanuele Viola

Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two

We study the complexity of arithmetic in finite fields of characteristic two, $\F_{2^n}$.
We concentrate on the following two problems:

Iterated Multiplication: Given $\alpha_1, \alpha_2,..., \alpha_t \in \F_{2^n}$, compute $\alpha_1 \cdot \alpha_2 \cdots \alpha_t \in \F_{2^n}$.

Exponentiation: Given $\alpha \in \F_{2^n}$ and a $t$-bit integer $k$, compute $\alpha^k \in \F_{2^n}$.

... more >>>

TR05-043 | 5th April 2005
Emanuele Viola

Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates

We exhibit an explicitly computable `pseudorandom' generator stretching $l$ bits into $m(l) = l^{\Omega(\log l)}$ bits that look random to constant-depth circuits of size $m(l)$ with $\log m(l)$ arbitrary symmetric gates (e.g. PARITY, MAJORITY). This improves on a generator by Luby, Velickovic and Wigderson (ISTCS '93) that achieves the same ... more >>>

TR04-088 | 12th October 2004
Emanuele Viola, Dan Gutfreund

Fooling Parity Tests with Parity Gates

We study the complexity of computing $k$-wise independent and
$\epsilon$-biased generators $G : \{0,1\}^n \to \{0,1\}^m$.
Specifically, we refer to the complexity of computing $G$ \emph{explicitly}, i.e.
given $x \in \{0,1\}^n$ and $i \in \{0,1\}^{\log m}$, computing the $i$-th output bit of $G(x)$.
Mansour, Nisan and Tiwari (1990) show that ... more >>>

TR04-087 | 13th October 2004
Alexander Healy, Salil Vadhan, Emanuele Viola

Using Nondeterminism to Amplify Hardness

We revisit the problem of hardness amplification in $\NP$, as
recently studied by O'Donnell (STOC `02). We prove that if $\NP$
has a balanced function $f$ such that any circuit of size $s(n)$
fails to compute $f$ on a $1/\poly(n)$ fraction of inputs, then
$\NP$ has a function $f'$ such ... more >>>

TR04-074 | 26th August 2004
Emanuele Viola

On Parallel Pseudorandom Generators

Revisions: 1

We study pseudorandom generator (PRG) constructions $G^f : {0,1}^l \to {0,1}^{l+s}$ from one-way functions $f : {0,1}^n \to {0,1}^m$. We consider PRG constructions of the form $G^f(x) = C(f(q_{1}) \ldots f(q_{poly(n)}))$
where $C$ is a polynomial-size constant depth circuit
and $C$ and the $q$'s are generated from $x$ arbitrarily.
more >>>

TR04-020 | 8th March 2004
Emanuele Viola

The Complexity of Constructing Pseudorandom Generators from Hard Functions

We study the complexity of building
pseudorandom generators (PRGs) from hard functions.

We show that, starting from a function f : {0,1}^l -> {0,1} that
is mildly hard on average, i.e. every circuit of size 2^Omega(l)
fails to compute f on at least a 1/poly(l)
fraction of inputs, we can ... more >>>

ISSN 1433-8092 | Imprint