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

Arkadev Chattopadhyay

Let m,q > 1 be two integers that are co-prime and A be any subset of Z_m. Let P be any multi-linear polynomial of degree d in n variables over Z_m. We show that the MOD_q boolean function on n variables has correlation at most exp(-\Omega(n/(m2^{m-1})^d)) with the boolean function ... more >>>

Prahladh Harsha, Rahul Jain, David McAllester, Jaikumar Radhakrishnan

We examine the communication required for generating random variables

remotely. One party Alice will be given a distribution D, and she

has to send a message to Bob, who is then required to generate a

value with distribution exactly D. Alice and Bob are allowed

to share random bits generated ...
more >>>

Arkadev Chattopadhyay

We develop a new technique of proving lower bounds for the randomized communication complexity of boolean functions in the multiparty 'Number on the Forehead' model. Our method is based on the notion of voting polynomial degree of functions and extends the Degree-Discrepancy Lemma in the recent work of Sherstov (STOC'07). ... 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 >>>

Arkadev Chattopadhyay, Rahul Santhanam

We formulate a new connection between instance compressibility \cite{Harnik-Naor10}), where the compressor uses circuits from a class $\C$, and correlation with

circuits in $\C$. We use this connection to prove the first lower bounds

on general probabilistic multi-round instance compression. We show that there

is no

probabilistic multi-round ...
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 >>>

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

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.

Abhishek Bhowmick, Shachar Lovett

The problem of constructing explicit functions which cannot be approximated by low degree polynomials has been extensively studied in computational complexity, motivated by applications in circuit lower bounds, pseudo-randomness, constructions of Ramsey graphs and locally decodable codes. Still, most of the known lower bounds become trivial for polynomials of ...
more >>>

Shiteng Chen, Periklis Papakonstantinou

We show that for any coprime $m,r$ there is a circuit of the form $\text{MOD}_m\circ \text{AND}_{d(n)}$ whose correlation with $\text{MOD}_r$ is at least $2^{-O\left( \frac{n}{d(n)} \right) }$. This is the first correlation lower bound for arbitrary $m,r$, whereas previously lower bounds were known for prime $m$. Our motivation is the ... more >>>

Alexander Kulikov, Vladimir Podolskii

We study the following computational problem: for which values of $k$, the majority of $n$ bits $\text{MAJ}_n$ can be computed with a depth two formula whose each gate computes a majority function of at most $k$ bits? The corresponding computational model is denoted by $\text{MAJ}_k \circ \text{MAJ}_k$. We observe that ... more >>>

Alexander Golovnev, Alexander Kulikov

The best known circuit lower bounds against unrestricted circuits remained around $3n$ for several decades. Moreover, the only known technique for proving lower bounds in this model, gate elimination, is inherently limited to proving lower bounds of less than $5n$. In this work, we suggest a first non-gate-elimination approach for ... more >>>