Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with xor lemma:
TR03-042 | 15th May 2003
Luca Trevisan

List Decoding Using the XOR Lemma

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

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

TR07-034 | 29th March 2007
Anup Rao

An Exposition of Bourgain's 2-Source Extractor

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

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

TR09-078 | 16th September 2009
Falk Unger

A Probabilistic Inequality with Applications to Threshold Direct-product Theorems

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

TR20-101 | 7th July 2020
Uma Girish, Ran Raz, Wei Zhan

Lower Bounds for XOR of Forrelations

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

TR22-118 | 23rd August 2022
Huacheng Yu

Strong XOR Lemma for Communication with Bounded Rounds

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

TR23-085 | 4th June 2023
Ari Karchmer

Average-Case PAC-Learning from Nisan's Natural Proofs

Revisions: 2

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

TR23-176 | 15th November 2023
William Hoza

A Technique for Hardness Amplification Against $\mathrm{AC}^0$

Revisions: 1

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

ISSN 1433-8092 | Imprint