Shachar Lovett

FOCS Conference 2025 Conference Paper

Quasipolynomial Bounds for the Corners Theorem

• Michael Jaber
• Yang P. Liu
• Shachar Lovett
• Anthony Ostuni
• Mehtaab Sawhney

Let G be a finite abelian group and A be a subset of $G \times G$ which is corner-free, meaning that there are no $x, y \in G$ and $d \in G \backslash\{0\}$ such that $(x, y), (x+d, y), (x, y+d) \in A$. We prove that \begin{equation*}|A| \leq|G|^{2} \cdot \exp \left(-(\log |G|)^{\Omega{1}}\right)\end{equation*}As a consequence, we obtain polynomial (in the input length) lower bounds on the non-deterministic communication complexity of Exactly-N in the 3-player Number-on-Forehead model. We also obtain the first “reasonable” lower bounds on the coloring version of the 3 -dimensional corners problem, as well as on the non-deterministic communication complexity of Exactly-N in the 4-player Number-on-Forehead model. This is an extended abstract. The full version of the paper can be found at https: //arxiv. org/abs/2504. 07006.

STOC Conference 2024 Conference Paper

Explicit Separations between Randomized and Deterministic Number-on-Forehead Communication

• Zander Kelley
• Shachar Lovett
• Raghu Meka

We study the power of randomness in the Number-on-Forehead (NOF) model in communication complexity. We construct an explicit 3-player function f :[ N ] 3 → {0,1}, such that: (i) there exist a randomized NOF protocol computing it that sends a constant number of bits; but (ii) any deterministic or nondeterministic NOF protocol computing it requires sending about (log N ) 1/3 many bits. This exponentially improves upon the previously best-known such separation. At the core of our proof is an extension of a recent result on sets of integers without 3-term arithmetic progressions into a non-arithmetic setting.

STOC Conference 2024 Conference Paper

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms

• Amir Abboud
• Nick Fischer
• Zander Kelley
• Shachar Lovett
• Raghu Meka

We revisit the fundamental Boolean Matrix Multiplication (BMM) problem. With the invention of algebraic fast matrix multiplication over 50 years ago, it also became known that BMM can be solved in truly subcubic O ( n ω ) time, where ω<3; much work has gone into bringing ω closer to 2. Since then, a parallel line of work has sought comparably fast combinatorial algorithms but with limited success. The na'ive O ( n 3 )-time algorithm was initially improved by a log 2 n factor [Arlazarov et al.; RAS’70], then by log 2.25 n [Bansal and Williams; FOCS’09], then by log 3 n [Chan; SODA’15], and finally by log 4 n [Yu; ICALP’15]. We design a combinatorial algorithm for BMM running in time n 3 / 2 Ω((log n ) 1/7 ) – a speed-up over cubic time that is stronger than any poly-log factor. This comes tantalizingly close to refuting the conjecture from the 90s that truly subcubic combinatorial algorithms for BMM are impossible. This popular conjecture is the basis for dozens of fine-grained hardness results. Our main technical contribution is a new regularity decomposition theorem for Boolean matrices (or equivalently, bipartite graphs) under a notion of regularity that was recently introduced and analyzed analytically in the context of communication complexity [Kelley, Lovett, Meka; STOC’24], and is related to a similar notion from the recent work on 3-term arithmetic progression free sets [Kelley, Meka; FOCS’23].

SODA Conference 2023 Conference Paper

Sampling Equilibria: Fast No-Regret Learning in Structured Games

• Daniel Beaglehole
• Max Hopkins
• Daniel M. Kane
• Sihan Liu
• Shachar Lovett

