All reports by Author Emanuele Viola:

__
TR20-015
| 18th February 2020
__

Emanuele Viola#### New lower bounds for probabilistic degree and AC0 with parity gates

Revisions: 2

__
TR19-175
| 4th December 2019
__

Emanuele Viola#### Matching Smolensky's correlation bound with majority

__
TR19-085
| 7th June 2019
__

Xuangui Huang, Emanuele Viola#### Approximate Degree-Weight and Indistinguishability

Revisions: 2

__
TR19-051
| 9th April 2019
__

Emanuele Viola#### Pseudorandom bits and lower bounds for randomized Turing machines

__
TR18-209
| 8th December 2018
__

Emanuele Viola#### AC0 unpredictability

__
TR18-186
| 6th November 2018
__

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

Revisions: 1

__
TR18-133
| 26th July 2018
__

Emanuele Viola#### Constant-error pseudorandomness proofs from hardness require majority

Revisions: 1

__
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

__
TR18-060
| 6th April 2018
__

Emanuele Viola#### Sampling lower bounds: boolean average-case and permutations

Revisions: 1

__
TR17-167
| 3rd November 2017
__

Chin Ho Lee, Emanuele Viola#### More on bounded independence plus noise: Pseudorandom generators for read-once polynomials

Revisions: 1

__
TR17-166
| 3rd November 2017
__

Emanuele Viola#### A sampling lower bound for permutations

__
TR17-090
| 15th May 2017
__

Chin Ho Lee, Emanuele Viola#### The coin problem for product tests

__
TR16-169
| 3rd November 2016
__

Elad Haramaty, Chin Ho Lee, Emanuele Viola#### Bounded independence plus noise fools products

__
TR16-129
| 16th August 2016
__

Emanuele Viola, Avi Wigderson#### Local Expanders

Revisions: 1

__
TR16-127
| 12th August 2016
__

Timothy Gowers, Emanuele Viola#### The multiparty communication complexity of interleaved group products

__
TR16-102
| 4th July 2016
__

Ravi Boppana, Johan HÃ¥stad, Chin Ho Lee, Emanuele Viola#### Bounded independence vs. moduli

Revisions: 1

__
TR15-205
| 15th December 2015
__

Emanuele Viola#### Quadratic maps are hard to sample

__
TR15-182
| 13th November 2015
__

Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson#### Bounded Indistinguishability and the Complexity of Recovering Secrets

Revisions: 1

__
TR15-044
| 2nd April 2015
__

Timothy Gowers, Emanuele Viola#### The communication complexity of interleaved group products

Revisions: 1

__
TR15-005
| 5th January 2015
__

Chin Ho Lee, Emanuele Viola#### Some limitations of the sum of small-bias distributions

Revisions: 1

__
TR15-003
| 3rd January 2015
__

Oded Goldreich, Emanuele Viola, Avi Wigderson#### On Randomness Extraction in AC0

__
TR14-037
| 21st March 2014
__

Hamidreza Jahanjou, Eric Miles, Emanuele Viola#### Succinct and explicit circuits for sorting and connectivity

__
TR14-017
| 9th February 2014
__

Eli Ben-Sasson, Emanuele Viola#### Short PCPs with projection queries

__
TR13-119
| 2nd September 2013
__

Emanuele Viola#### Challenges in computational lower bounds

__
TR13-099
| 6th July 2013
__

Hamidreza Jahanjou, Eric Miles, Emanuele Viola#### Local reductions

Revisions: 3

__
TR13-009
| 9th January 2013
__

Zahra Jafargholi, Emanuele Viola#### 3SUM, 3XOR, Triangles

Revisions: 1

__
TR13-003
| 2nd January 2013
__

Eric Miles, Emanuele Viola#### Shielding circuits with groups

Revisions: 2

__
TR12-160
| 20th November 2012
__

Frederic Green, Daniel Kreymer, Emanuele Viola#### Block-symmetric polynomials correlate with parity better than symmetric

__
TR12-144
| 6th November 2012
__

Rocco Servedio, Emanuele Viola#### On a special case of rigidity

__
TR12-134
| 22nd October 2012
__

Alexander Razborov, Emanuele Viola#### Real Advantage

Revisions: 1

__
TR12-125
| 2nd October 2012
__

Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola#### From RAM to SAT

Revisions: 1

__
TR12-047
| 24th April 2012
__

Emanuele Viola#### Extractors for Turing-machine sources

__
TR12-019
| 2nd March 2012
__

Eric Miles, Emanuele Viola#### On the complexity of constructing pseudorandom functions (especially when they don't exist)

__
TR11-152
| 12th November 2011
__

Emanuele Viola#### The communication complexity of addition

__
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

__
TR11-113
| 11th August 2011
__

Emanuele Viola#### Reducing 3XOR to listing triangles, an exposition

__
TR11-076
| 7th May 2011
__

Eric Miles, Emanuele Viola#### The Advanced Encryption Standard, Candidate Pseudorandom Functions, and Natural Proofs

Revisions: 1

__
TR11-056
| 14th April 2011
__

Emanuele Viola#### Extractors for circuit sources

__
TR11-039
| 19th March 2011
__

Frederic Green, Daniel Kreymer, Emanuele Viola#### In Brute-Force Search of Correlation Bounds for Polynomials

__
TR10-186
| 2nd December 2010
__

Bill Fefferman, Ronen Shaltiel, Chris Umans, Emanuele Viola#### On beating the hybrid argument

__
TR10-175
| 14th November 2010
__

Emanuele Viola#### Randomness buys depth for approximate counting

Revisions: 1

__
TR10-115
| 17th July 2010
__

Shachar Lovett, Emanuele Viola#### Bounded-depth circuits cannot sample good codes

__
TR09-114
| 13th November 2009
__

