Luca Trevisan

We show that Yao's XOR Lemma, and its essentially equivalent

rephrasing as a Direct Product Lemma, can be

re-interpreted as a way of obtaining error-correcting

codes with good list-decoding algorithms from error-correcting

codes having weak unique-decoding algorithms. To get codes

with good rate and efficient list decoding algorithms

one needs ...
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 >>>

Anup Rao

A construction of Bourgain gave the first 2-source

extractor to break the min-entropy rate 1/2 barrier. In this note,

we write an exposition of his result, giving a high level way to view

his extractor construction.

We also include a proof of a generalization of Vazirani's XOR lemma

that seems ...
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 >>>

Falk Unger

We prove a simple concentration inequality, which is an extension of the Chernoff bound and Hoeffding's inequality for binary random variables. Instead of assuming independence of the variables we use a slightly weaker condition, namely bounds on the co-moments.

This inequality allows us to simplify and strengthen several known ... more >>>

Uma Girish, Ran Raz, Wei Zhan

The Forrelation problem, first introduced by Aaronson [AA10] and Aaronson and Ambainis [AA15], is a well studied computational problem in the context of separating quantum and classical computational models. Variants of this problem were used to give tight separations between quantum and classical query complexity [AA15]; the first separation between ... more >>>

Huacheng Yu

In this paper, we prove a strong XOR lemma for bounded-round two-player randomized communication. For a function $f:\mathcal{X}\times \mathcal{Y}\rightarrow\{0,1\}$, the $n$-fold XOR function $f^{\oplus n}:\mathcal{X}^n\times \mathcal{Y}^n\rightarrow\{0,1\}$ maps $n$ input pairs $(X_1,\ldots,X_n,Y_1,\ldots,Y_n)$ to the XOR of the $n$ output bits $f(X_1,Y_1)\oplus \cdots \oplus f(X_n, Y_n)$. We prove that if every ... more >>>

Ari Karchmer

Carmosino et al. (2016) demonstrated that natural proofs of circuit lower bounds imply algorithms for learning circuits with membership queries over the uniform distribution. Indeed, they exercised this implication to obtain a quasi-polynomial time learning algorithm for ${AC}^0[p]$ circuits, for any prime $p$, by leveraging the existing natural proofs from ... more >>>

William Hoza

We study hardness amplification in the context of two well-known "moderate" average-case hardness results for $\mathrm{AC}^0$ circuits. First, we investigate the extent to which $\mathrm{AC}^0$ circuits of depth $d$ can approximate $\mathrm{AC}^0$ circuits of some larger depth $d + k$. The case $k = 1$ is resolved by HÃ¥stad, Rossman, ... more >>>