Learning and equilibrium computation in games are fundamental problems across computer science and economics, with applications ranging from politics to machine learning. Much of the work in this area revolves around a simple algorithm termed randomized weighted majority (RWM), also known as “Hedge” or “Multiplicative Weights Update, ” which is well known to achieve statistically optimal rates in adversarial settings (Littlestone and Warmuth '94, Freund and Schapire '99). Unfortunately, RWM comes with an inherent computational barrier: it requires maintaining and sampling from a distribution over all possible actions. In typical settings of interest the action space is exponentially large, seemingly rendering RWM useless in practice. In this work, we refute this notion for a broad variety of structured games, showing it is possible to efficiently (approximately) sample the action space in RWM in polylogarithmic time. This gives the first efficient no-regret algorithms for problems such as the ( discrete ) Colonel Blotto game, matroid congestion, matroid security, and basic dueling games. As an immediate corollary, we give a polylogarithmic time meta-algorithm to compute approximate Nash Equilibria for these games that is exponentially faster than prior methods in several important settings. Further, our algorithm is the first to efficiently compute equilibria for more involved variants of these games with general sums, more than two players, and, for Colonel Blotto, multiple resource types. Our results also greatly generalize earlier work on efficient RWM-based techniques for exponential strategy sets from (Cesa-Bianchi and Lugosi '09).

FOCS Conference 2023 Conference Paper

Streaming Lower Bounds and Asymmetric Set-Disjointness

• 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 the case where the data stream is given in a random order, or is stochastic, only weaker lower bounds exist. In this work we close this gap, up to logarithmic factors. In order to do so we consider the needle problem, which is a natural hard problem for frequency estimation studied in (Andoni et al. 2008, Crouch et al. 2016). Here, the goal is to distinguish between two distributions over data streams with t samples. The first is uniform over a large enough domain. The second is a planted model; a secret “needle“ is uniformly chosen, and then each element in the stream equals the needle with probability p, and otherwise is uniformly chosen from the domain. It is simple to design streaming algorithms that distinguish the distributions using space $s \approx 1 /\left(p^{2} t\right)$. It was unclear if this is tight, as the existing lower bounds are weaker. We close this gap and show that the trade-off is near optimal, up to a logarithmic factor. Our proof builds and extends classical connections between streaming algorithms and communication complexity, concretely multi-party unique set-disjointness. We introduce two new ingredients that allow us to prove sharp bounds. The first is a lower bound for an asymmetric version of multi-party unique set-disjointness, where players receive input sets of different sizes, and where the communication of each player is normalized relative to their input length. The second is a combinatorial technique that allows to sample needles in the planted model by first sampling intervals, and then sampling a uniform needle in each interval.

SODA Conference 2022 Conference Paper

High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games

• Mitali Bafna
• Max Hopkins
• Tali Kaufman
• Shachar Lovett

Higher order random walks (HD-walks) on high dimensional expanders (HDX) have seen an incredible amount of study and application since their introduction by Kaufman and Mass (ITCS 2016), yet their broader combinatorial and spectral properties remain poorly understood. We develop a combinatorial characterization of the spectral structure of HD-walks on two-sided local-spectral expanders (Dinur and Kaufman FOCS 2017), which offer a broad generalization of the well-studied Johnson and Grassmann graphs. Our characterization, which shows that the spectra of HD-walks lie tightly concentrated in a few combinatorially structured strips, leads to novel structural theorems such as a tight ℓ 2 -characterization of edge-expansion, as well as to a new understanding of local-to-global graph algorithms on HDX. Towards the latter, we introduce a novel spectral complexity measure called Stripped Threshold Rank, and show how it can replace the (much larger) threshold rank as a parameter controlling the performance of algorithms on structured objects. Combined with a sum-of-squares proof for the former ℓ 2 -characterization, we give a concrete application of this framework to algorithms for unique games on HD-walks, where in many cases we improve the state of the art (Barak, Raghavendra, and Steurer FOCS 2011, and Arora, Barak, and Steurer JACM 2015) from nearly-exponential to polynomial time (e. g. for sparsifications of Johnson graphs or of slices of the q -ary hypercube). Our characterization of expansion also holds an interesting connection to hardness of approximation, where an ℓ ∞ -variant for the Grassmann graphs was recently used to resolve the 2-2 Games Conjecture (Khot, Minzer, and Safra FOCS 2018). We give a reduction from a related ℓ ∞ -variant to our ℓ 2 -characterization, but it loses factors in the regime of interest for hardness where the gap between ℓ 2 and ℓ ∞ structure is large. Nevertheless, our results open the door for further work on the use of HDX in hardness of approximation and their general relation to unique games.

STOC Conference 2022 Conference Paper

Hypercontractivity on high dimensional expanders

• 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 Khot’s 2-2 Games Conjecture (Khot, Minzer, Safra FOCS 2018). In this work, we develop a new theory of hypercontractivity on high dimensional expanders (HDX), an important class of expanding complexes that has recently seen similarly impressive applications in both coding theory and approximate sampling. Our results lead to a new understanding of the structure of Boolean functions on HDX, including a tight analog of the KKL Theorem and a new characterization of non-expanding sets. Unlike previous settings satisfying hypercontractivity, HDX can be asymmetric, sparse, and very far from products, which makes the application of traditional proof techniques challenging. We handle these barriers with the introduction of two new tools of independent interest: a new explicit combinatorial Fourier basis for HDX that behaves well under restriction, and a new local-to-global method for analyzing higher moments. Interestingly, unlike analogous second moment methods that apply equally across all types of expanding complexes, our tools rely inherently on simplicial structure. This suggests a new distinction among high dimensional expanders based upon their behavior beyond the second moment. This is an extended abstract. The full paper may be found at https://arxiv.org/abs/2111.09444.

ICML Conference 2021 Conference Paper

Bilinear Classes: A Structural Framework for Provable Generalization in RL

• Simon S. Du
• Sham M. Kakade
• Jason D. Lee
• Shachar Lovett
• Gaurav Mahajan
• Wen Sun 0002
• Ruosong Wang

This work introduces Bilinear Classes, a new structural framework, which permit generalization in reinforcement learning in a wide variety of settings through the use of function approximation. The framework incorporates nearly all existing models in which a polynomial sample complexity is achievable, and, notably, also includes new models, such as the Linear Q*/V* model in which both the optimal Q-function and the optimal V-function are linear in some known feature space. Our main result provides an RL algorithm which has polynomial sample complexity for Bilinear Classes; notably, this sample complexity is stated in terms of a reduction to the generalization error of an underlying supervised learning sub-problem. These bounds nearly match the best known sample complexity bounds for existing models. Furthermore, this framework also extends to the infinite dimensional (RKHS) setting: for the the Linear Q*/V* model, linear MDPs, and linear mixture MDPs, we provide sample complexities that have no explicit dependence on the explicit feature dimension (which could be infinite), but instead depends only on information theoretic quantities.

STOC Conference 2021 Conference Paper

Log-rank and lifting for AND-functions

• Alexander Knop
• Shachar Lovett
• Sam McGuire
• Weiqiang Yuan 0002

Let f : {0, 1} n → {0, 1} be a boolean function, and let f ∧ ( x , y ) = f ( x ∧ y ) denote the AND-function of f , where x ∧ y denotes bit-wise AND. We study the deterministic communication complexity of f ∧ and show that, up to a log n factor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix of f ∧ . This comes within a log n factor of establishing the log-rank conjecture for AND-functions with no assumptions on f . Our result stands in contrast with previous results on special cases of the log-rank conjecture, which needed significant restrictions on f such as monotonicity or low F 2 -degree. Our techniques can also be used to prove (within a log n factor) a lifting theorem for AND-functions, stating that the deterministic communication complexity of f ∧ is polynomially related to the AND-decision tree complexity of f .

STOC Conference 2020 Conference Paper

Decision list compression by mild random restrictions

• Shachar Lovett
• Kewen Wu 0001
• 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 whose term is satisfied by the input. Decision lists generalize both CNFs and DNFs, and have been studied both in complexity theory and in learning theory.

STOC Conference 2020 Conference Paper

Improved bounds for the sunflower lemma

• Ryan Alweiss
• Shachar Lovett
• Kewen Wu 0001
• Jiapeng Zhang

A sunflower with r petals is a collection of r sets so that the intersection of each pair is equal to the intersection of all. Erdős and Rado proved the sunflower lemma: for any fixed r , any family of sets of size w , with at least about w w sets, must contain a sunflower. The famous sunflower conjecture is that the bound on the number of sets can be improved to c w for some constant c . In this paper, we improve the bound to about (log w ) w . In fact, we prove the result for a robust notion of sunflowers, for which the bound we obtain is tight up to lower order terms.

FOCS Conference 2020 Conference Paper

Point Location and Active Learning: Learning Halfspaces Almost Optimally

• Max Hopkins
• Daniel M. Kane
• Shachar Lovett
• Gaurav Mahajan

Given a finite set X ⊂ R d and a binary linear classifier c: R d → {0, 1}, how many queries of the form c(x) are required to learn the label of every point in X? Known as point location, this problem has inspired over 35 years of research in the pursuit of an optimal algorithm. Building on the prior work of Kane, Lovett, and Moran (ICALP 2018), we provide the first nearly optimal solution, a randomized linear decision tree of depth Õ(dlog(|X|)), improving on the previous best of Õ(d 2 log(|X|)) from Ezra and Sharir (Discrete and Computational Geometry, 2019). As a corollary, we also provide the first nearly optimal algorithm for actively learning halfspaces in the membership query model. En route to these results, building on the work of Carlen, Lieb, and Loss (J. Geometric Analysis 2004), as well as Dvir, Saraf, and Wigderson (STOC 2014), we prove a novel characterization of Barthe's Theorem (Inventiones Mathematicae, 1998) of independent interest. In particular, we show that X may be transformed into approximate isotropic position if and only if there exists no k-dimensional subspace with more than a k/d-fraction of X, and provide a similar characterization for exact isotropic position. The below is an extended abstract. The full work can be found at https: //arxiv. org/abs/2004. 11380.

NeurIPS Conference 2020 Conference Paper

The Power of Comparisons for Actively Learning Linear Classifiers

• Max Hopkins
• Daniel Kane
• Shachar Lovett

In the world of big data, large but costly to label datasets dominate many fields. Active learning, a semi-supervised alternative to the standard PAC-learning model, was introduced to explore whether adaptive labeling could learn concepts with exponentially fewer labeled samples. While previous results show that active learning performs no better than its supervised alternative for important concept classes such as linear separators, we show that by adding weak distributional assumptions and allowing comparison queries, active learning requires exponentially fewer samples. Further, we show that these results hold as well for a stronger model of learning called Reliable and Probably Useful (RPU) learning. In this model, our learner is not allowed to make mistakes, but may instead answer ``I don't know. '' While previous negative results showed this model to have intractably large sample complexity for label queries, we show that comparison queries make RPU-learning at worst logarithmically more expensive in both the passive and active regimes.

NeurIPS Conference 2020 Conference Paper

Towards a Combinatorial Characterization of Bounded-Memory Learning

• Alon Gonen
• Shachar Lovett
• Michal Moshkovitz

Combinatorial dimensions play an important role in the theory of machine learning. For example, VC dimension characterizes PAC learning, SQ dimension characterizes weak learning with statistical queries, and Littlestone dimension characterizes online learning. In this paper we aim to develop combinatorial dimensions that characterize bounded memory learning. We propose a candidate solution for the case of realizable strong learning under a known distribution, based on the SQ dimension of neighboring distributions. We prove both upper and lower bounds for our candidate solution, that match in some regime of parameters. This is the first characterization of strong learning under space constraints in any regime. In this parameter regime there is an equivalence between bounded memory and SQ learning. We conjecture that our characterization holds in a much wider regime of parameters.

STOC Conference 2020 Conference Paper

XOR lemmas for resilient functions against polynomials

• Eshan Chattopadhyay
• Pooya Hatami
• Kaave Hosseini
• Shachar Lovett
• David Zuckerman

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 fact, we prove a more general XOR lemma that extends to arbitrary resilient functions. We conjecture that the technique generalizes to higher degree polynomials as well. A key ingredient in our new approach is a structural result about the Fourier spectrum of low degree polynomials over F 2 . We show that for any n -variate polynomial p over F 2 of degree at most d , there is a small set S ⊂ [ n ] of variables, such that almost all of the Fourier mass of p lies on Fourier coefficients that intersect with S . In fact our result is more general, and finds such a set S for any low-dimensional subspace of polynomials. This generality is crucial in deriving the new XOR lemmas.

STOC Conference 2019 Conference Paper

DNF sparsification beyond sunflowers

• 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 the size). The other direction is much less clear.

