Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Fourier analysis:
TR95-056 | 26th November 1995
Oded Goldreich

Three XOR-Lemmas -- An Exposition

We provide an exposition of three Lemmas which relate
general properties of distributions
with the exclusive-or of certain bit locations.

The first XOR-Lemma, commonly attributed to U.V. Vazirani,
relates the statistical distance of a distribution from uniform
to the maximum bias of the xor of certain bit positions.
more >>>

TR03-085 | 28th November 2003
Ke Yang

On the (Im)possibility of Non-interactive Correlation Distillation

We study the problem of non-interactive correlation distillation
(NICD). Suppose Alice and Bob each has a string, denoted by
$A=a_0a_1\cdots a_{n-1}$ and $B=b_0b_1\cdots b_{n-1}$,
respectively. Furthermore, for every $k=0,1,...,n-1$, $(a_k,b_k)$ is
independently drawn from a distribution $\noise$, known as the ``noise
mode''. Alice and Bob wish to ``distill'' the correlation
more >>>

TR05-088 | 3rd August 2005
Jan Arpe

Learning Juntas in the Presence of Noise

The combination of two major challenges in machine learning is investigated: dealing with large amounts of irrelevant information and learning from noisy data. It is shown that large classes of Boolean concepts that depend on a small number of variables---so-called juntas---can be learned efficiently from random examples corrupted by random ... more >>>

TR07-098 | 2nd October 2007
Tali Kaufman, Simon Litsyn, Ning Xie

Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)

For Boolean functions that are $\epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted $\textsc{rej}(\epsilon)$) of the linearity test suggested by Blum, Luby and Rubinfeld. The interest in this problem is partly due to its relation to PCP constructions and hardness of ... more >>>

TR07-128 | 10th November 2007
Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco Servedio

Testing Halfspaces

