All reports by Author Shachar Lovett:

__
TR23-003
| 11th January 2023
__

Shachar Lovett, Jiapeng Zhang#### Streaming Lower Bounds and Asymmetric Set-Disjointness

__
TR22-107
| 20th July 2022
__

Shachar Lovett, Jiapeng Zhang#### Fractional certificates for bounded functions

__
TR21-169
| 24th November 2021
__

Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett#### Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments

__
TR20-170
| 9th November 2020
__

Max Hopkins, Tali Kaufman, Shachar Lovett#### High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games

Revisions: 1

__
TR20-155
| 18th October 2020
__

Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan#### Log-rank and lifting for AND-functions

Revisions: 1

__
TR20-048
| 16th April 2020
__

Shachar Lovett, Raghu Meka, Jiapeng Zhang#### Improved lifting theorems via robust sunflowers

__
TR19-137
| 24th September 2019
__

Shachar Lovett, Kewen Wu, Jiapeng Zhang#### Decision list compression by mild random restrictions

Revisions: 1

__
TR18-190
| 5th November 2018
__

Shachar Lovett, Jiapeng Zhang#### DNF sparsification beyond sunflowers

__
TR18-169
| 18th September 2018
__

Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev#### Optimality of Linear Sketching under Modular Updates

__
TR18-082
| 21st April 2018
__

Xin Li, Shachar Lovett, Jiapeng Zhang#### Sunflowers and Quasi-sunflowers from Randomness Extractors

__
TR18-074
| 23rd April 2018
__

Daniel Kane, Shachar Lovett, Shay Moran#### Generalized comparison trees for point-location problems

__
TR18-047
| 7th March 2018
__

Shachar Lovett#### A proof of the GM-MDS conjecture

Revisions: 1

__
TR18-015
| 25th January 2018
__

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett#### Pseudorandom Generators from Polarizing Random Walks

Revisions: 1
,
Comments: 1

__
TR17-085
| 4th May 2017
__

Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang#### Active classification with comparison queries

__
TR17-082
| 4th May 2017
__

Daniel Kane, Shachar Lovett, Shay Moran#### Near-optimal linear decision trees for k-SUM and related problems

__
TR17-070
| 15th April 2017
__

Shachar Lovett, Sankeerth Rao Karingula, Alex Vardy#### Probabilistic Existence of Large Sets of Designs

__
TR17-033
| 19th February 2017
__

Daniel Kane, Shachar Lovett, Sankeerth Rao Karingula#### Labeling the complete bipartite graph with no zero cycles

Revisions: 2

__
TR16-161
| 26th October 2016
__

Shachar Lovett, Jiapeng Zhang#### Robust sensitivity

Revisions: 1

__
TR16-118
| 31st July 2016
__

Shachar Lovett, Jiapeng Zhang#### On the impossibility of entropy reversal, and its application to zero-knowledge proofs

__
TR16-044
| 21st March 2016
__

Kaave Hosseini, Shachar Lovett#### Structure of protocols for XOR functions

Revisions: 1

__
TR16-025
| 26th February 2016
__

Shachar Lovett#### The Fourier structure of low degree polynomials

Revisions: 1

__
TR16-021
| 11th February 2016
__

Shachar Lovett, Jiapeng Zhang#### Noisy Population Recovery from Unknown Noise

__
TR15-190
| 2nd November 2015
__

Esther Ezra, Shachar Lovett#### On the Beck-Fiala Conjecture for Random Set Systems

__
TR15-179
| 10th November 2015
__

Divesh Aggarwal, Kaave Hosseini, Shachar Lovett#### Affine-malleable Extractors, Spectrum Doubling, and Application to Privacy Amplification

__
TR15-172
| 3rd November 2015
__

Benny Applebaum, Shachar Lovett#### Algebraic Attacks against Random Local Functions and Their Countermeasures

Revisions: 1

__
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

__
TR14-175
| 15th December 2014
__