FOCS Conference 2018 Conference Paper

MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture

• Shachar Lovett

An MDS matrix is a matrix whose minors all have full rank. A question arising in coding theory is, what zero patterns can MDS matrices have. There is a natural combinatorial necessary condition (called the MDS condition) which is necessary over any field, and sufficient over very large fields by a probabilistic argument. Dau et al. (ISIT 2014) conjectured that the MDS condition is sufficient over small fields as well, and gave an algebraic conjecture which would imply this. In this work, we prove this conjecture.

STOC Conference 2018 Conference Paper

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

• Daniel M. 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 queries, which compare the sums of two k -subsets; when viewed as linear queries, comparison queries are 2 k -sparse and have only {−1,0,1} coefficients. We give similar constructions for sorting sumsets A + B and for solving the SUBSET-SUM problem, both with optimal number of queries, up to poly-logarithmic terms. Our constructions are based on the notion of “inference dimension”, recently introduced by the authors in the context of active classification with comparison queries. This can be viewed as another contribution to the fruitful link between machine learning and discrete geometry, which goes back to the discovery of the VC dimension.

SODA Conference 2018 Conference Paper

Probabilistic Existence of Large Sets of Designs

• Shachar Lovett
• Sankeerth Rao
• Alexander Vardy

STOC Conference 2018 Conference Paper

