Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Shachar Lovett:

TR18-082 | 21st April 2018
Xin Li, Shachar Lovett, Jiapeng Zhang

Sunflowers and Quasi-sunflowers from Randomness Extractors

The Erdos-Rado sunflower theorem (Journal of Lond. Math. Soc. 1960) is a fundamental result in combinatorics, and the corresponding sunflower conjecture is a central open problem. Motivated by applications in complexity theory, Rossman (FOCS 2010) extended the result to quasi-sunflowers, where similar conjectures emerge about the optimal parameters for which ... more >>>

TR18-074 | 23rd April 2018
Daniel Kane, Shachar Lovett, Shay Moran

Generalized comparison trees for point-location problems

Let $H$ be an arbitrary family of hyper-planes in $d$-dimensions. We show that the point-location problem for $H$
can be solved by a linear decision tree that only uses a special type of queries called \emph{generalized comparison queries}. These queries correspond to hyperplanes that can be written as a linear ... more >>>

TR18-047 | 7th March 2018
Shachar Lovett

A proof of the GM-MDS conjecture

Revisions: 1

The GM-MDS conjecture of Dau et al. (ISIT 2014) speculates that the MDS condition, which guarantees the existence of MDS matrices with a prescribed set of zeros over large fields, is in fact sufficient for existence of such matrices over small fields. We prove this conjecture.

more >>>

TR18-015 | 25th January 2018
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett

Pseudorandom Generators from Polarizing Random Walks

Comments: 1

We propose a new framework for constructing pseudorandom generators for $n$-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in $[-1,1]^n$. Next, we use a fractional pseudorandom generator as steps of a random walk in $[-1,1]^n$ that ... more >>>

TR17-085 | 4th May 2017
Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang

Active classification with comparison queries

We study an extension of active learning in which the learning algorithm may ask the annotator to compare the distances of two examples from the boundary of their label-class. For example, in a recommendation system application (say for restaurants), the annotator may be asked whether she liked or disliked a ... more >>>

TR17-082 | 4th May 2017
Daniel Kane, Shachar Lovett, Shay Moran

Near-optimal linear decision trees for k-SUM and related problems

We construct near optimal linear decision trees for a variety of decision problems in combinatorics and discrete geometry.
For example, for any constant $k$, we construct linear decision trees that solve the $k$-SUM problem on $n$ elements using $O(n \log^2 n)$ linear queries.
Moreover, the queries we use are comparison ... more >>>

TR17-070 | 15th April 2017
Shachar Lovett, Sankeerth Rao, Alex Vardy

Probabilistic Existence of Large Sets of Designs

A new probabilistic technique for establishing the existence of certain regular combinatorial structures has been introduced by Kuperberg, Lovett, and Peled (STOC 2012). Using this technique, it can be shown that under certain conditions, a randomly chosen structure has the required properties of a $t-(n,k,?)$ combinatorial design with tiny, yet ... more >>>

TR17-033 | 19th February 2017
Daniel Kane, Shachar Lovett, Sankeerth Rao

Labeling the complete bipartite graph with no zero cycles

Revisions: 2

Assume that the edges of the complete bipartite graph $K_{n,n}$ are labeled with elements of $\mathbb{F}_2^d$, such that the sum over
any simple cycle is nonzero. What is the smallest possible value of $d$? This problem was raised by Gopalan et al. [SODA 2017] as it characterizes the alphabet size ... 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-118 | 31st July 2016
Shachar Lovett, Jiapeng Zhang

On the impossibility of entropy reversal, and its application to zero-knowledge proofs

Zero knowledge proof systems have been widely studied in cryptography. In the statistical setting, two classes of proof systems studied are Statistical Zero Knowledge (SZK) and Non-Interactive Statistical Zero Knowledge (NISZK), where the difference is that in NISZK only very limited communication is allowed between the verifier and the prover. ... more >>>

TR16-044 | 21st March 2016
Kaave Hosseini, Shachar Lovett

Structure of protocols for XOR functions

Revisions: 1

Let $f:\{0,1\}^n \to \{0,1\}$ be a boolean function. Its associated XOR function is the two-party function $f_\oplus(x,y) = f(x \oplus y)$.
We show that, up to polynomial factors, the deterministic communication complexity of $f_{\oplus}$ is equal to the parity decision tree complexity of $f$.
This relies on a novel technique ... more >>>

TR16-025 | 26th February 2016
Shachar Lovett

The Fourier structure of low degree polynomials

Revisions: 1