Abhishek Bhowmick, Shachar Lovett#### Nonclassical polynomials as a barrier to polynomial lower bounds

__
TR14-147
| 6th November 2014
__

Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman#### Rectangles Are Nonnegative Juntas

Revisions: 1

__
TR14-141
| 24th October 2014
__

Shachar Lovett#### Linear codes cannot approximate the network capacity within any constant factor

__
TR14-123
| 7th October 2014
__

Shachar Lovett, Jiapeng Zhang#### Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions

__
TR14-087
| 12th July 2014
__

Abhishek Bhowmick, Shachar Lovett#### List decoding Reed-Muller codes over small fields

Revisions: 1

__
TR14-073
| 14th May 2014
__

Shachar Lovett, Cris Moore, Alexander Russell#### Group representations that resist random sampling

Revisions: 1

__
TR14-041
| 31st March 2014
__

Shachar Lovett#### Recent advances on the log-rank conjecture in communication complexity

__
TR14-040
| 30th March 2014
__

Hamed Hatami, Pooya Hatami, Shachar Lovett#### General systems of linear forms: equidistribution and true complexity

Revisions: 1

__
TR14-024
| 19th February 2014
__

Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider#### 0-1 Integer Linear Programming with a Linear Number of Constraints

__
TR13-126
| 11th September 2013
__

Arman Fazeli, Shachar Lovett, Alex Vardy#### Nontrivial t-designs over finite fields exist for all t

__
TR13-087
| 4th June 2013
__

Hamed Hatami, Shachar Lovett#### Estimating the distance from testable affine-invariant properties

__
TR13-084
| 8th June 2013
__

Shachar Lovett#### Communication is bounded by root of rank

Revisions: 1

__
TR13-081
| 6th June 2013
__

Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett#### Non-malleable Codes from Additive Combinatorics

__
TR13-080
| 4th June 2013
__

Dmytro Gavinsky, Shachar Lovett#### En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations

__
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

__
TR12-180
| 21st December 2012
__

Chaim Even-Zohar, Shachar Lovett#### The Freiman-Ruzsa Theorem in Finite Fields

__
TR12-051
| 25th April 2012
__

Dmytro Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan#### A Tail Bound for Read-k Families of Functions

__
TR12-042
| 17th April 2012
__

Chris Beck, Russell Impagliazzo, Shachar Lovett#### Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits

__
TR12-034
| 5th April 2012
__

Abhishek Bhowmick, Zeev Dvir, Shachar Lovett#### New Lower Bounds for Matching Vector Codes

Revisions: 5

__
TR12-029
| 3rd April 2012
__

Shachar Lovett#### An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem

__
TR12-001
| 1st January 2012
__

Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett#### Testing Low Complexity Affine-Invariant Properties

__
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

__
TR11-144
| 2nd November 2011
__

Greg Kuperberg, Shachar Lovett, Ron Peled#### Probabilistic existence of rigid combinatorial structures

__
TR11-139
| 26th October 2011
__

Zeev Dvir, Shachar Lovett#### Subspace Evasive Sets

__
TR11-094
| 20th June 2011
__

Shachar Lovett#### Computing polynomials with few multiplications

__
TR11-049
| 9th April 2011
__

Noga Alon, Shachar Lovett#### Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions

__
TR11-048
| 10th April 2011
__

Arkadev Chattopadhyay, Shachar Lovett#### Linear systems over abelian groups

__
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

__
TR10-182
| 26th November 2010
__

Shachar Lovett#### An elementary proof of anti-concentration of polynomials in Gaussian variables

__
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

__
TR10-115
| 17th July 2010
__

Shachar Lovett, Emanuele Viola#### Bounded-depth circuits cannot sample good codes

__
TR10-087
| 17th May 2010
__

Shachar Lovett, Ely Porat#### A lower bound for dynamic approximate membership data structures

__
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

__
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

__
TR10-010
| 16th January 2010
__