The gram-schmidt walk: a cure for the Banaszczyk blues

• Nikhil Bansal 0001
• Daniel Dadush
• Shashwat Garg
• Shachar Lovett

An important result in discrepancy due to Banaszczyk states that for any set of n vectors in ℝ m of ℓ 2 norm at most 1 and any convex body K in ℝ m of Gaussian measure at least half, there exists a ± 1 combination of these vectors which lies in 5 K . This result implies the best known bounds for several problems in discrepancy. Banaszczyk’s proof of this result is non-constructive and an open problem has been to give an efficient algorithm to find such a ± 1 combination of the vectors.

SODA Conference 2018 Conference Paper

The Robust Sensitivity of Boolean Functions

• Shachar Lovett
• Avishay Tal
• 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 the robust sensitivity conjecture in this work with near optimal parameters.

FOCS Conference 2017 Conference Paper

Active Classification with Comparison Queries

• Daniel M. 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 specific restaurant (a label query); or which one of two restaurants did she like more (a comparison query). We focus on the class of half spaces, and show that under natural assumptions, such as large margin or bounded bit-description of the input examples, it is possible to reveal all the labels of a sample of size n using approximately O(log n) queries. This implies an exponential improvement over classical active learning, where only label queries are allowed. We complement these results by showing that if any of these assumptions is removed then, in the worst case, Ω(n) queries are required. Our results follow from a new general framework of active learning with additional queries. We identify a combinatorial dimension, called the inference dimension, that captures the query complexity when each additional query is determined by O(1) examples (such as comparison queries, each of which is determined by the two compared examples). Our results for half spaces follow by bounding the inference dimension in the cases discussed above.

FOCS Conference 2017 Conference Paper

The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes

• Daniel M. Kane
• Shachar Lovett
• Sankeerth Rao

Maximally recoverable codes are codes designed for distributed storage which combine quick recovery from single node failure and optimal recovery from catastrophic failure. Gopalan et al [SODA 2017] studied the alphabet size needed for such codes in grid topologies and gave a combinatorial characterization for it. Consider a labeling of the edges of the complete bipartite graph K n, n with labels coming from F 2 d, that satisfies the following condition: for any simple cycle, the sum of the labels over its edges is nonzero. The minimal d where this is possible controls the alphabet size needed for maximally recoverable codes in n × n grid topologies. Prior to the current work, it was known that d is between log(n) 2 and n log n. We improve both bounds and show that d is linear in n. The upper bound is a recursive construction which beats the random construction. The lower bound follows by first relating the problem to the independence number of the Birkhoff polytope graph, and then providing tight bounds for it using the representation theory of the symmetric group.