We study the structure of the Fourier coefficients of low degree multivariate polynomials over finite fields. We consider three properties: (i) the number of nonzero Fourier coefficients; (ii) the sum of the absolute value of the Fourier coefficients; and (iii) the size of the linear subspace spanned by the nonzero ... more >>>

TR16-021 | 11th February 2016
Shachar Lovett, Jiapeng Zhang

Noisy Population Recovery from Unknown Noise

The noisy population recovery problem is a statistical inference problem, which is a special case of the problem of learning mixtures of product distributions. Given an unknown distribution on $n$-bit strings with support of size $k$, and given access only to noisy samples from it, where each bit is flipped ... more >>>

TR15-190 | 2nd November 2015
Esther Ezra, Shachar Lovett

On the Beck-Fiala Conjecture for Random Set Systems

Motivated by the Beck-Fiala conjecture, we study discrepancy bounds for random sparse set systems. Concretely, these are set systems $(X,\Sigma)$, where each element $x \in X$ lies in $t$ randomly selected sets of $\Sigma$, where $t$ is an integer parameter. We provide new bounds in two regimes of parameters. We ... more >>>

TR15-179 | 10th November 2015
Divesh Aggarwal, Kaave Hosseini, Shachar Lovett

Affine-malleable Extractors, Spectrum Doubling, and Application to Privacy Amplification

The study of seeded randomness extractors is a major line of research in theoretical computer science. The goal is to construct deterministic algorithms which can take a ``weak" random source $X$ with min-entropy $k$ and a uniformly random seed $Y$ of length $d$, and outputs a string of length close ... more >>>

TR15-172 | 3rd November 2015
Benny Applebaum, Shachar Lovett

Algebraic Attacks against Random Local Functions and Their Countermeasures

Revisions: 1

Suppose that you have $n$ truly random bits $x=(x_1,\ldots,x_n)$ and you wish to use them to generate $m\gg n$ pseudorandom bits $y=(y_1,\ldots, y_m)$ using a local mapping, i.e., each $y_i$ should depend on at most $d=O(1)$ bits of $x$. In the polynomial regime of $m=n^s$, $s>1$, the only known solution, ... more >>>

TR15-096 | 5th June 2015
Abhishek Bhowmick, Shachar Lovett

Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory

Let $f$ be a polynomial of degree $d$ in $n$ variables over a finite field $\mathbb{F}$. The polynomial is said to be unbiased if the distribution of $f(x)$ for a uniform input $x \in \mathbb{F}^n$ is close to the uniform distribution over $\mathbb{F}$, and is called biased otherwise. The polynomial ... more >>>

TR14-175 | 15th December 2014
Abhishek Bhowmick, Shachar Lovett

Nonclassical polynomials as a barrier to polynomial lower bounds

The problem of constructing explicit functions which cannot be approximated by low degree polynomials has been extensively studied in computational complexity, motivated by applications in circuit lower bounds, pseudo-randomness, constructions of Ramsey graphs and locally decodable codes. Still, most of the known lower bounds become trivial for polynomials of ... more >>>

TR14-147 | 6th November 2014
Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman

Rectangles Are Nonnegative Juntas

Revisions: 1

We develop a new method to prove communication lower bounds for composed functions of the form $f\circ g^n$ where $f$ is any boolean function on $n$ inputs and $g$ is a sufficiently ``hard'' two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of $f \circ ... more >>>

TR14-141 | 24th October 2014
Shachar Lovett

Linear codes cannot approximate the network capacity within any constant factor

Network coding studies the capacity of networks to carry information, when internal nodes are allowed to actively encode information. It is known that for multi-cast networks, the network coding capacity can be achieved by linear codes. It is also known not to be true for general networks. The best separation ... more >>>

TR14-123 | 7th October 2014
Shachar Lovett, Jiapeng Zhang

Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions

The noisy population recovery problem is a basic statistical inference problem. Given an unknown distribution in $\{0,1\}^n$ with support of size $k$,
and given access only to noisy samples from it, where each bit is flipped independently with probability $1/2-\eps$,
estimate the original probability up to an additive error of ... more >>>

TR14-087 | 12th July 2014
Abhishek Bhowmick, Shachar Lovett

List decoding Reed-Muller codes over small fields

Revisions: 1

The list decoding problem for a code asks for the maximal radius up to which any ball of that radius contains only a constant number of codewords. The list decoding radius is not well understood even for well studied codes, like Reed-Solomon or Reed-Muller codes.

Fix a finite field $\mathbb{F}$. ... more >>>

TR14-073 | 14th May 2014
Shachar Lovett, Cris Moore, Alexander Russell

Group representations that resist random sampling

Revisions: 1

