Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LOW DEGREE POLYNOMIALS:
Reports tagged with low degree polynomials:
TR05-155 | 10th December 2005
Amir Shpilka

#### Constructions of low-degree and error-correcting epsilon-biased sets

In this work we give two new constructions of $\epsilon$-biased
generators. Our first construction answers an open question of
Dodis and Smith, and our second construction
significantly extends a result of Mossel et al.
In particular we obtain the following results:

1. We construct a family of asymptotically good binary ... more >>>

TR07-075 | 9th August 2007
Shachar Lovett

#### Unconditional pseudorandom generators for low degree polynomials

We give an explicit construction of pseudorandom
generators against low degree polynomials over finite fields. We
show that the sum of $2^d$ small-biased generators with error
$\epsilon^{2^{O(d)}}$ is a pseudorandom generator against degree $d$
polynomials with error $\epsilon$. This gives a generator with seed
length $2^{O(d)} \log{(n/\epsilon)}$. Our construction follows ... more >>>

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

TR08-072 | 11th August 2008
Shachar Lovett, Tali Kaufman

#### Worst case to Average case reductions for polynomials

A degree-d polynomial p in n variables over a field F is equidistributed if it takes on each of its |F| values close to equally often, and biased otherwise. We say that p has low rank if it can be expressed as a function of a small number of lower ... more >>>

TR08-111 | 14th November 2008
Shachar Lovett, Tali Kaufman

#### The List-Decoding Size of Reed-Muller Codes

Revisions: 2

In this work we study the list-decoding size of Reed-Muller codes. Given a received word and a distance parameter, we are interested in bounding the size of the list of Reed-Muller codewords that are within that distance from the received word. Previous bounds of Gopalan, Klivans and Zuckerman~\cite{GKZ08} on the ... more >>>

TR13-145 | 20th October 2013
Gil Cohen, Avishay Tal

#### Two Structural Results for Low Degree Polynomials and Applications

Revisions: 1

In this paper, two structural results concerning low degree polynomials over the field $\mathbb{F}_2$ are given. The first states that for any degree d polynomial f in n variables, there exists a subspace of $\mathbb{F}_2^n$ with dimension $\Omega(n^{1/(d-1)})$ on which f is constant. This result is shown to be tight. ... more >>>

TR13-155 | 10th November 2013
Gil Cohen, Amnon Ta-Shma

#### Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes

Revisions: 2

Constructing pseudorandom generators for low degree polynomials has received a considerable attention in the past decade. Viola [CC 2009], following an exciting line of research, constructed a pseudorandom generator for degree d polynomials in n variables, over any prime field. The seed length used is $O(d \log{n} + d 2^d)$, ... more >>>

TR19-145 | 31st October 2019
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman

#### XOR Lemmas for Resilient Functions Against Polynomials

A major challenge in complexity theory is to explicitly construct functions that have small correlation with low-degree polynomials over $F_2$. We introduce a new technique to prove such correlation bounds with $F_2$ polynomials. Using this technique, we bound the correlation of an XOR of Majorities with constant degree polynomials. In ... more >>>

ISSN 1433-8092 | Imprint