Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > GOWERS NORM:
Reports tagged with Gowers norm:
TR07-123 | 21st November 2007
Shachar Lovett, Roy Meshulam, Alex Samorodnitsky

#### Inverse Conjecture for the Gowers norm is false

Revisions: 2

Let $p$ be a fixed prime number, and $N$ be a large integer.
The 'Inverse Conjecture for the Gowers norm' states that if the "$d$-th Gowers norm" of a function $f:\F_p^N \to \F_p$ is non-negligible, that is larger than a constant independent of $N$, then $f$ can be non-trivially ... more >>>

TR07-132 | 8th December 2007
Emanuele Viola

#### The sum of d small-bias generators fools polynomials of degree d

We prove that the sum of $d$ small-bias generators $L : \F^s \to \F^n$ fools degree-$d$ polynomials in $n$
variables over a prime field $\F$, for any fixed
degree $d$ and field $\F$, including $\F = \F_2 = {0,1}$.

Our result improves on both the work by Bogdanov and
Viola ... 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-033 | 16th April 2009
Phokion G. Kolaitis, Swastik Kopparty

#### Random Graphs and the Parity Quantifier

The classical zero-one law for first-order logic on random graphs says that for every first-order property $\varphi$ in the theory of graphs and every $p \in (0,1)$, the probability that the random graph $G(n, p)$ satisfies $\varphi$ approaches either $0$ or $1$ as $n$ approaches infinity. It is well known ... more >>>

TR09-086 | 2nd October 2009
Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

#### Optimal testing of Reed-Muller codes

Revisions: 1

We consider the problem of testing if a given function
$f : \F_2^n \rightarrow \F_2$ is close to any degree $d$ polynomial
in $n$ variables, also known as the Reed-Muller testing problem.
Alon et al.~\cite{AKKLR} proposed and analyzed a natural
$2^{d+1}$-query test for this property and showed that it accepts
more >>>

TR11-029 | 6th March 2011
Hamed Hatami, Shachar Lovett

Revisions: 1

Recently there has been much interest in Gowers uniformity norms from the perspective of theoretical computer science. This is mainly due to the fact that these norms provide a method for testing whether the maximum correlation of a function $f:\mathbb{F}_p^n \rightarrow \mathbb{F}_p$ with polynomials of degree at most $d \le ... more >>> TR12-001 | 1st January 2012 Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett #### Testing Low Complexity Affine-Invariant Properties Invariance with respect to linear or affine transformations of the domain is arguably the most common symmetry exhibited by natural algebraic properties. In this work, we show that any low complexity affine-invariant property of multivariate functions over finite fields is testable with a constant number of queries. This immediately reproves, ... more >>> TR12-184 | 26th December 2012 Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett #### Every locally characterized affine-invariant property is testable. Revisions: 1 Let$\mathbb{F} = \mathbb{F}_p$for any fixed prime$p \geq 2$. An affine-invariant property is a property of functions on$\mathbb{F}^n$that is closed under taking affine transformations of the domain. We prove that all affine-invariant property having local characterizations are testable. In fact, we show a proximity-oblivious test for ... more >>> TR13-166 | 28th November 2013 Arnab Bhattacharyya #### On testing affine-invariant properties An affine-invariant property over a finite field is a property of functions over F_p^n that is closed under all affine transformations of the domain. This class of properties includes such well-known beasts as low-degree polynomials, polynomials that nontrivially factor, and functions of low spectral norm. The last few years has ... more >>> TR14-018 | 13th February 2014 Arnab Bhattacharyya #### Polynomial decompositions in polynomial time Fix a prime$p$. Given a positive integer$k$, a vector of positive integers${\bf \Delta} = (\Delta_1, \Delta_2, \dots, \Delta_k)$and a function$\Gamma: \mathbb{F}_p^k \to \F_p$, we say that a function$P: \mathbb{F}_p^n \to \mathbb{F}_p$is$(k,{\bf \Delta},\Gamma)$-structured if there exist polynomials$P_1, P_2, \dots, P_k:\mathbb{F}_p^n \to \mathbb{F}_p\$ ... more >>>

TR14-040 | 30th March 2014
Hamed Hatami, Pooya Hatami, Shachar Lovett

#### General systems of linear forms: equidistribution and true complexity

Revisions: 1

The densities of small linear structures (such as arithmetic progressions) in subsets of Abelian groups can be expressed as certain analytic averages involving linear forms. Higher-order Fourier analysis examines such averages by approximating the indicator function of a subset by a function of bounded number of polynomials. Then, to approximate ... more >>>

TR15-185 | 24th November 2015
Arnab Bhattacharyya, Sivakanth Gopi

#### Lower bounds for constant query affine-invariant LCCs and LTCs

Affine-invariant codes are codes whose coordinates form a vector space over a finite field and which are invariant under affine transformations of the coordinate space. They form a natural, well-studied class of codes; they include popular codes such as Reed-Muller and Reed-Solomon. A particularly appealing feature of affine-invariant codes is ... more >>>

ISSN 1433-8092 | Imprint