We show that there exists a family of groups $G_n$ and nontrivial irreducible representations $\rho_n$ such that, for any constant $t$, the average of $\rho_n$ over $t$ uniformly random elements $g_1, \ldots, g_t \in G_n$ has operator norm $1$ with probability approaching 1 as $n \rightarrow \infty$. More quantitatively, we ... more >>>

TR14-041 | 31st March 2014
Shachar Lovett

Recent advances on the log-rank conjecture in communication complexity

The log-rank conjecture is one of the fundamental open problems in communication complexity. It speculates that the deterministic communication complexity of any two-party function is equal to the log of the rank of its associated matrix, up to polynomial factors. Despite much research, we still know very little about this ... 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 >>>

TR14-024 | 19th February 2014
Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider

0-1 Integer Linear Programming with a Linear Number of Constraints

We give an exact algorithm for the 0-1 Integer Linear Programming problem with a linear number of constraints that improves over exhaustive search by an exponential factor. Specifically, our algorithm runs in time $2^{(1-\text{poly}(1/c))n}$ where $n$ is the
number of variables and $cn$ is the number of constraints. The key ... more >>>

TR13-126 | 11th September 2013
Arman Fazeli, Shachar Lovett, Alex Vardy

Nontrivial t-designs over finite fields exist for all t

A $t$-$(n,k,\lambda)$ design over $\mathbb{F}_q$ is a collection of $k$-dimensional subspaces of $\mathbb{F}_q^n$, ($k$-subspaces, for short), called blocks, such that each $t$-dimensional subspace of $\mathbb{F}_q^n$ is contained in exactly $\lambda$ blocks. Such $t$-designs over $\mathbb{F}_q$ are the $q$-analogs of conventional combinatorial designs. Nontrivial $t$-$(n,k,\lambda)$ designs over $\mathbb{F}_q$ are currently known ... more >>>

TR13-087 | 4th June 2013
Hamed Hatami, Shachar Lovett

Estimating the distance from testable affine-invariant properties

Let $\cal{P}$ be an affine invariant property of functions $\mathbb{F}_p^n \to [R]$ for fixed $p$ and $R$. We show that if $\cal{P}$ is locally testable with a constant number of queries, then one can estimate the distance of a function $f$ from $\cal{P}$ with a constant number of queries. This ... more >>>

TR13-084 | 8th June 2013
Shachar Lovett

Communication is bounded by root of rank

Revisions: 1

We prove that any total boolean function of rank $r$ can be computed by a deterministic communication protocol of complexity $O(\sqrt{r} \cdot \log(r))$. Equivalently, any graph whose adjacency matrix has rank $r$ has chromatic number at most $2^{O(\sqrt{r} \cdot \log(r))}$. This gives a nearly quadratic improvement in the dependence on ... more >>>

TR13-081 | 6th June 2013
Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett

Non-malleable Codes from Additive Combinatorics

Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a ... more >>>

TR13-080 | 4th June 2013
Dmitry Gavinsky, Shachar Lovett

En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations

We prove that several measures in communication complexity are equivalent, up to polynomial factors in the logarithm of the rank of the associated matrix: deterministic communication complexity, randomized communication complexity, information cost and zero-communication cost. This shows that in order to prove the log-rank conjecture, it suffices to show that ... 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 >>>

TR12-180 | 21st December 2012
Chaim Even-Zohar, Shachar Lovett

The Freiman-Ruzsa Theorem in Finite Fields

Let $G$ be a finite abelian group of torsion $r$ and let $A$ be a subset of $G$.
The Freiman-Ruzsa theorem asserts that if $|A+A| \le K|A|$
then $A$ is contained in a coset of a subgroup of $G$ of size at most $K^2 r^{K^4} |A|$. It was ... more >>>

TR12-051 | 25th April 2012
Dmitry Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan

A Tail Bound for Read-k Families of Functions

We prove a Chernoff-like large deviation bound on the sum of non-independent random variables that have the following dependence structure. The variables $Y_1,\ldots,Y_r$ are arbitrary Boolean functions of independent random variables $X_1,\ldots,X_m$, modulo a restriction that every $X_i$ influences at most $k$ of the variables $Y_1,\ldots,Y_r$.

more >>>

TR12-042 | 17th April 2012
Chris Beck, Russell Impagliazzo, Shachar Lovett

Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits

There has been considerable interest lately in the complexity of distributions. Recently, Lovett and Viola (CCC 2011) showed that the statistical distance between a uniform distribution over a good code, and any distribution which can be efficiently sampled by a small bounded-depth AC0 circuit, is inverse-polynomially close to one. That ... more >>>