Shachar Lovett#### Equivalence of polynomial conjectures in additive combinatorics

__
TR09-118
| 18th November 2009
__

Shachar Lovett, Ido Ben-Eliezer, Ariel Yadin#### Title: Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness

Revisions: 1

__
TR09-088
| 29th September 2009
__

Shachar Lovett, Yoav Tzur#### Explicit lower bound for fooling polynomials by the sum of small-bias generators

__
TR09-048
| 29th May 2009
__

Parikshit Gopalan, Shachar Lovett, Amir Shpilka#### On the Complexity of Boolean Functions in Different Characteristics

__
TR09-030
| 5th April 2009
__

Shachar Lovett#### The density of weights of Generalized Reed-Muller codes

__
TR08-111
| 14th November 2008
__

Shachar Lovett, Tali Kaufman#### The List-Decoding Size of Reed-Muller Codes

Revisions: 2

__
TR08-080
| 3rd July 2008
__

Ido Ben-Eliezer, Rani Hod, Shachar Lovett#### Random low degree polynomials are hard to approximate

Revisions: 1

__
TR08-072
| 11th August 2008
__

Shachar Lovett, Tali Kaufman#### Worst case to Average case reductions for polynomials

__
TR07-123
| 21st November 2007
__

Shachar Lovett, Roy Meshulam, Alex Samorodnitsky#### Inverse Conjecture for the Gowers norm is false

Revisions: 2

__
TR07-090
| 11th September 2007
__

Shachar Lovett#### Tight lower bounds for adaptive linearity tests

Revisions: 1
,
Comments: 1

__
TR07-075
| 9th August 2007
__

Shachar Lovett#### Unconditional pseudorandom generators for low degree polynomials

__
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

Shachar Lovett, Jiapeng Zhang

Frequency estimation in data streams is one of the classical problems in streaming algorithms. Following much research, there are now almost matching upper and lower bounds for the trade-off needed between the number of samples and the space complexity of the algorithm, when the data streams are adversarial. However, in ... more >>>

Shachar Lovett, Jiapeng Zhang

A folklore conjecture in quantum computing is that the acceptance probability of a quantum query algorithm can be approximated by a classical decision tree, with only a polynomial increase in the number of queries. Motivated by this conjecture, Aaronson and Ambainis (Theory of Computing, 2014) conjectured that this should hold ... more >>>

Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett

Hypercontractivity is one of the most powerful tools in Boolean function analysis. Originally studied over the discrete hypercube, recent years have seen increasing interest in extensions to settings like the $p$-biased cube, slice, or Grassmannian, where variants of hypercontractivity have found a number of breakthrough applications including the resolution of ... more >>>

Max Hopkins, Tali Kaufman, Shachar Lovett

Higher order random walks (HD-walks) on high dimensional expanders have played a crucial role in a number of recent breakthroughs in theoretical computer science, perhaps most famously in the recent resolution of the Mihail-Vazirani conjecture (Anari et al. STOC 2019), which focuses on HD-walks on one-sided local-spectral expanders. In this ... more >>>

Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan

Let $f: \{0,1\}^n \to \{0, 1\}$ be a boolean function, and let $f_\land (x, y) = f(x \land y)$ denote the AND-function of $f$, where $x \land y$ denotes bit-wise AND. We study the deterministic communication complexity of $f_\land$ and show that, up to a $\log n$ factor, it is ... more >>>

Shachar Lovett, Raghu Meka, Jiapeng Zhang

Lifting theorems are a generic way to lift lower bounds in query complexity to lower bounds in communication complexity, with applications in diverse areas, such as combinatorial optimization, proof complexity, game theory. Lifting theorems rely on a gadget, where smaller gadgets give stronger lower bounds. However, existing proof techniques are ... more >>>

Shachar Lovett, Kewen Wu, Jiapeng Zhang

