Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with noise stability:
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 >>>

TR09-130 | 1st December 2009
Ryan O'Donnell, YI WU, Yuan Zhou

Optimal lower bounds for locality sensitive hashing (except when $q$ is tiny)

We study lower bounds for Locality Sensitive Hashing (LSH) in the strongest setting: point sets in $\{0,1\}^d$ under the Hamming distance. Recall that $\mathcal{H}$ is said to be an $(r, cr, p, q)$-sensitive hash family if all pairs $x,y \in \{0,1\}^d$ with dist$(x,y) \leq r$ have probability at least $p$ ... more >>>

TR12-174 | 12th December 2012
Anat Ganor, Ilan Komargodski, Ran Raz

The Spectrum of Small DeMorgan Formulas

Revisions: 1

We show a connection between the deMorgan formula size of a Boolean function and the noise stability of the function. Using this connection, we show that the Fourier spectrum of any balanced Boolean function computed by a deMorgan formula of size $s$ is concentrated on coefficients of degree up to ... more >>>

TR17-125 | 7th August 2017
Badih Ghazi, Pritish Kamath, Prasad Raghavendra

Dimension Reduction for Polynomials over Gaussian Space and Applications

In this work we introduce a new technique for reducing the dimension of the ambient space of low-degree polynomials in the Gaussian space while preserving their relative correlation structure. As applications, we address the following problems:

(I) Computability of the Approximately Optimal Noise Stable function over Gaussian space:

The goal ... more >>>

TR17-141 | 19th September 2017
Joshua Brakensiek, Venkatesan Guruswami

A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover

We give a family of dictatorship tests with perfect completeness and low-soundness for 2-to-2 constraints. The associated 2-to-2 conjecture has been the basis of some previous inapproximability results with perfect completeness. However, evidence towards the conjecture in the form of integrality gaps even against weak semidefinite programs has been elusive. ... more >>>

ISSN 1433-8092 | Imprint