STOC Conference 2016 Conference Paper

Algebraic attacks against random local functions and their countermeasures

• Benny Applebaum
• Shachar Lovett

Suppose that you have n truly random bits x =( x 1 ,…, x n ) and you wish to use them to generate m ≫ n pseudorandom bits y =( y 1 ,…, 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, originates from (Goldreich, ECCC 2000), is based on Random Local Functions : Compute y i by applying some fixed (public) d -ary predicate P to a random (public) tuple of distinct inputs ( x i 1 ,…, x i d ). Our goal in this paper is to understand, for any value of s , how the pseudorandomness of the resulting sequence depends on the choice of the underlying predicate. We derive the following results:

FOCS Conference 2016 Conference Paper

Structure of Protocols for XOR Functions

• Hamed Hatami
• Kaave Hosseini
• Shachar Lovett

Let f be a boolean function on n variables. Its associated XOR function is the two-party function F(x, y) = f(x xor y). We show that, up to polynomial factors, the deterministic communication complexity of F is equal to the parity decision tree complexity of f. This relies on a novel technique of entropy reduction for protocols, combined with existing techniques in Fourier analysis and additive combinatorics.

STOC Conference 2015 Conference Paper

Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions

• 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, estimate the original probability up to an additive error of ε. We give an algorithm which solves this problem in time polynomial in (k log log k , n, 1/ε). This improves on the previous algorithm of Wigderson and Yehudayoff [FOCS 2012] which solves the problem in time polynomial in (k log k , n, 1/ε). Our main technical contribution, which facilitates the algorithm, is a new reverse Bonami-Beckner inequality for the L 1 norm of sparse functions.

STOC Conference 2015 Conference Paper

Rectangles Are Nonnegative Juntas

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

We develop a new method to prove communication lower bounds for composed functions of the form f o 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 o g n can be simulated by a nonnegative combination of juntas. This is the strongest yet formalization for the intuition that each low-communication randomized protocol can only "query" few inputs of f as encoded by the gadget g. Consequently, we characterize the communication complexity of f o g n in all known one-sided zero-communication models by a corresponding query complexity measure of f. These models in turn capture important lower bound techniques such as corruption, smooth rectangle bound, relaxed partition bound, and extended discrepancy. As applications, we resolve several open problems from prior work: We show that SBPcc (a class characterized by corruption) is not closed under intersection. An immediate corollary is that MAcc ≠ SBPcc. These results answer questions of Klauck (CCC 2003) and Bohler et al. (JCSS 2006). We also show that approximate nonnegative rank of partial boolean matrices does not admit efficient error reduction. This answers a question of Kol et al. (ICALP) for partial matrices.

STOC Conference 2015 Conference Paper

The List Decoding Radius of Reed-Muller Codes over Small Fields

• Abhishek Bhowmick 0001
• 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 F. The Reed-Muller code RM F (n,d) is defined by n-variate degree-d polynomials over F. In this work, we study the list decoding radius of Reed-Muller codes over a constant prime field F=F p , constant degree d and large n. We show that the list decoding radius is equal to the minimal distance of the code. That is, if we denote by δ(d) the normalized minimal distance of RM F (n,d), then the number of codewords in any ball of radius δ(d)-ε is bounded by c=c(p,d,ε) independent of n. This resolves a conjecture of Gopalan-Klivans-Zuckerman [STOC 2008], who among other results proved it in the special case of F=F 2 ; and extends the work of Gopalan [FOCS 2010] who proved the conjecture in the case of d=2. We also analyse the number of codewords in balls of radius exceeding the minimal distance of the code. For e ≤ d, we show that the number of codewords of RM F (n,d) in a ball of radius δ(e) - ε is bounded by exp(c • n d-e ), where c=c(p,d,ε) is independent of n. The dependence on $n$ is tight. This extends the work of Kaufman-Lovett-Porat [IEEE Inf. Theory 2012] who proved similar bounds over F 2 . The proof relies on several new ingredients: an extension of the Frieze-Kannan weak regularity to general function spaces, higher-order Fourier analysis, and an extension of the Schwartz-Zippel-DeMillo-Lipton lemma to compositions of polynomials.

STOC Conference 2014 Conference Paper

Communication is bounded by root of rank

• Shachar Lovett

We prove that any total boolean function of rank r can be computed by a deterministic communication protocol of complexity O (√r · log(r)). Similarly, any graph whose adjacency matrix has rank r has chromatic number at most 2 O (√r · log(r)) . This gives a nearly quadratic improvement in the dependence on the rank over previous results.

STOC Conference 2014 Conference Paper

Non-malleable codes from additive combinatorics

• Divesh Aggarwal
• Yevgeniy Dodis
• Shachar Lovett

Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional errorcorrection (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 completely unrelated value. Although such codes do not exist if the family of "tampering functions" F is completely unrestricted, they are known to exist for many broad tampering families F . One such natural family is the family of tampering functions in the so called split-state model. Here the message m is encoded into two shares L and R , and the attacker is allowed to arbitrarily tamper with L and R individually . The split-state tampering arises in many realistic applications, such as the design of non-malleable secret sharing schemes , motivating the question of designing efficient non-malleable codes in this model.

FOCS Conference 2013 Conference Paper

Estimating the Distance from Testable Affine-Invariant Properties

• Hamed Hatami
• Shachar Lovett

Let P be an affine invariant property of multivariate functions over a constant size finite field. We show that if P is locally testable with a constant number of queries, then one can estimate the distance of a function f from P with a constant number of queries. This was previously unknown even for simple properties such as cubic polynomials over the binary field. Our test is simple: take a restriction of f to a constant dimensional affine subspace, and measure its distance from P. We show that by choosing the dimension large enough, this approximates with high probability the global distance of f from P. The analysis combines the approach of Fischer and Newman [SIAM J. Comp 2007] who established a similar result for graph properties, with recently developed tools in higher order Fourier analysis, in particular those developed in Bhattacharyya et al. [STOC 2013].

STOC Conference 2013 Conference Paper

Every locally characterized affine-invariant property is testable

• Arnab Bhattacharyya 0001
• Eldar Fischer
• Hamed Hatami
• Pooya Hatami
• Shachar Lovett

STOC Conference 2013 Conference Paper

New bounds for matching vector families

• Abhishek Bhowmick 0001
• Zeev Dvir
• Shachar Lovett

SODA Conference 2013 Conference Paper

Testing Low Complexity Affine-Invariant Properties

• Arnab Bhattacharyya 0001
• 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, for instance, that the Reed-Muller code over F p of degree d < p is testable, with an argument that uses no detailed algebraic information about polynomials, except that having low degree is preserved by composition with affine maps. The complexity of an affine-invariant property refers to the maximum complexity, as defined by Green and Tao (Ann. Math. 2008), of the sets of linear forms used to characterize. A more precise statement of our main result is that for any fixed prime p ≥ 2 and fixed integer R ≥ 2, any affine-invariant property of functions f: F n p → [ R ] is testable, if the complexity of the property is less than p. Our proof involves developing analogs of graph-theoretic techniques in an algebraic setting, using tools from higher-order Fourier analysis.

FOCS Conference 2012 Conference Paper

An Additive Combinatorics Approach Relating Rank to Communication Complexity

• 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. It is well-known since the work of Mehlhorn and Schmidt [STOC 1982] that CC(M) is bounded from above by rank(M) and from below by log rank(M) where rank(M) denotes the rank of M over the field of real numbers. Determining where in this range lies the true worst-case value of CC(M) is a fundamental open problem in communication complexity. The state of the art is log 1. 631 rank(M) ≤ CC(M) ≤ 0. 415 rank(M), the lower bound is by Kushilevitz [unpublished, 1995] and the upper bound is due to Kotlov [Journal of Graph Theory, 1996]. Lovasz and Saks [FOCS 1988] conjecture that CC(M) is closer to the lower bound, i. e. , CC(M)≤ log c rank(M)) for some absolute constant c - this is the famous "log-rank conjecture'' - but so far there has been no evidence to support it, even giving a slightly non-trivial (o(rank(M))) upper bound on the communication complexity. Our main result is that, assuming the Polynomial Freiman-Ruzsa (PFR) conjecture in additive combinatorics, there exists a universal constant c such that CC(M) ≤ c ·rank(M)/log rank(M). Although our bound is stated using the rank of M over the reals, our proof goes by studying the problem over the finite field of size 2, and there we bring to bear a number of new tools from additive combinatorics which we hope will facilitate further progress on this perplexing question. In more detail, our proof is based on the study of the "approximate duality conjecture'' which was suggested by Ben-Sasson and Zewi [STOC 2011] and studied there in connection to the PFR conjecture. First we improve the bounds on approximate duality assuming the PFR conjecture. Then we use the approximate duality conjecture (with improved bounds) to get our upper bound on the communication complexity of low-rank martices.

FOCS Conference 2012 Conference Paper

Constructive Discrepancy Minimization by Walking on the Edges

• Shachar Lovett
• Raghu Meka

Minimizing the discrepancy of a set system is a fundamental problem in combinatorics. One of the cornerstones in this area is the celebrated six standard deviations result of Spencer (AMS 1985): In any system of n sets in a universe of size n, there always exists a coloring which achieves discrepancy 6√n. The original proof of Spencer was existential in nature, and did not give an efficient algorithm to find such a coloring. Recently, a breakthrough work of Bansal (FOCS 2010) gave an efficient algorithm which finds such a coloring. His algorithm was based on an SDP relaxation of the discrepancy problem and a clever rounding procedure. In this work we give a new randomized algorithm to find a coloring as in Spencer's result based on a restricted random walk we call Edge-Walk. Our algorithm and its analysis use only basic linear algebra and is “truly” constructive in that it does not appeal to the existential arguments, giving a new proof of Spencer's theorem and the partial coloring lemma.

FOCS Conference 2012 Conference Paper

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

• Christopher 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 is, such distributions are very far from each other. We strengthen their result, and show that the distance is in fact exponentially close to one. This allows us to strengthen the parameters in their application for data structure lower bounds for succinct data structures for codes. From a technical point of view, we develop new large deviation bounds for functions computed by small depth decision trees, which we then apply to obtain bounds for AC0 circuits via the switching lemma. We show that if such functions are Lipschitz on average in a certain sense, then they are in fact Lipschitz almost everywhere. This type of result falls into the extensive line of research which studies large deviation bounds for the sum of random variables, where while not independent, exhibit large deviation bounds similar to these obtained by independent random variables.

STOC Conference 2012 Conference Paper

Probabilistic existence of rigid combinatorial structures

• 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. The proof of existence is probabilistic. We show that a randomly chosen such object has the required properties with positive yet tiny probability. The main technical ingredient is a special local central limit theorem for suitable lattice random walks with finitely many steps.

STOC Conference 2012 Conference Paper

Subspace evasive sets

• Zeev Dvir
• Shachar Lovett

We construct explicit subspace-evasive sets. These are subsets of F n of size |F| (1-ε)n whose intersection with any k-dimensional subspace is bounded by a constant c(k,ε). This problem was raised by Guruswami (CCC 2011) as it leads to optimal rate list-decodable codes of constant list size. The main technical ingredient is the construction of k low-degree polynomials whose common set of zeros has small intersection with any k-dimensional subspace.

STOC Conference 2011 Conference Paper

Correlation testing for affine invariant properties on F p n in the high error regime

• 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:F p n -> F p with polynomials of degree at most d ≤ p is non-negligible, while making only a constant number of queries to the function. This is an instance of correlation testing . In this framework, a fixed test is applied to a function, and the acceptance probability of the test is dependent on the correlation of the function from the property. This is an analog of proximity oblivious testing , a notion coined by Goldreich and Ron, in the high error regime. We study in this work general properties which are affine invariant and which are correlation testable using a constant number of queries. We show that any such property (as long as the field size is not too small) can in fact be tested by the Gowers uniformity test, and hence having correlation with the property is equivalent to having correlation with degree d polynomials for some fixed d. We stress that our result holds also for non-linear properties which are affine invariant. This completely classifies affine invariant properties which are correlation testable. The proof is based on higher-order Fourier analysis, where we establish a new approximate orthogonality for structures defined by linear forms. In particular, this resolves an open problem posed by Gowers and Wolf. Another ingredient is a nontrivial extension of a graph theoretical theorem of Erdos, Lovasz and Spencer to the context of additive number theory.

FOCS Conference 2011 Conference Paper

New Extension of the Weil Bound for Character Sums with Applications to Coding

• Tali Kaufman
• Shachar Lovett

The Weil bound for character sums is a deep result in Algebraic Geometry with many applications both in mathematics and in the theoretical computer science. The Weil bound states that for any polynomial f(x) over a finite field F and any additive character χ: F → ℂ, either χ(f(x)) is a constant function or it is distributed close to uniform. The Weil bound is quite effective as long as deg (f) ≪ √|F|, but it breaks down when the degree of f exceeds √|F|. As the Weil bound plays a central role in many areas, finding extensions for polynomials of larger degree is an important problem with many possible applications. In this work we develop such an extension over finite fields F p n of small characteristic: we prove that if f(x) = g(x) + h(x) where deg(g) ≪ √|F| and h(x) is a sparse polynomial of arbitrary degree but bounded weight degree, then the same conclusion of the classical Weil bound still holds: either χ(f(x)) is constant or its distribution is close to uniform. In particular, this shows that the subcode of Reed-Muller codes of degree ω(1) generated by traces of sparse polynomials is a code with near optimal distance, while Reed-Muller of such a degree has no distance (i. e. o(1) distance); this is one of the few examples where one can prove that sparse polynomials behave differently from non-sparse polynomials of the same degree. As an application we prove new general results for affine invariant codes. We prove that any affine-invariant subspace of quasi-polynomial size is (1) indeed a code (i. e. has good distance) and (2) is locally testable. Previous results for general affine invariant codes were known only for codes of polynomial size, and of length 2 n where n needed to be a prime. Thus, our techniques are the first to extend to general families of such codes of super- polynomial size, where we also remove the requirement from n to be a prime. The proof is based on two main ingredients: the extension of the Weil bound for character sums, and a new Fourier-analytic approach for estimating the weight distribution of general codes with large dual distance, which may be of independent interest.

FOCS Conference 2010 Conference Paper

A Lower Bound for Dynamic Approximate Membership Data Structures

• 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, mainly in distributed systems, database systems, and networks. The algorithm of Bloom is quite effective: it can store a set S of size n by using only ≈1. 44nlog 2 (1/ε) bits while having false positive error ε. This is within a constant factor of the entropy lower bound of nlog 2 (1/ε) for storing such sets. Closing this gap is an important open problem, as Bloom filters are widely used is situations were storage is at a premium. Bloom filters have another property: they are dynamic. That is, they support the iterative insertions of up to n elements. In fact, if one removes this requirement, there exist static data structures which receive the entire set at once and can almost achieve the entropy lower bound; they require only nlog 2 (1/ε)(1 + o(1)) bits. Our main result is a new lower bound for the memory requirements of any dynamic approximate membership data structure. We show that for any constant ε > 0, any such data structure which achieves false positive error rate of ε must use at least C(ε) · nlog 2 (1/ε) memory bits, where C(ε) > 1 depends only on ε. This shows that the entropy lower bound cannot be achieved by dynamic data structures for any constant error rate. In fact, our lower bound holds even in the setting where the insertion and query algorithms may use shared randomness, and where they are only required to perform well on average.

FOCS Conference 2010 Conference Paper

Pseudorandom Generators for CC0[p] and the Fourier Spectrum of Low-Degree Polynomials over Finite Fields

• 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 CC 0 [p], the class of constant-depth circuits with unbounded fan-in MOD p gates, for some prime p. More accurately, the seed length of our generator is O(log n) for any constant error ϵ > 0. In fact, we obtain our generator by fooling distributions generated by low degree polynomials, over F p, when evaluated on the Boolean cube. This result significantly extends previous constructions that either required a long seed or that could only fool the distribution generated by linear functions over F p, when evaluated on the Boolean cube. Enroute of constructing our PRG, we prove two structural results for low degree polynomials over finite fields that can be of independent interest. 1) Let f be an n-variate degree d polynomial over F p. Then, for every ϵ > 0 there exists a subset S ⊂ [n], whose size depends only on d and ϵ, such that Σ α∈F p n: α≠0, α S =0 |f̂(α)| 2 ≤ ϵ. Namely, there is a constant size subset S such that the total weight of the nonzero Fourier coefficients that do not involve any variable from S is small. 2) Let f be an n-variate degree d polynomial over F p. If the distribution of f when applied to uniform zero-one bits is ϵ-far (in statistical distance) from its distribution when applied to biased bits, then for every δ > 0, f can be approximated over zero-one bits, up to error δ, by a function of a small number (depending only on ϵ, δ and d) of lower degree polynomials.