This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e. a function of the form f(x)=sgn(w ⋅ x - θ). We consider halfspaces over the continuous domain R^n (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube {-1,1}^n ... more >>>

TR08-088 | 13th September 2008
Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

Testing Linear-Invariant Non-Linear Properties

Revisions: 1

We consider the task of testing properties of Boolean functions that
are invariant under linear transformations of the Boolean cube. Previous
work in property testing, including the linearity test and the test
for Reed-Muller codes, has mostly focused on such tasks for linear
properties. The one exception is a test ... more >>>

TR08-098 | 12th November 2008
Victor Chen

A Hypergraph Dictatorship Test with Perfect Completeness

Revisions: 1

A hypergraph dictatorship test is first introduced by Samorodnitsky
and Trevisan and serves as a key component in
their unique games based $\PCP$ construction. Such a test has oracle
access to a collection of functions and determines whether all the
functions are the same dictatorship, or all their low degree ... more >>>

TR09-020 | 2nd March 2009
Venkatesan Guruswami, Prasad Raghavendra

Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers.

A classic result due to Hastad established that for every constant \eps > 0, given an overdetermined system of linear equations over a finite field \F_q where each equation depends on exactly 3 variables and at least a fraction (1-\eps) of the equations can be satisfied, it is NP-hard to ... more >>>

TR09-037 | 10th April 2009
Parikshit Gopalan

A Fourier-analytic approach to Reed-Muller decoding

We present a Fourier-analytic approach to list-decoding Reed-Muller codes over arbitrary finite fields. We prove that the list-decoding radius for quadratic polynomials equals $1 - 2/q$ over any field $F_q$ where $q > 2$. This confirms a conjecture due to Gopalan, Klivans and Zuckerman for degree $2$. Previously, tight bounds ... more >>>

TR09-104 | 26th October 2009
Scott Aaronson

BQP and the Polynomial Hierarchy

The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis.

First, we show that there ... more >>>

TR09-110 | 5th November 2009
Scott Aaronson, Andris Ambainis

The Need for Structure in Quantum Speedups

Revisions: 1

Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate.

First, we show that for any problem that ... more >>>

TR11-075 | 6th May 2011
Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira

Testing Odd-Cycle-Freeness in Boolean Functions

Call a function $f: \mathbb{F}_2^n \to \{0,1\}$ odd-cycle-free if there are no $x_1, \dots, x_k \in \mathbb{F}_2^n$ with $k$ an odd integer such that $f(x_1) = \cdots = f(x_k) = 1$ and $x_1 + \cdots + x_k = 0$. We show that one can distinguish odd-cycle-free functions from those $\epsilon$-far ... more >>>

TR12-072 | 5th June 2012
Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio

Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces

The \emph{Chow parameters} of a Boolean function $f: \{-1,1\}^n \to \{-1,1\}$ are its $n+1$ degree-0 and degree-1 Fourier coefficients. It has been known since 1961 \cite{Chow:61, Tannenbaum:61} that the (exact values of the) Chow parameters of any linear threshold function $f$ uniquely specify $f$ within the space of all Boolean ... more >>>

TR12-074 | 12th June 2012
Venkatesan Guruswami, Yuan Zhou

Approximating Bounded Occurrence Ordering CSPs

A theorem of HÃ¥stad shows that for every constraint satisfaction problem (CSP) over a fixed size domain, instances where each variable appears in at most $O(1)$ constraints admit a non-trivial approximation algorithm, in the sense that one can beat (by an additive constant) the approximation ratio achieved by the naive ... 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 >>>

TR12-185 | 29th December 2012
Siu Man Chan, Aaron Potechin

Tight Bounds for Monotone Switching Networks via Fourier Analysis

We prove tight size bounds on monotone switching networks for the NP-complete problem of
$k$-clique, and for an explicit monotone problem by analyzing a pyramid structure of height $h$ for
the P-complete problem of generation. This gives alternative proofs of the separations of m-NC
from m-P and of m-NC$^i$ from ... more >>>

TR13-061 | 17th April 2013
Zeev Dvir, Guangda Hu

Matching-Vector Families and LDCs Over Large Modulo

We prove new upper bounds on the size of families of vectors in $\Z_m^n$ with restricted modular inner products, when $m$ is a large integer. More formally, if $\vec{u}_1,\ldots,\vec{u}_t \in \Z_m^n$ and $\vec{v}_1,\ldots,\vec{v}_t \in \Z_m^n$ satisfy $\langle\vec{u}_i,\vec{v}_i\rangle\equiv0\pmod m$ and $\langle\vec{u}_i,\vec{v}_j\rangle\not\equiv0\pmod m$ for all $i\neq j\in[t]$, we prove that $t \leq ... more >>>

TR13-086 | 13th June 2013
Omer Reingold, Thomas Steinke, Salil Vadhan

Pseudorandomness for Regular Branching Programs via Fourier Analysis

Revisions: 1

We present an explicit pseudorandom generator for oblivious, read-once, permutation branching programs of constant width that can read their input bits in any order. The seed length is $O(\log^2 n)$, where $n$ is the length of the branching program. The previous best seed length known for this model was $n^{1/2+o(1)}$, ... more >>>

TR13-114 | 24th August 2013
Parikshit Gopalan, Salil Vadhan, Yuan Zhou

Locally Testable Codes and Cayley Graphs

Revisions: 1

We give two new characterizations of ($\F_2$-linear) locally testable error-correcting codes in terms of Cayley graphs over $\F_2^h$:

\item A locally testable code is equivalent to a Cayley graph over $\F_2^h$ whose set of generators is significantly larger than $h$ and has no short linear dependencies, but yields a ... more >>>

TR13-122 | 5th September 2013
Irit Dinur, Venkatesan Guruswami

PCPs via low-degree long code and hardness for constrained hypergraph coloring

Revisions: 1

We develop new techniques to incorporate the recently proposed ``short code" (a low-degree version of the long code) into the construction and analysis of PCPs in the classical ``Label Cover + Fourier Analysis'' framework. As a result, we obtain more size-efficient PCPs that yield improved hardness results for approximating CSPs ... more >>>

TR13-163 | 28th November 2013
Russell Impagliazzo, Valentine Kabanets

Fourier Concentration from Shrinkage

Revisions: 2

For Boolean functions computed by de Morgan formulas of subquadratic size or read-once de Morgan formulas, we prove a sharp concentration of the Fourier mass on ``small-degree'' coefficients. For a Boolean function $f:\{0,1\}^n\to\{1,-1\}$ computable by a de Morgan formula of size $s$, we show that
\sum_{A\subseteq [n]\; :\; |A|>s^{1/\Gamma ... more >>>

TR14-048 | 10th April 2014
Avishay Tal

Shrinkage of De Morgan Formulae from Quantum Query Complexity

Revisions: 1

We give a new and improved proof that the shrinkage exponent of De Morgan formulae is $2$. Namely, we show that for any Boolean function $f: \{-1,1\}^n \to \{-1,1\}$, setting each variable out of $x_1, \ldots, x_n$ with probability $1-p$ to a randomly chosen constant, reduces the expected formula size ... more >>>

TR14-076 | 27th May 2014
Thomas Steinke

Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs

Revisions: 1

We present an explicit pseudorandom generator for oblivious, read-once, width-$3$ branching programs, which can read their input bits in any order. The generator has seed length $\tilde{O}( \log^3 n ).$ The previously best known seed length for this model is $n^{1/2+o(1)}$ due to Impagliazzo, Meka, and Zuckerman (FOCS '12). Our ... more >>>

TR14-155 | 21st November 2014
Scott Aaronson, Andris Ambainis

Forrelation: A Problem that Optimally Separates Quantum from Classical Computing

We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum ... more >>>

TR14-174 | 14th December 2014
Avishay Tal

Tight bounds on The Fourier Spectrum of $AC^0$

Revisions: 2

We show that $AC^0$ circuits of depth $d$ and size $m$ have at most $2^{-\Omega(k/(\log m)^{d-1})}$ of their Fourier mass at level $k$ or above. Our proof builds on a previous result by H{\aa}stad (SICOMP, 2014) who proved this bound for the special case $k=n$. Our result is tight up ... more >>>

TR15-076 | 28th April 2015
Mahdi Cheraghchi, Piotr Indyk

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

For every fixed constant $\alpha > 0$, we design an algorithm for computing the $k$-sparse Walsh-Hadamard transform of an $N$-dimensional vector $x \in \mathbb{R}^N$ in time $k^{1+\alpha} (\log N)^{O(1)}$. Specifically, the algorithm is given query access to $x$ and computes a $k$-sparse $\tilde{x} \in \mathbb{R}^N$ satisfying $\|\tilde{x} - \hat{x}\|_1 \leq ... more >>>

TR16-113 | 22nd July 2016
Gillat Kol, Ran Raz, Avishay Tal

Time-Space Hardness of Learning Sparse Parities

We define a concept class ${\cal F}$ to be time-space hard (or memory-samples hard) if any learning algorithm for ${\cal F}$ requires either a memory of size super-linear in $n$ or a number of samples super-polynomial in $n$, where $n$ is the length of one sample.

A recent work shows ... more >>>

TR16-161 | 26th October 2016
Shachar Lovett, Jiapeng Zhang

Robust sensitivity

Revisions: 1

The sensitivity conjecture is one of the central open problems in boolean complexity. A recent work of Gopalan et al. [CCC 2016] conjectured a robust analog of the sensitivity conjecture, which relates the decay of the Fourier mass of a boolean function to moments of its sensitivity. We prove this ... more >>>

TR16-174 | 7th November 2016
Elchanan Mossel, Sampath Sampath Kannan, Grigory Yaroslavtsev

Linear Sketching over $\mathbb F_2$

Revisions: 5 , Comments: 2

We initiate a systematic study of linear sketching over $\mathbb F_2$. For a given Boolean function $f \colon \{0,1\}^n \to \{0,1\}$ a randomized $\mathbb F_2$-sketch is a distribution $\mathcal M$ over $d \times n$ matrices with elements over $\mathbb F_2$ such that $\mathcal Mx$ suffices for computing $f(x)$ with high ... more >>>

TR17-075 | 29th April 2017
Clement Canonne, Ilias Diakonikolas, Alistair Stewart

Fourier-Based Testing for Families of Distributions

Revisions: 1

We study the general problem of testing whether an unknown discrete distribution belongs to a given family of distributions. More specifically, given a class of distributions $\mathcal{P}$ and sample access to an unknown distribution $\mathbf{P}$, we want to distinguish (with high probability) between the case that $\mathbf{P} \in \mathcal{P}$ and ... 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