TR12-034 | 5th April 2012
Abhishek Bhowmick, Zeev Dvir, Shachar Lovett

New Lower Bounds for Matching Vector Codes

Revisions: 5

We prove new lower bounds on the encoding length of Matching Vector (MV) codes. These recently discovered families of Locally Decodable Codes (LDCs) originate in the works of Yekhanin [Yek] and Efremenko [Efr] and are the only known families of LDCs with a constant number of queries and sub-exponential encoding ... more >>>

TR12-029 | 3rd April 2012
Shachar Lovett

An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem

The polynomial Freiman-Ruzsa conjecture is one of the important conjectures in additive combinatorics. It asserts than one can switch between combinatorial and algebraic notions of approximate subgroups with only a polynomial loss in the underlying parameters. This conjecture has also already found several applications in theoretical computer science. Recently, Tom ... 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 >>>

TR11-157 | 25th November 2011
Eli Ben-Sasson, Shachar Lovett, Noga Ron-Zewi

An additive combinatorics approach to the log-rank conjecture in communication complexity

Revisions: 1

For a {0,1}-valued matrix $M$ let CC($M$) denote the deterministic communication complexity of the boolean function associated with $M$. The log-rank conjecture of Lovasz and Saks [FOCS 1988] states that CC($M$) is at most $\log^c({\mbox{rank}}(M))$ for some absolute constant $c$ where rank($M$) denotes the rank of $M$ over the field ... more >>>

TR11-144 | 2nd November 2011
Greg Kuperberg, Shachar Lovett, Ron Peled

Probabilistic existence of rigid combinatorial structures

We show the existence of rigid combinatorial objects which previously were not known to exist. Specifically, for a wide range of the underlying parameters, we show the existence of non-trivial orthogonal arrays, $t$-designs, and $t$-wise permutations. In all cases, the sizes of the objects are optimal up to polynomial overhead. ... more >>>

TR11-139 | 26th October 2011
Zeev Dvir, Shachar Lovett

Subspace Evasive Sets

In this work we describe an explicit, simple, construction of large subsets of F^n, where F is a finite field, that have small intersection with every k-dimensional affine subspace. Interest in the explicit construction of such sets, termed subspace-evasive sets, started in the work of Pudlak and Rodl (2004) ... more >>>

TR11-094 | 20th June 2011
Shachar Lovett

Computing polynomials with few multiplications

A folklore result in arithmetic complexity shows that the number of multiplications required to compute some $n$-variate polynomial of degree $d$ is $\sqrt{{n+d \choose n}}$. We complement this by an almost matching upper bound, showing that any $n$-variate polynomial of degree $d$ over any field can be computed with only ... more >>>

TR11-049 | 9th April 2011
Noga Alon, Shachar Lovett

Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions

A family of permutations in $S_n$ is $k$-wise independent if a uniform permutation chosen from the family maps any distinct $k$ elements to any distinct $k$ elements equally likely. Efficient constructions of $k$-wise independent permutations are known for $k=2$ and $k=3$, but are unknown for $k \ge 4$. In fact, ... more >>>

TR11-048 | 10th April 2011
Arkadev Chattopadhyay, Shachar Lovett

Linear systems over abelian groups

We consider a system of linear constraints over any finite Abelian group $G$ of the following form: $\ell_i(x_1,\ldots,x_n) \equiv \ell_{i,1}x_1+\cdots+\ell_{i,n}x_n \in A_i$ for $i=1,\ldots,t$ and each $A_i \subset G$, $\ell_{i,j}$ is an element of $G$ and $x_i$'s are Boolean variables. Our main result shows that the subset of the Boolean ... more >>>

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

Correlation testing for affine invariant properties on $\mathbb{F}_p^n$ in the high error regime

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

TR10-182 | 26th November 2010
Shachar Lovett

An elementary proof of anti-concentration of polynomials in Gaussian variables

Recently there has been much interest in polynomial threshold functions in the context of learning theory, structural results and pseudorandomness. A crucial ingredient in these works is the understanding of the distribution of low-degree multivariate polynomials evaluated over normally distributed inputs. In particular, the two important properties are exponential tail ... more >>>

TR10-181 | 21st November 2010
Hamed Hatami, Shachar Lovett

Higher-order Fourier analysis of $\mathbb{F}_p^n$ and the complexity of systems of linear forms

In this article we are interested in the density of small linear structures (e.g. arithmetic progressions) in subsets $A$ of the group $\mathbb{F}_p^n$. It is possible to express these densities as certain analytic averages involving $1_A$, the indicator function of $A$. In the higher-order Fourier analytic approach, the function $1_A$ ... more >>>

