Publications, preprints and expositions

Sorted by first publication date    (Without summaries)

    Preprints
  1. Abhishek Bhowmick, Shachar Lovett. Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory.
    Submitted.
    Summary: Let f be a low degree multivariate polynomial over a finite field. The polynomial is said to be unbiased if the distribution of f(x) for a uniform input x is close to the uniform distribution over the field, and is called biased otherwise. The polynomial is said to have low rank if it can be expressed as a composition of a few lower degree polynomials. Green and Tao [Contrib. Discrete Math 2009] and Kaufman and Lovett [FOCS 2008] showed that bias implies low rank for fixed degree polynomials over fixed prime fields. This lies at the heart of many tools in higher order Fourier analysis. In this work, we extend this result to all prime fields (of size possibly growing with the number of variables). We also provide a generalization to nonprime fields in the large characteristic case. As an immediate application, we obtain improved bounds for a suite of problems in effective algebraic geometry, including Hilbert nullstellensatz, radical membership and counting rational points in low degree varieties. Using the above generalization to large fields as a starting point, we are also able to settle the list decoding radius of fixed degree Reed-Muller codes over growing fields. The case of fixed size fields was solved by Bhowmick and Lovett [STOC 2015], which resolved a conjecture of Gopalan-Klivans-Zuckerman [STOC 2008]. Here, we show that the list decoding radius is equal the minimum distance of the code for all fixed degrees, even when the field size is possibly growing with the number of variables.

  2. Shachar Lovett, Jiapeng Zhang. Noisy Population Recovery from Unknown Noise.
    Submitted.
    Summary: 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 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 some unknown noise probability, estimate from a few samples the underlying parameters of the model. Previous work designed quasi-polynomial time algorithms which work under the assumption that the noise parameters are exactly known. In this work, we remove this assumption, and show how to recover all the underlying parameters, even when the noise is unknown, in quasi-polynomial time.

  3. Shachar Lovett, Jiapeng Zhang. On the impossibility of entropy reversal, and its application to zero-knowledge proofs.
    Submitted.
    Summary: 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. It is an open problem whether these two classes are in fact equal. In this paper, we rule out efficient black box reductions between SZK and NISZK. We achieve this by studying algorithms which can reverse the entropy of a function. The problem of estimating the entropy of a circuit is complete for NISZK. Hence, reversing the entropy of a function is equivalent to a black box reduction of NISZK to its complement, which is known to be equivalent to a black box reduction of SZK to NISZK [Goldreich et al, CRYPTO 1999]. We show that any such algorithm incurs an exponential loss of parameters, and hence cannot be implemented efficiently.

  4. Shachar Lovett, Avishay Tal, Jiapeng Zhang. Robust sensitivity.
    Submitted.
    Summary: 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 robust analog in this work.

  5. Daniel Kane, Shachar Lovett, Sankeerth Rao. The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes.
    Submitted.
    Summary: 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 $\mathbb{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 \times 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.


  6. 2017
  7. Kaave Hosseini, Shachar Lovett. On the structure of the spectrum of small sets.
    Journal of Combinatorial Theory, Series A (148), pp. 1-14, 2017.
    Summary: Let $G$ be a finite abelian group and $A$ a subset of $G$. The spectrum of $A$ is the set of its large Fourier coefficients. Known combinatorial results on the structure of spectrum, such as Chang's theorem, become trivial in the regime $|A| = |G|^\alpha $ whenever $\alpha \le c$, where $c \ge 1/2$ is some absolute constant. On the other hand, there are statistical results, which apply only to a noticeable fraction of the elements, which give nontrivial bounds even to much smaller sets. One such theorem (due to Bourgain) goes as follows. For a noticeable fraction of pairs $\gamma_1,\gamma_2 $ in the spectrum, $\gamma_1+\gamma_2$ belongs to the spectrum of the same set with a smaller threshold. Here we show that this result can be made combinatorial by restricting to a large subset. That is, we show that for any set $A$ there exists a large subset $A'$, such that the sumset of the spectrum of $A'$ has bounded size. Our results apply to sets of size $|A| = |G|^{\alpha}$ for any constant $\alpha>0$, and even in some sub-constant regime.

  8. Shachar Lovett, Oded Regev. A counterexample to a strong variant of the Polynomial Freiman-Ruzsa conjecture in Euclidean space.
    Accepted to Discrete Analysis, 2017.
    Summary: The Polynomial Freiman-Ruzsa conjecture is one of the central open problems in additive combinatorics. It speculates tight quantitative bounds between combinatorial and algebraic notions of approximate subgroups. In this note, we restrict our attention to subsets of Euclidean space. In this regime, the original conjecture considers approximate algebraic subgroups as the set of lattice points in a convex body. Green asked in 2007 whether this can be simplified to a generalized arithmetic progression, while not losing more than a polynomial factor in the underlying parameters. We give a negative answer to this question, based on a recent reverse Minkowski theorem combined with estimates for random lattices.


  9. 2016
  10. Hamed Hatami, Kaave Hosseini, Shachar Lovett. Structure of protocols for XOR functions.
    Accepted to the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016).
    Summary: 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 of entropy reduction for protocols, combined with existing techniques in Fourier analysis and additive combinatorics.

  11. Esther Ezra, Shachar Lovett. On the Beck-Fiala Conjecture for Random Set Systems.
    Accepted to the 20th International Workshop on Randomization and Computation (RANDOM 2016).
    Summary: 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 show that when $|\Sigma| \ge |X|$ the hereditary discrepancy of $(X,\Sigma)$ is with high probability $O(\sqrt{t \log t})$; and when $|X| \gg |\Sigma|^t$ the hereditary discrepancy of $(X,\Sigma)$ is with high probability $O(1)$. The first bound combines the Lovasz Local Lemma with a new argument based on partial matchings; the second follows from an analysis of the lattice spanned by sparse vectors.

  12. Daniel Dadush, Shashwat Garg, Shachar Lovett, Aleksandr Nikolov. Towards a constructive version of Banaszczyk's Vector Balancing Theorem.
    Accepted to the 20th International Workshop on Randomization and Computation (RANDOM 2016).
    Summary: An important theorem of Banaszczyk states that for any sequence of vectors of $\ell_2$ norm at most $1/5$ and any convex body $K$ of Gaussian measure $1/2$ in $\mathbb{R}^n$, there exists a signed combination of these vectors which lands inside $K$. A major open problem is to devise a constructive version of Banaszczyk's vector balancing theorem, that is, to find an efficient algorithm which constructs the signed combination. In this paper, we make progress towards this conjecture, by giving equivalent formulations of it and algorithms for weaker variants.

  13. Divesh Aggrawal, Kaave Hosseini, Shachar Lovett. Affine-malleable Extractors, Spectrum Doubling, and Application to Privacy Amplification.
    Accepted to the 2016 IEEE International Symposium on Information Theory (ISIT 2016).
    Summary: We define a new notion of malleable extractor, called an affine malleable extractor. We show that a very simple function, the inner product function over large finite fields, is such an extractor, assuming a conjecture in additive combinatorics. We also relate this to optimal protocls for privacy amplification.

  14. Benny Applebaum, Shachar Lovett. Algebraic Attacks against Random Local Functions and Their Countermeasures.
    The 48th ACM Symposium on Theory of Computing (STOC 2016).
    Summary: 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, 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},\ldots,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: (1) We show that pseudorandomness against $\mathbb{F}_2$-linear adversaries (i.e., the distribution $y$ has low-bias) is achieved if the predicate is (a) $k=\Omega(s)$-resilience, i.e., uncorrelated with any $k$-subset of its inputs, and (b) has algebraic degree of $\Omega(s)$ even after fixing $\Omega(s)$ of its inputs. We also show that these requirements are necessary, and so they form a tight characterization (up to constants) of security against linear attacks. (2) Motivated by the cryptanalysis literature, we consider security against algebraic attacks. We provide the first theoretical treatment of such attacks by formalizing a general notion of algebraic inversion and distinguishing attacks based on the Polynomial Calculus proof system. %(Clegg, Edmonds, and Impagliazzo, STOC 1996). We show that algebraic attacks succeed if and only if there exist a degree $e=\Theta(s)$ non-zero polynomial $Q$ whose roots cover the roots of $P$ or cover the roots of $P$'s complement.

  15. Hamed Hatami, Pooya Hatami, Shachar Lovett. General systems of linear forms: equidistribution and true complexity.
    Advances in Mathematics (292), pp. 446-477, 2016.
    Summary: 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 the average, it suffices to know the joint distribution of the polynomials applied to the linear forms. We prove a near-equidistribution theorem that describes these distributions for the group $\mathbb{F}_p^n$ when $p$ is a fixed prime. This fundamental fact is equivalent to a strong near-orthogonality statement regarding the higher-order characters, and was previously known only under various extra assumptions about the linear forms.

  16. Shachar Lovett. Communication is bounded by root of rank.
    Journal of the ACM (JACM) 63, no. 1, 2016. Preliminary version appeared in the 46th ACM Symposium on Theory of Computing (STOC 2014).
    Summary: We prove that any total boolean function of rank $r$ can be computed by a deterministic communication protocol of complexity $O(\sqrt{r} \log(r))$. This gives a nearly quadratic improvement over previous bounds.


  17. 2015
  18. Yogesh Anbalagan, Hao Huang, Shachar Lovett, Sergey Norin, Adrian Vetta, Hehui Wu. Large Supports are required for Well-Supported Nash Equilibria.
    The 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2015).
    Summary: We prove that for any constant $k$ and any $\epsilon \lt 1$, there exist bimatrix win-lose games for which every $\epsilon$-WSNE requires supports of cardinality greater than $k$. To do this, we provide a graph-theoretic characterization of win-lose games that possess $\epsilon$-WSNE with constant cardinality supports. We then apply a result in additive number theory of Haight to construct win-lose games that do not satisfy the requirements of the characterization. These constructions disprove graph theoretic conjectures of Daskalakis, Mehta and Papadimitriou, and Myers.

  19. Shachar Lovett. An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem.
    Theory of computing, graduate survey #6.
    Summary: The polynomial Freiman-Ruzsa conjecture is one of the most important conjectures in additive combinatorics. It asserts that one can switch between combinatorial and algebraic notions of approximate subgroups with only a polynomial loss in the underlying parameters. This conjecture has also found several applications in theoretical computer science. Recently, Tom Sanders proved a weaker version of the conjecture, with a quasi-polynomial loss in parameters. The aim of this note is to make his proof accessible to the theoretical computer science community, and in particular to readers who are less familiar with additive combinatorics.

  20. Shachar Lovett, Jiapeng Zhang. Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions.
    The 47th ACM Symposium on Theory of Computing (STOC 2015).
    Summary: 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 0.49, say, estimate the original probability up to an additive error of epsilon. We give an algorithm which solves this problem in time polynomial in (k^{loglog k},n,1/epsilon). 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/epsilon). Our main technical contribution, which facilitates the algorithm, is a new reverse Bonami-Beckner inequality for the L_1 norm of sparse functions.

  21. Abhishek Bhowmick, Shachar Lovett. List decoding Reed-Muller codes over small fields.
    The 47th ACM Symposium on Theory of Computing (STOC 2015).
    Summary: 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. We show that for Reed-Muller codes over a fixed finite field, fixed degree and large number of variables, the list decoding radius is equal to the minimum distance of the code. This resolves a conjecture of Gopalan-Klivans-Zuckerman [STOC 2008]. We also give tight bounds on the number of codewords for radii beyond the list decoding radius.

  22. Mika Goos, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman. Rectangles Are Nonnegative Juntas.
    The 47th ACM Symposium on Theory of Computing (STOC 2015).
    Summary: 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 the composed function can be simulated by a nonnegative combination of juntas. This allows us to prove several new lower bounds in communication complexity, by first proving analogous lower bounds on the decision tree complexity of $f$, and then applying our gadget reduction.

  23. Abhishek Bhowmick, Shachar Lovett. Nonclassical polynomials as a barrier to polynomial lower bounds.
    The 2015 IEEE Conference on Computational Complexity (CCC 2015).
    Summary: 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 super-logarithmic degree. Here, we suggest a new barrier explaining this phenomenon. We show that many of the existing lower bound proof techniques extend to nonclassical polynomials, an extension of classical polynomials which arose in higher order Fourier analysis. Moreover, these techniques are tight for nonclassical polynomials of logarithmic degree.


  24. 2014
  25. Arman Fazeli, Shachar Lovett, Alexander Vardy. Nontrivial t-Designs over Finite Fields Exist for All t.
    Journal of Combinatorial Theory A (127), pp 149-160, 2014.
    Summary: A $t-(n,k,\lambda)$ design over a finite field $\mathbb{F}_q$ is a collection of $k$-dimensional subspaces of $\mathbb{F}_q^n$, called blocks, such that each $t$-dimensional subspace is contained in exactly $\lambda$ blocks. We prove the existence of nontrivial designs over finite fields for any field $\mathbb{F}_q$, $k>12 t$ and large enough $n$. Previously, existence was only known for $t \le 3$. The proof is by a probabilistic argument.

  26. Shachar Lovett. Linear codes cannot approximate the network capacity within any constant factor.
    Manuscript.
    Summary: 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 to date is by Dougherty et al. who constructed a network with capacity 1 where linear codes can achieve a rate of at most 10/11. Here, we show that linear codes cannot approximate the capacity of a network within any constant factor. That is, for any alpha \in [0,1] we construct a network with capacity 1 where linear codes can achieve a rate of at most alpha. This is achieved by a new network composition operation, which allows to amplify bounds on the linear capacity of networks.

  27. Dmitry Gavinsky, Shachar Lovett. En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations.
    The 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014).
    Summary: The log rank conjecture in communication complexity asserts that the deterministic communication complexity of a total boolean function is determined by the log of its rank, up to polynomial factors. In this work we show that in order to prove it, it suffices to construct weaker notions of protocols for low rank functions: randomized protocols, low information cost protocols or efficient zero-communication protocols.

  28. Chaim Even-Zohar, Shachar Lovett. The Freiman-Ruzsa theorem in finite fields.
    Journal of Combinatorial Theory A (125), pp. 333-341, 2014.
    Summary: 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 conjectured by Ruzsa that the subgroup size can be reduced to $r^{CK}|A|$ for some absolute constant $C \geq 2$. This conjecture was verified for $r=2$ in a sequence of recent works. In this work, we establish the conjecture for any prime torsion.

  29. Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett. Non-malleable Codes from Additive Combinatorics.
    The 46th ACM Symposium on Theory of Computing (STOC 2014).
    Summary: We give a construction of non-malleable codes in the split state model with a polynomial block length. The construction relies on new properties of the inner product function over prime fields, and the analysis utilizes recent tools in additive combinatorics.

  30. Kaave Hosseini, Shachar Lovett, Guy Moshkovitz, Asaf Shapira. An Improved Lower Bound for Arithmetic Regularity.
    To appear in the Mathematical Proceedings of the Cambridge Philosophical Society.
    Summary: The arithmetic regularity lemma due to Green asserts that, for any abelian group $G$ and any bounded function $f:G \to [0,1]$, there exists a subgroup $H \le G$ of bounded index such that $f$ is pseudorandom on most cosets of $H$. The bound on the index $[G:H]$ is a tower of twos of height polynomial in the error parameter. Here, we give an example showing that this bound is essentially best possible.

  31. Yoram Bachrach, Omer Lev, Shachar Lovett, Jeffrey Rosenschein, Morteza Zadimoghaddam. Cooperative Weakest Link Games.
    The 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2014).
    Summary: We introduce and study weakest link games, a cooperative game modelling domains where a team's value is determined by its weakest member.

  32. Shachar Lovett, Cris Moore, Alexander Russell. Group representations that resist random sampling.
    Random Structures and Algorithms, 2014.
    Summary: We show that there exists groups $G_n$ and nontrivial irreducible representations $\rho_n$ such that, for any constant $t$, the average of $\rho_n$ over $t$ uniformly random group elements has operator norm $1$ with probability approaching $1$ as $n \to \infty$. More quantitatively, we show that there exist families of finite groups for which $O(\log \log G)$ random elements are required to bound the norm of a typical representation below $1$. This settles a conjecture of A. Wigderson.

  33. Dmitry Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan. A tail bound for read-k families of functions.
    Random Structures and Algorithms, 2014.
    Summary: We prove a Chernoff-like large deviation bound on the sum of non-independent random variables $Y_1,\ldots,Y_r$ that have the following dependence structure: each is an arbitrary [0,1]-valued function 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$.

  34. Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider. 0-1 Integer Linear Programming with a Linear Number of Constraints.
    Submitted.
    Summary: 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.


  35. 2013
  36. Hamed Hatami, Shachar Lovett. Estimating the distance from testable affine-invariant properties.
    The 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013).
    Summary: 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 was previously unknown even for simple properties such as cubic polynomials over $\mathbb{F}_2$.

  37. Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett. Every locally characterized affine-invariant property is testable.
    The 45th ACM Symposium on Theory of Computing (STOC 2013).
    Summary: An affine-invariant property over a fixed finite field $\mathbb{F}_p$ is a property of functions over $\mathbb{F}_p^n$ that is closed under taking affine transformations of the domain. We prove that all affine-invariant properties having local characterizations are locally testable. We also prove that any property which can be expressed as compositions of a few low degree polynomials (eg reducibility) has this property.

  38. Abhishek Bhowmick, Zeev Dvir, Shachar Lovett. New bounds for matching vector families.
    The 45th ACM Symposium on Theory of Computing (STOC 2013).
    Summary: A matching vector family is a collection of vectors $u_i,v_i \in \mathbb{Z}_m^n$ such that $\langle u_i,v_i \rangle=0$ but $\langle u_i,v_j \rangle \ne 0$ for all $i \ne j$. They form the combinatorial core of matching vector codes, which are recent locally decodable codes with constant query complexity and sub-exponential block length. In this work we give several upper bounds on the size of matching vector families, which imply lower bounds on certain constructions of matching vector codes.

  39. Zeev Dvir, Janos Kollar, Shachar Lovett. Variety evasive sets.
    Computational Complexity, 1-21, 2012.
    Summary: We give an explicit construction of a large subset of $\mathbb{F}^n$, where $\mathbb{F}$ is a finite field, that has small intersection with any affine variety of fixed dimension and bounded degree. Our construction generalizes a recent result of Dvir and Lovett (STOC 2012) who considered varieties of degree one (that is, affine subspaces).

  40. Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett. Testing low complexity affine invariant properties.
    The 2013 ACM-SIAM Symposium on Discrete Algorithms (SODA 2013).
    Summary: An affine-invariant property over a fixed finite field $\mathbb{F}_p$ is a property of functions over $\mathbb{F}_p^n$ that is closed under taking affine transformations of the domain. We prove that all "low complexity" affine-invariant properties having local characterizations are locally testable.


  41. 2012
  42. Eli Ben-Sasson, Shachar Lovett, Noga Zewi. An additive combinatorics approach relating rank to communication complexity.
    Journal of the ACM (JACM), 61(4), article 22, 2014. Preliminary version appeared in the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012).
    Summary: We show that, assuming a number-theoretic conjecture (the polynomial Freiman-Ruzsa conjecture), any total boolean function of rank $r$ has a deterministic communication protocol of complexity $O(r / \log{r})$. This improves over the trivial upper bound of $O(r)$.

  43. Chris Beck, Russell Impagliazzo, Shachar Lovett. Large deviation bounds for decision trees and sampling lower bounds for AC0-circuits.
    The 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012).
    Summary: We prove large deviation bounds for functions computed by decision trees and by $AC^0$ circuits. As an application we strengthen the lower bounds on the ability of $AC^0$ circuits to sample distributions which approximate the uniform distribution over good codes.

  44. Noga Alon, Shachar Lovett. Almost k-wise vs k-wise independent permutations, and uniformity for general group actions.
    The 16th International Workshop on Randomization and Computation (RANDOM 2012).
    Summary: We study distributions over permutations which are statistically close to being $k$-wise independent. We provide several probabilistic and explicit constructions of such distributions.

  45. Shachar Lovett, Raghu Meka. Constructive discrepancy minimization by walking on the edges.
    SIAM Journal on Computing, 44:5, 1573-1582, 2015. Preliminary version appeared at the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012).
    Summary: Minimizing the discrepancy of a set system is a fundamental problem in combinatorics. One of the cornerstones in this area is Spencer's theorem: in any system of $n$ sets in a universe of size $n$, there always exists a coloring which achieves discrepancy $6\sqrt{n}$. The original proof of Spencer was existential in nature. Recently, Bansal found an efficient algorithm to find such a coloring, based on SDP relaxation and a clever rounding procedure. In this work we give a new randomized algorithm to find a coloring based on a restricted random walk. Our algorithm and its analysis use only basic linear algebra and give a new proof of Spencer's theorem.

  46. Dmitry Gavinsky, Shachar Lovett, Srikanth Srinivasan.. Pseudorandom Generators for Read-Once ACC^0.
    IEEE Conference on Computational Complexity (CCC 2012).
    Summary: We construct a pseudo-random generator for the class of read-once constant-depth circuits with unbounded fan-in AND, OR, NOT and generalized modulo $m$ gates, where $m$ is an arbitrary fixed constant. The seed length of our generator is poly-logarithmic in the number of variables and the error.

  47. Zohar Karnin, Edo Liberty, Shachar Lovett, Roy Schwartz, Omri Weinstein. Unsupervised SVMs: on the complexity of the furthest hyperplane problem.
    Conference on Learning Theory 2012 (COLT 2012).
    Summary: This paper introduces the Furthest Hyperplane Problem (FHP), which is an unsupervised counterpart of Support Vector Machines. Given a set of $n$ points in $\mathbb{R}^d$, the objective is to produce the hyperplane (passing through the origin) which maximizes the separation margin, that is, the minimal distance between the hyperplane and any input point. We give a simple randomized algorithm whose running time is $n^{O(1/{\theta}^2)}$ where $\theta$ is the optimal separation margin, and show that the exponent is tight assuming SAT cannot be solved in sub-exponential time. We also give an approximation algorithm for a relaxed problem, and show that FHP does not admit a PTAS by presenting a gap preserving reduction from a particular version of the PCP theorem.

  48. Shachar Lovett. Equivalence of polynomial conjectures in additive combinatorics.
    Combinatorica 32(5), pp. 607-618, 2012.
    Summary: We show that two central conjectures in additive combinatorics are equivalent: the polynomial Freiman-Ruzsa conjecture and the polynomial inverse Gowers conjecture for the $U^3$ norm.

  49. Greg Kuperberg, Shachar Lovett, Ron Peled. Probabilistic existence of regular combinatorial objects.
    The 44th ACM Symposium on Theory of Computing (STOC 2012).
    Summary: We develop a new probabilistic framework which allows us to prove existence of certain regular combinatorial objects which previously were not known to exist. These include combinatorial designs, orthogonal arrays and $k$-wise independent permutations. The main technical innovation is a new connection between random walks on lattices and LDPC codes over the rationals.

  50. Zeev Dvir, Shachar Lovett. Subspace evasive sets.
    The 44th ACM Symposium on Theory of Computing (STOC 2012).
    Summary: We give an explicit construction of a subset of $\mathbb{F}_p^n$ which has small intersection with any low dimensional subspace. The construction is algebraic and is based on a carefully chosen variety.


  51. 2011
  52. Tali Kaufman, Shachar Lovett. New extension of the Weil bound for character sums with applications to coding.
    The 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011).
    Summary: We prove an extension to the famous Weil bound for character sums over fields of low characteristics. We study polynomials over $\mathbb{F}_{p^n}$ which can be expressed as $f_1+f_2$ where $\deg(f_1) \ll p^{n/2}$ and $f_2$ is a sparse polynomial of low weight degree. As an application, we prove that sparse affine invariant codes of quasi-polynomial size have good distance and are locally testable.

  53. Shachar Lovett. Computing polynomials with few multiplications.
    Theory of Computing 7(13), pp. 185-188, 2011.
    Summary: Is is a folklore result in arithmetic complexity that the number of multiplication gates required to compute a worst-case n-variate polynomial of degree d is at least $\Omega(\sqrt{n+d \choose d})$, even if addition gates are allowed to compute arbitrary linear combinations of their inputs. In this note we complement this by an almost matching upper bound

  54. Shachar Lovett, Srikanth Srinivasan. Correlation bounds for poly-size AC0 circuits with n^{1-o(1)} symmetric gates.
    The 15th International Workshop on Randomization and Computation (RANDOM 2011).
    Summary: We prove average case lower bounds (aka correlation bounds) for $AC^0$ circuits which additionally have at most $n^{1-o(1)}$ arbitrary symmetric gates or at most $n^{1/2-o(1)}$ linear threshold gates.

  55. Hamed Hatami, Shachar Lovett. Correlation testing of affine invariant properties on F_p^n in the high error regime.
    SIAM Journal on Computing, 43(4), pp. 1417-1455, 2014. Preliminary version appeared in the 43rd ACM Symposium on Theory of Computing (STOC 2011).
    Summary: We study affine invariant properties over $\mathbb{F}_p^n$, such that correlation with these properties can be tested using a constant number of queries. We show that, if the field is large enough, then any such property is equivalent to low degree polynomials and the test is equivalent to the Gowers uniformity norm. The proof is based on higher-order Fourier analysis.

  56. Arkadev Chattopadhyay, Shachar Lovett. Linear systems over finite abelian groups.
    The 26th Conference on Computational Complexity (CCC 2011).
    Summary: We consider a system of linear constraints over any finite abelian group $G$ of the following form: $\ell_{i,1} x_1 + \ldots + \ell_{i,n} x_n \in A_i$. Our main result is that the subset of the boolean cube that satisfies these constraints has exponentially small correlation with the $MOD_q$ boolean function, when the order of $G$ and $q$ are co-prime numbers. Our work extends the recent result of Chattopadhyay and Wigderson (FOCS 2009) who obtain such a correlation bound for linear systems over cyclic groups whose order is a product of two distinct primes or has at most one prime factor; and implies lower bounds for certain families of depth $4$ circuits.

  57. Shachar Lovett, Emanuele Viola. Bounded-depth circuits cannot sample good codes.
    Computational Complexity (special issue) 21(2), pp. 245-266, 2012. Preliminary version appeared in the 26th Conference on Computational Complexity (CCC 2011).
    Summary: We study a variant of the classical circuit-lower-bound problems: proving lower bounds for sampling distributions given random bits. We show that $AC^0$ circuits cannot sample the uniform distribution over a good code, or even a distribution somewhat close to it. We show applications of this for data structure lower bounds.

  58. Hamed Hatami, Shachar Lovett. Higher-order Fourier analysis of F_p^n and the complexity of systems of linear forms.
    Geometric and Functional Analysis 21(6), pp. 1331-1357, 2011.
    Summary: We study the density of small linear structures (e.g. arithmetic progressions) in subsets $A$ of $\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$ is decomposed as a sum $f_1+f_2$ where $f_1$ is structured in the sense that it has a simple higher-order Fourier expansion, and $f_2$ is pseudo-random in the sense that its $k$-th Gowers uniformity norm is small. In this paper we determine the minimal value of $k$ required for this approach, which resolves an open problem posed by Gowers and Wolf.


  59. 2010
  60. Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka. Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields.
    Computational Complexity 22(4), pp. 679-725, 2013. Preliminary version appeared in the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010).
    Summary: We give the first construction of a pseudo-random generator for the circuit class $CC^0[p]$, the class of constant-depth circuits with unbounded fan-in $MOD_p$ gates. The seed length of our generator is logarithmic in the number of inputs, for any constant error.

  61. Shachar Lovett, Ely Porat. A lower bound for dynamic approximate membership data structures.
    The 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010).
    Summary: We prove that dynamic data structures for the approximate set membership problem (aka Bloom filters) require a constant factor more memory than static data structures.

  62. Shachar Lovett. Holes in generalized Reed-Muller codes.
    IEEE Transactions on Information Theory 56(6), pp. 2583-2586, 2010.
    Summary: The possible relative weights of codewords of Generalized Reed-Muller codes are studied. We show that the set of possible limits of weights of constant degree polynomials is sparse.

  63. Tali Kaufman, Shachar Lovett, Ely Porat. Weight distribution and list-decoding size of Reed-Muller codes.
    IEEE Transactions on Information Theory 58(5), pp. 2689-2696, 2012. Preliminary version in the 1st Symposium on Innovations in Computer Science (ICS 2010).
    Summary: We characterize the weight distribution and the list-decoding size of Reed-Muller codes for all distances. Previously, these where known only for small distances, up to twice the minimal distance of the code. Our result is based on a new connection between the coding problems and computer science techniques used to study low-degree polynomials.


  64. 2009
  65. Ido Ben-Eliezer, Shachar Lovett, Ariel Yadin. Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness.
    Manuscript.
    Summary: We give several structural results on polynomial threshold functions. Several concurrent works established stronger results, hence this manuscript was never published.

  66. Shachar Lovett, Omer Reingold, Luca Trevisan, Salil Vadhan. Pseudorandom bit generators that fool modular sums.
    The 13th Intl. Workshop on Randomization and Computation (RANDOM 2009).
    Summary: We construct pseudo-random generators which fools linear tests modulo a fixed $M$. The seed length of our generators is logarithmic in the number of variables for constant $M$, and slightly worse for super-constant $M$.

  67. Parikshit Gopalan, Shachar Lovett, Amir Shpilka. The complexity of boolean functions in different characteristics.
    Computational Complexity 19(2), pp. 235-263, 2010. Preliminary version in the IEEE Conference on Computational Complexity (CCC 2009).
    Summary: Every boolean function 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 modulo $p$ must have high degree in every other characteristic $q$.

  68. Yevgeniy Dodis, Yael Tauman Kalai, Shachar Lovett. On cryptography with auxiliary input.
    The 41st ACM Symposium on Theory of Computing (STOC 2009).
    Summary: 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. As our main result, we construct CPA/CCA secure symmetric encryption schemes that remain secure with exponentially hard-to-invert auxiliary input.

  69. Ido Ben-Eliezer, Rani Hod, Shachar Lovett. Random low degree polynomials are hard to approximate.
    Computational Complexity (special issue) 21(1), pp. 63-81, 2012. Peliminary version in the 13th Intl. Workshop on Randomization and Computation (RANDOM 2009).
    Summary: We prove that almost all $n$-variate polynomials over $\mathbb{F}_2$ cannot be approximated by low degree polynomials, even with an exponentially small bias. Our results hold for all degrees up to $O(n)$.


  70. 2008
  71. Tali Kaufman, Shachar Lovett. Worst case to average case reductions for polynomials.
    The 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008).
    Summary: A degree-$d$ polynomial $p(x)$ in $n$ variables over a finite field $\mathbb{F}$ is equidistributed if it takes on each of its $|\mathbb{F}|$ values close to equally often, and biased otherwise. We say that $p(x)$ has low rank if it can be expressed as a function of a small number of lower degree polynomials. Green and Tao showed that if the degree is small enough ($d \lt |\mathbb{F}|$) then a biased polynomial must have low rank. In this work we extend their work to polynomials of any constant degree over any constant finite field.

  72. Shachar Lovett, Roy Meshulam, Alex Samorodnitsky. Inverse conjecture for the Gowers norm is false.
    Theory of Computing, 7(9), pp. 131-145, 2011. Preliminary version in the 40th ACM Symposium on Theory of Computing (STOC 2008).
    Summary: 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:\mathbb{F}_p^n \to \mathbb{F}_p$ is non-negligible, then f is non-trivially correlated to a degree-$(d-1)$ polynomial. The conjecture was 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 $d=4$. The same result (with different correlation bounds) was independently obtained by Green and Tao. Later, a revised conjecture was proved by Bergelson, Tao and Ziegler.

  73. Shachar Lovett. Unconditional pseudorandom generators for low degree polynomials.
    Theory of Computing 5(3) pp. 69-82, 2009. Preliminary version appeared in the 40th ACM Symposium on Theory of Computing (STOC 2008).
    Summary: We give the first unconditional construction of a pseudo-random generator against degree $d$ polynomials over finite fields. The construction is the sum of $2^d$ independent small-bias generators. Previously, Bogdanov-Viola had a conditional construction based on the inverse Gowers conjecture. Subsequently, Viola improved the analysis and showed that it suffices to sum $d$ independent small-bias generators.

  74. Shachar Lovett. Lower bounds for adaptive linearity tests.
    The 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008).
    Summary: Linearity tests are randomized algorithms which have oracle access to the truth table of a function, and are supposed to distinguish between linear functions and functions which are far from linear. We prove optimal bounds on the trade-off between the query complexity and the soundness of such algorithms. This result was already known by works of Samorodnitsky-Trevisan and BenSasson-Harsha-Raskhodnikova, but our proof technique is more direct and simple.

  75. Shachar Lovett, Sasha Sodin. Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits.
    Communications in Contemporay Mathematics (CCM), 10(4), 2008.
    Summary: It is well known that $\mathbb{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.

  76. Shachar Lovett, Yoav Tzur. Explicit lower bound for fooling polynomials by the sum of small-bias generators.
    Manuscript.
    Summary: Viola showed that the sum of $d$ independent small-bias generators is a pseudo-random generator against polynomials of degree $d$. We show that the number of summands cannot be reduced below $d$.

Copyright warning: most papers appeared or hopefully will appear in a journal or conference proceedings. In all such cases, the copyright belongs to the publisher. The posting here is only for non-commercial, personal use.