STOC Conference 2009 Conference Paper

On cryptography with auxiliary input

• Yevgeniy Dodis
• Yael Tauman Kalai
• Shachar Lovett

We study the question of designing cryptographic schemes which are secure even if an arbitrary function f(sk) of the secret key is leaked, as long as the secret key sk is still (exponentially) hard to compute from this auxiliary input. This setting of auxiliary input is more general than the more traditional setting, which assumes that some of information about the secret key sk may be leaked, but sk still has high min-entropy left. In particular, we deal with situations where f(sk) information-theoretically determines the entire secret key sk. As our main result, we construct CPA/CCA secure symmetric encryption schemes that remain secure with exponentially hard-to-invert auxiliary input. We give several applications of such schemes. * We construct an average-case obfuscator for the class of point functions, which remains secure with exponentially hard-to-invert auxiliary input, and is reusable. * We construct a reusable and robust extractor that remains secure with exponentially hard-to-invert auxiliary input. Our results rely on a new cryptographic assumption, Learning Subspace-with-Noise (LSN), which is related to the well known Learning Parity-with-Noise (LPN) assumption.

STOC Conference 2008 Conference Paper

Inverse conjecture for the gowers norm is false

• 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 to F p is non-negligible, that is larger than a constant independent of N, then f has a non-trivial correlation with a degree d-1 polynomial. The conjecture is known to hold for d=2,3 and for any prime p. In this paper we show the conjecture to be false for p=2 and for d=4, by presenting an explicit function whose 4-th Gowers norm is non-negligible, but whose correlation with any polynomial of degree 3 is exponentially small. Essentially the same result, with different bounds for correlation, was independently obtained by Green and Tao. Their analysis uses a modification of a Ramsey-type argument of Alon and Beigel to show inapproximability of certain functions by low-degree polynomials. We observe that a combination of our results with the argument of Alon and Beigel implies the inverse conjecture to be false for any prime p, for d = p 2 .