TR10-115 | 17th July 2010
Shachar Lovett, Emanuele Viola

Bounded-depth circuits cannot sample good codes

We study a variant of the classical circuit-lower-bound problems: proving lower bounds for sampling distributions given random bits. We prove a lower bound of $1-1/n^{\Omega(1)}$ on the statistical distance between (i) the output distribution of any small constant-depth (a.k.a.~$\mathrm{AC}^0$) circuit $f : \{0,1\}^{\mathrm{poly}(n)} \to \{0,1\}^n$, and (ii) the uniform distribution ... more >>>

TR10-087 | 17th May 2010
Shachar Lovett, Ely Porat

A lower bound for dynamic approximate membership data structures

An approximate membership data structure is a randomized data
structure for representing a set which supports membership
queries. It allows for a small false positive error rate but has
no false negative errors. Such data structures were first
introduced by Bloom in the 1970's, and have since had numerous
applications, ... more >>>

TR10-065 | 13th April 2010
Tali Kaufman, Shachar Lovett

Testing of exponentially large codes, by a new extension to Weil bound for character sums

Revisions: 1

In this work we consider linear codes which are locally testable
in a sublinear number of queries. We give the first general family
of locally testable codes of exponential size. Previous results of
this form were known only for codes of quasi-polynomial size (e.g.
Reed-Muller codes). We accomplish this by ... more >>>

TR10-033 | 6th March 2010
Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka

Pseudorandom generators for $\mathrm{CC}_0[p]$ and the Fourier spectrum of low-degree polynomials over finite fields

In this paper we give the first construction of a pseudorandom generator, with seed length $O(\log n)$, for $\mathrm{CC}_0[p]$, the class of constant-depth circuits with unbounded fan-in $\mathrm{MOD}_p$ gates, for some prime $p$. More accurately, the seed length of our generator is $O(\log n)$ for any constant error $\epsilon>0$. In ... more >>>

TR10-010 | 16th January 2010
Shachar Lovett

Equivalence of polynomial conjectures in additive combinatorics

We study two conjectures in additive combinatorics. The first is the polynomial Freiman-Ruzsa conjecture, which relates to the structure of sets with small doubling. The second is the inverse Gowers conjecture for $U^ $, which relates to functions which locally look like quadratics. In both cases a weak form, with ... more >>>

TR09-118 | 18th November 2009
Shachar Lovett, Ido Ben-Eliezer, Ariel Yadin

Title: Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness

Revisions: 1

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 of this model.
Our first result shows that low-degree polynomial threshold functions cannot approximate any function with many influential variables. We ... more >>>

TR09-088 | 29th September 2009
Shachar Lovett, Yoav Tzur

Explicit lower bound for fooling polynomials by the sum of small-bias generators

Recently, Viola (CCC'08) showed that the sum of $d$ small-biased distributions fools degree-$d$ polynomial tests; that is, every polynomial expression of degree at most $d$ in the bits of the sum has distribution very close to that induced by this expression evaluated on uniformly selected random bits. We show that ... more >>>

TR09-048 | 29th May 2009
Parikshit Gopalan, Shachar Lovett, Amir Shpilka

On the Complexity of Boolean Functions in Different Characteristics

Every Boolean function on $n$ variables can be expressed as a unique multivariate polynomial modulo $p$ for every prime $p$. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We establish the following general principle: functions with low degree ... more >>>

TR09-030 | 5th April 2009
Shachar Lovett

The density of weights of Generalized Reed-Muller codes

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 consider the case of fixed degree $r$, when we let the number of variables $m$ tend to infinity. We ... 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 >>>

TR08-080 | 3rd July 2008
Ido Ben-Eliezer, Rani Hod, Shachar Lovett

Random low degree polynomials are hard to approximate

Revisions: 1

We study the problem of how well a typical multivariate polynomial can be approximated by lower degree polynomials over $\F$.
We prove that, with very high probability, a random degree $d$ polynomial has only an exponentially small correlation with all polynomials of degree $d-1$, for all degrees $d$ up to ... 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 >>>

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-090 | 11th September 2007
Shachar Lovett

Tight lower bounds for adaptive linearity tests

Revisions: 1 , Comments: 1

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 linear. Linearity tests were first introduced by Blum, Luby and Rubenfeld in \cite{BLR93}, and were later used in the ... 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-012 | 22nd January 2007
Shachar Lovett, Sasha Sodin

Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits

Revisions: 1

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 by Artstein--Avidan and Milman, we prove that
such a subspace can be generated using $O(N)$ random bits.

... more >>>

ISSN 1433-8092 | Imprint