Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness (2009)
Ben-Eliezer, Ido, Lovett, Shachar, Yadin, Ariel
We study the computational power of polynomial threshold functions, that is, threshold functions of real polynomials over the boolean cube. We provide two new results bounding the computational power...
The density of weights of Generalized Reed--Muller codes (2009)
We study the density of the weights of Generalized Reed--Muller codes. Let $RM_p(r,m)$ denote the code of multivariate polynomials over $\F_p$ in $m$ variables of total degree at most $r$. We...
The List-Decoding Size of Reed-Muller Codes (2008)
Kaufman, Tali, Lovett, Shachar
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...
Worst Case to Average Case Reductions for Polynomials (2008)
Kaufman, Tali, Lovett, Shachar
A degree-$d$ polynomial $p$ in $n$ variables over a field $\F$ is {\em equidistributed} if it takes on each of its $|\F|$ values close to equally often, and {\em biased} otherwise. We say that $p$...
Lower bounds for Adaptive Linearity Tests without using the Gowers Norm (2008)
Linearity tests are randomized algorithms which have oracle access to the truth table of some function f, which are supposed to distinguish between linear functions and functions which are far from...
Lower bounds for adaptive linearity tests (2008)
Linearity tests are randomized algorithms which have oracle access to the truth table of some function f, and are supposed to distinguish between linear functions and functions which are far from...
Lower bounds for adaptive linearity tests (2008)
Linearity tests are randomized algorithms which have oracle access to the truth table of some function f, and are supposed to distinguish between linear functions and functions which are far from...
Lower bounds for adaptive linearity tests (2008)
Linearity tests are randomized algorithms which have oracle access to the truth table of some function f, and are supposed to distinguish between linear functions and functions which are far from...
45. Lower bounds for adaptive linearity tests (2008)
Linearity tests are randomized algorithms which have oracle access to the truth table of some function f, and are supposed to distinguish between linear functions and functions which are far from...
Inverse Conjecture for the Gowers norm is false (2007)
Lovett, Shachar, Meshulam, Roy, Samorodnitsky, Alex
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,...
Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits (2007)
It is well known that R^N has subspaces of dimension proportional to N on which the \ell_1 norm is equivalent to the \ell_2 norm; however, no explicit constructions are known. Extending earlier work...
Inverse Conjecture for the Gowers norm is false (2007)
Shachar Lovett, Roy Meshulam, Alex Samorodnitsky
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 N p → F is non-negligible,...
Inverse Conjecture for the Gowers norm is false (2007)
Shachar Lovett, Roy Meshulam, Alex Samorodnitsky
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 N p → F is non-negligible,...
Unconditional pseudorandom generators for low degree polynomials (2007)
We give an explicit construction of pseudorandom generators against low degree polynomials over finite fields. We show that the sum of 2d small-biased generators with error ɛ2O(d) is a pseudorandom...