STOC Conference 2008 Conference Paper

Unconditional pseudorandom generators for low degree polynomials

• 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 ε 2 O(d) is a pseudorandom generator against degree d polynomials with error ε. This gives a generator with seed length 2 O(d) log(n/ε). Our construction follows the recent breakthrough result of Bogadnov and Viola. Their work shows that the sum of d small-biased generators is a pseudo-random generator against degree d polynomials, assuming the Inverse Gowers Conjecture. However, this conjecture is only proven for d=2,3. The main advantage of our work is that it does not rely on any unproven conjectures.

FOCS Conference 2008 Conference Paper

Worst Case to Average Case Reductions for Polynomials

• Tali Kaufman
• Shachar Lovett

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 degree polynomials. Green and Tao [GT07] have shown that over large fields (i. e when d <|F|) a biased polynomial must have low rank. They have also conjectured that bias implies low rank over general fields, but their proof technique fails to show that. In this work we affirmatively answer their conjecture. Using this result we obtain a general worst case to average case reductions for polynomials. That is, we show that a polynomial that can be approximated by a few polynomials of bounded degree (i. e. a polynomial with non negligible correlation with a function of few bounded degree polynomials), can be computed by a few polynomials of bounded degree. We derive some relations between our results to the construction of pseudorandom generators. Our work provides another evidence to the structure vs. randomness dichotomy.