A decision list is an ordered list of rules. Each rule is specified by a term, which is a conjunction of literals, and a value. Given an input, the output of a decision list is the value corresponding to the first rule whole term is satisfied by the input. Decision ... more >>>

Shachar Lovett, Jiapeng Zhang

There are two natural complexity measures associated with DNFs: their size, which is the number of clauses; and their width, which is the maximal number of variables in a clause. It is a folklore result that DNFs of small size can be approximated by DNFs of small width (logarithmic in ... more >>>

Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev

We study the relation between streaming algorithms and linear sketching algorithms, in the context of binary updates. We show that for inputs in $n$ dimensions,

the existence of efficient streaming algorithms which can process $\Omega(n^2)$ updates implies efficient linear sketching algorithms with comparable cost.

This improves upon the previous work ...
more >>>

Xin Li, Shachar Lovett, Jiapeng Zhang

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

Daniel Kane, Shachar Lovett, Shay Moran

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

Shachar Lovett

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.

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett

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

Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang

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

Daniel Kane, Shachar Lovett, Shay Moran

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

Shachar Lovett, Sankeerth Rao Karingula, Alex Vardy

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

Daniel Kane, Shachar Lovett, Sankeerth Rao Karingula

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

Shachar Lovett, Jiapeng Zhang

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

Shachar Lovett, Jiapeng Zhang

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

Kaave Hosseini, Shachar Lovett

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

Shachar Lovett

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

Shachar Lovett, Jiapeng Zhang

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

Esther Ezra, Shachar Lovett

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

Divesh Aggarwal, Kaave Hosseini, Shachar Lovett

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

Benny Applebaum, Shachar Lovett

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

Abhishek Bhowmick, Shachar Lovett

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

Abhishek Bhowmick, Shachar Lovett

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

Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman

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

Shachar Lovett

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

Shachar Lovett, Jiapeng Zhang

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

Abhishek Bhowmick, Shachar Lovett

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

Shachar Lovett, Cris Moore, Alexander Russell

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

Shachar Lovett

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

Hamed Hatami, Pooya Hatami, Shachar Lovett

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

Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider

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

Arman Fazeli, Shachar Lovett, Alex Vardy

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

Hamed Hatami, Shachar Lovett

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

Shachar Lovett

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

Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett

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

Dmytro Gavinsky, Shachar Lovett

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

Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett

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

Chaim Even-Zohar, Shachar Lovett

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

Dmytro Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan

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 >>>Chris Beck, Russell Impagliazzo, Shachar Lovett

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

Abhishek Bhowmick, Zeev Dvir, Shachar Lovett

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

Shachar Lovett

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

Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett

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

Eli Ben-Sasson, Shachar Lovett, Noga Ron-Zewi

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

Greg Kuperberg, Shachar Lovett, Ron Peled

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

Zeev Dvir, Shachar Lovett

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

Shachar Lovett

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

Noga Alon, Shachar Lovett

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

Arkadev Chattopadhyay, Shachar Lovett

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

Hamed Hatami, Shachar Lovett

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

Shachar Lovett

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

Hamed Hatami, Shachar Lovett

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

Shachar Lovett, Emanuele Viola

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

Shachar Lovett, Ely Porat

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

Tali Kaufman, Shachar Lovett

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

Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka

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

Shachar Lovett

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

Shachar Lovett, Ido Ben-Eliezer, Ariel Yadin

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

Shachar Lovett, Yoav Tzur

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

Parikshit Gopalan, Shachar Lovett, Amir Shpilka

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

Shachar Lovett

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

Shachar Lovett, Tali Kaufman

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

Ido Ben-Eliezer, Rani Hod, Shachar Lovett

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

Shachar Lovett, Tali Kaufman

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

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_p^N \to \F_p$ is non-negligible, that is larger than a constant independent of $N$, then $f$ can be non-trivially ...
more >>>

Shachar Lovett

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

Shachar Lovett

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

Shachar Lovett, Sasha Sodin

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.