Emanuele Viola#### Are all distributions easy?

__
TR09-054
| 7th June 2009
__

Emanuele Viola, Emanuele Viola#### Cell-Probe Lower Bounds for Prefix Sums

__
TR09-054
| 7th June 2009
__

Emanuele Viola, Emanuele Viola#### Cell-Probe Lower Bounds for Prefix Sums

__
TR09-016
| 21st February 2009
__

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola#### Bounded Independence Fools Halfspaces

__
TR09-005
| 7th December 2008
__

Emanuele Viola#### Bit-Probe Lower Bounds for Succinct Data Structures

__
TR07-132
| 8th December 2007
__

Emanuele Viola#### The sum of d small-bias generators fools polynomials of degree d

__
TR07-130
| 3rd December 2007
__

Ronen Shaltiel, Emanuele Viola#### Hardness amplification proofs require majority

__
TR07-103
| 28th September 2007
__

Emanuele Viola#### Selected Results in Additive Combinatorics: An Exposition

__
TR07-081
| 10th August 2007
__

Andrej Bogdanov, Emanuele Viola#### Pseudorandom bits for polynomials

__
TR07-079
| 11th August 2007
__

Emanuele Viola, Avi Wigderson#### One-way multi-party communication lower bound for pointer jumping with applications

__
TR06-097
| 9th August 2006
__

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

__
TR05-137
| 21st November 2005
__

Emanuele Viola#### On Probabilistic Time versus Alternating Time

__
TR05-087
| 9th August 2005
__

Alexander Healy, Emanuele Viola#### Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two

__
TR05-043
| 5th April 2005
__

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

__
TR04-088
| 12th October 2004
__

Emanuele Viola, Dan Gutfreund#### Fooling Parity Tests with Parity Gates

__
TR04-087
| 13th October 2004
__

Alexander Healy, Salil Vadhan, Emanuele Viola#### Using Nondeterminism to Amplify Hardness

__
TR04-074
| 26th August 2004
__

Emanuele Viola#### On Parallel Pseudorandom Generators

Revisions: 1

__
TR04-020
| 8th March 2004
__

Emanuele Viola#### The Complexity of Constructing Pseudorandom Generators from Hard Functions

Emanuele Viola

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 >>>

Emanuele Viola

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.

Xuangui Huang, Emanuele Viola

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 >>>

Emanuele Viola

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 >>>

Emanuele Viola

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 >>>

Emanuele Viola

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 >>>

Emanuele Viola

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 >>>

Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola

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 >>>

Emanuele Viola

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 >>>

Chin Ho Lee, Emanuele Viola

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 >>>

Emanuele Viola

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 >>>

Chin Ho Lee, Emanuele Viola

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 >>>

Elad Haramaty, Chin Ho Lee, Emanuele Viola

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 >>>

Emanuele Viola, Avi Wigderson

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 >>>

Timothy Gowers, Emanuele Viola

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 >>>

Ravi Boppana, Johan HÃ¥stad, Chin Ho Lee, Emanuele Viola

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 >>>

Emanuele Viola

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$.

Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson

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 >>>

Timothy Gowers, Emanuele Viola

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 >>>

Chin Ho Lee, Emanuele Viola

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 >>>

Oded Goldreich, Emanuele Viola, Avi Wigderson

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 >>>

Hamidreza Jahanjou, Eric Miles, Emanuele Viola

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 >>>

Eli Ben-Sasson, Emanuele Viola

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 >>>

Emanuele Viola

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.

Hamidreza Jahanjou, Eric Miles, Emanuele Viola

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 >>>

Zahra Jafargholi, Emanuele Viola

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 >>>

Eric Miles, Emanuele Viola

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 >>>

Frederic Green, Daniel Kreymer, Emanuele Viola

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 >>>

Rocco Servedio, Emanuele Viola

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 >>>

Alexander Razborov, Emanuele Viola

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 >>>

Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola

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 >>>

Emanuele Viola

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 >>>

Eric Miles, Emanuele Viola

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 >>>

Emanuele Viola

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 >>>

Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola

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 >>>

Emanuele Viola

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 >>>

Eric Miles, Emanuele Viola

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 >>>

Emanuele Viola

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 >>>

Frederic Green, Daniel Kreymer, Emanuele Viola

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 >>>

Bill Fefferman, Ronen Shaltiel, Chris Umans, Emanuele Viola

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 >>>

Emanuele Viola

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 >>>

Shachar Lovett, Emanuele Viola

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 >>>

Emanuele Viola

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:

\begin{itemize}

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

Emanuele Viola, Emanuele Viola

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 >>>

Emanuele Viola, Emanuele Viola

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 >>>

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola

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 >>>

Emanuele Viola

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:

\begin{itemize}

\item To represent $n$ ternary values $t \in

\zot^n$ in ...
more >>>

Emanuele Viola

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 =

{0,1}$.

Our result improves on both the work by Bogdanov and

Viola ...
more >>>

Ronen Shaltiel, Emanuele Viola

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 >>>

Emanuele Viola

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

the

Freiman-Ruzsa theorem ('73 and '99), leading to the remarkable result

by Samorodnitsky ('07) that linear transformations are efficiently ...
more >>>

Andrej Bogdanov, Emanuele Viola

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$:

\begin{enumerate}

\item a ...
more >>>

Emanuele Viola, Avi Wigderson

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 >>>

Emanuele Viola

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 >>>

Emanuele Viola

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 >>>

Alexander Healy, Emanuele Viola

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 >>>Emanuele Viola

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 >>>

Emanuele Viola, Dan Gutfreund

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 >>>

Alexander Healy, Salil Vadhan, Emanuele Viola

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 >>>

Emanuele Viola

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 >>>

Emanuele Viola

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 >>>