Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > FOURIER ANALYSIS:
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 &#8901; x - &#952;). 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
functions are the same dictatorship, or all their low degree ... more >>>

TR09-020 | 2nd March 2009

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

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$: \begin{enumerate} \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$

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

TR17-171 | 6th November 2017
Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal

#### Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity

Revisions: 1

We present an explicit pseudorandom generator with seed length $\tilde{O}((\log n)^{w+1})$ for read-once, oblivious, width $w$ branching programs that can read their input bits in any order. This improves upon the work of Impaggliazzo, Meka and Zuckerman (FOCS'12) where they required seed length $n^{1/2+o(1)}$.

A central ingredient in our work ... more >>>

TR18-016 | 25th January 2018
Naomi Kirshner, Alex Samorodnitsky

#### On $\ell_4$ : $\ell_2$ ratio of functions with restricted Fourier support

Revisions: 1

Given a subset $A\subseteq \{0,1\}^n$, let $\mu(A)$ be the maximal ratio between $\ell_4$ and $\ell_2$ norms of a function whose Fourier support is a subset of $A$. We make some simple observations about the connections between $\mu(A)$ and the additive properties of $A$ on one hand, and between $\mu(A)$ and ... more >>>

TR18-147 | 19th August 2018
Michael Forbes, Zander Kelley

#### Pseudorandom Generators for Read-Once Branching Programs, in any Order

A central question in derandomization is whether randomized logspace (RL) equals deterministic logspace (L). To show that RL=L, it suffices to construct explicit pseudorandom generators (PRGs) that fool polynomial-size read-once (oblivious) branching programs (roBPs). Starting with the work of Nisan, pseudorandom generators with seed-length $O(\log^2 n)$ were constructed. Unfortunately, ... more >>>

TR19-070 | 14th May 2019
Alessandro Chiesa, Peter Manohar, Igor Shinkar

#### On Local Testability in the Non-Signaling Setting

Revisions: 1

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics for decades, and have recently found applications in theoretical computer science. These applications motivate the study of local-to-global phenomena for non-signaling functions.

We present general results about the local testability of linear codes in the non-signaling ... more >>>

TR19-087 | 10th June 2019
Rohit Agrawal

Revisions: 1

In this note we compare two measures of the complexity of a class $\mathcal F$ of Boolean functions studied in (unconditional) pseudorandomness: $\mathcal F$'s ability to distinguish between biased and uniform coins (the coin problem), and the norms of the different levels of the Fourier expansion of functions in $\mathcal ... more >>> TR19-173 | 28th November 2019 Divesh Aggarwal, Siyao Guo, Maciej Obremski, Joao Ribeiro, Noah Stephens-Davidowitz #### Extractor Lower Bounds, Revisited Revisions: 1 We revisit the fundamental problem of determining seed length lower bounds for strong extractors and natural variants thereof. These variants stem from a change in quantifiers'' over the seeds of the extractor: While a strong extractor requires that the average output bias (over all seeds) is small for all input ... more >>> TR20-151 | 8th October 2020 Venkatesan Guruswami, Vinayak Kumar #### Pseudobinomiality of the Sticky Random Walk Random walks on expanders are a central and versatile tool in pseudorandomness. If an arbitrary half of the vertices of an expander graph are marked, known Chernoff bounds for expander walks imply that the number$M$of marked vertices visited in a long$n$-step random walk strongly concentrates around the ... more >>> TR21-004 | 10th January 2021 Vishnu Iyer, Avishay Tal, Michael Whitmeyer #### Junta Distance Approximation with Sub-Exponential Queries Leveraging tools of De, Mossel, and Neeman [FOCS, 2019], we show two different results pertaining to the tolerant testing of juntas. Given black-box access to a Boolean function$f:\{\pm1\}^{n} \to \{\pm1\}$we give a poly$(k, \frac{1}{\varepsilon})$query algorithm that distinguishes between functions that are$\gamma$-close to$k$-juntas and$(\gamma+\varepsilon)$-far from ... more >>> TR21-110 | 22nd July 2021 Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco Servedio, Emanuele Viola #### Fourier growth of structured$\mathbb{F}_2$-polynomials and applications We analyze the Fourier growth, i.e. the$L_1$Fourier weight at level$k$(denoted$L_{1,k}$), of various well-studied classes of "structured"$\mathbb{F}_2$-polynomials. This study is motivated by applications in pseudorandomness, in particular recent results and conjectures due to [CHHL19,CHLT19,CGLSS20] which show that upper bounds on Fourier growth (even at ... more >>> TR21-139 | 24th September 2021 Venkatesan Guruswami, Jonathan Mosheiff #### Punctured Large Distance Codes, and Many Reed-Solomon Codes, Achieve List-Decoding Capacity Revisions: 2 We prove the existence of Reed-Solomon codes of any desired rate$R \in (0,1)$that are combinatorially list-decodable up to a radius approaching$1-R$, which is the information-theoretic limit. This is established by starting with the full-length$[q,k]_q$Reed-Solomon code over a field$\mathbb{F}_q$that is polynomially larger than the ... more >>> TR21-168 | 17th November 2021 Tom Gur, Noam Lifshitz, Siqi Liu #### Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for$\epsilon$-Product Spaces Revisions: 2 We prove hypercontractive inequalities on high dimensional expanders. As in the settings of the p-biased hypercube, the symmetric group, and the Grassmann scheme, our inequalities are effective for global functions, which are functions that are not significantly affected by a restriction of a small set of coordinates. As applications, we ... more >>> TR22-012 | 2nd February 2022 Anup Rao, Oscar Sprumont #### On List Decoding Transitive Codes From Random Errors We study the error resilience of transitive linear codes over$F_2$. We give tight bounds on the weight distribution of every such code$C$, and we show how these bounds can be used to infer bounds on the error rates that$C$can tolerate on the binary symmetric channel. Using ... more >>> TR22-034 | 3rd March 2022 Chin Ho Lee, Edward Pyne, Salil Vadhan #### Fourier Growth of Regular Branching Programs We analyze the Fourier growth, i.e. the$L_1$Fourier weight at level$k$(denoted$L_{1,k}$), of read-once regular branching programs. We prove that every read-once regular branching program$B$of width$w \in [1,\infty]$with$s$accepting states on$n$-bit inputs must have its$L_{1,k}$bounded by$\$
\min\left\{ ... more >>>

ISSN 1433-8092 | Imprint