Preprints
- Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan. Do PAC-Learners Learn the Marginal Distribution?.
Manuscript.
[pdf] [bib] [abstract]
@article{hopkins2023pac,
title={Do PAC-Learners Learn the Marginal Distribution?},
author={Hopkins, Max and Kane, Daniel M and Lovett, Shachar and Mahajan, Gaurav},
journal={arXiv preprint arXiv:2302.06285},
year={2023}
}
We study a foundational variant of Valiant and Vapnik and Chervonenkis' Probably Approximately Correct (PAC)-Learning in which the adversary is restricted to a known family of marginal distributions $\mathscr{P}$. In particular, we study how the PAC-learnability of a triple $(\mathscr{P},X,H)$ relates to the learners ability to infer distributional information about the adversary's choice of $D \in \mathscr{P}$. To this end, we introduce the `unsupervised' notion of TV-Learning, which, given a class $(\mathscr{P},X,H)$, asks the learner to approximate $D$ from unlabeled samples with respect to a natural class-conditional total variation metric.
In the classical distribution-free setting, we show that TV-learning is equivalent to PAC-Learning: in other words, any learner must infer near-maximal information about $D$. On the other hand, we show this characterization breaks down for general $\mathscr{P}$, where PAC-Learning is strictly sandwiched between two approximate variants we call `Strong' and `Weak' TV-learning, roughly corresponding to unsupervised learners that estimate most relevant events in $D$ with respect to $H$, but differ in whether the learner knows the well-estimated set. Finally, we observe that TV-learning is in fact equivalent to the classical notion of uniform estimation, and thereby give a strong refutation of the uniform convergence paradigm in supervised learning.
- Michael Jaber, Shachar Lovett, Anthony Ostuni. Strong bounds for skew corner-free sets.
Manuscript.
[pdf] [bib] [abstract]
@article{jaber2024strong,
title={Strong bounds for skew corner-free sets},
author={Jaber, Michael and Lovett, Shachar and Ostuni, Anthony},
journal={arXiv preprint 2404.07380},
year={2024}
}
Motivated by applications to matrix multiplication algorithms, Pratt asked (ITCS'24) how large a subset of $[n] \times [n]$ could be without containing a \textit{skew-corner}: three points $(x,y), (x,y+h),(x+h,y')$ with $h \ne 0$. We prove any skew corner-free set has size at most $\exp(-\Omega(\log^{1/12} n))\cdot n^2$, nearly matching the best known lower bound of $\exp(-O(\sqrt{\log n}))\cdot n^2$ by Beker (arXiv'24). Our techniques generalize those of Kelley and Meka's recent breakthrough on three-term arithmetic progression (FOCS'23), answering a question of Beker (arXiv'24).
2024
- Hamed Hatami, Kaave Hosseini, Shachar Lovett, Anthony Ostuni. Refuting approaches to the log-rank conjecture for XOR functions.
Accepted to the 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024).
[pdf] [bib] [abstract]
@article{hatami2023refuting,
title={Refuting approaches to the log-rank conjecture for XOR functions},
author={Hatami, Hamed and Hosseini, Kaave and Lovett, Shachar and Ostuni, Anthony},
journal={ECCC preprint TR23-203},
year={2023}
}
The log-rank conjecture, a longstanding problem in communication complexity, has persistently eluded resolution for decades. Consequently, some recent efforts have focused on potential approaches for establishing the conjecture in the special case of XOR functions, where the communication matrix is lifted from a boolean function, and the rank of the matrix equals the Fourier sparsity of the function, which is the number of its nonzero Fourier coefficients.
In this note, we refute two conjectures. The first has origins in Montanaro and Osborne (arXiv'09) and is considered in Tsang et al. (FOCS'13), and the second one is due to Mande and Sanyal (FSTTCS'20). These conjectures were proposed in order to improve the best-known bound of Lovett (STOC'14) regarding the log-rank conjecture in the special case of XOR functions. Both conjectures speculate that the set of nonzero Fourier coefficients of the boolean function has some strong additive structure. We refute these conjectures by constructing two specific boolean functions tailored to each.
- Zander Kelley, Shachar Lovett, Raghu Meka. Explicit separations between randomized and deterministic Number-on-Forehead communication.
Accepted to the 56th ACM Symposium on Theory of Computing (STOC 2024).
[pdf] [bib] [abstract]
@article{kelley2023explicit,
title={Explicit separations between randomized and deterministic Number-on-Forehead communication},
author={Kelley, Zander and Lovett, Shachar and Meka, Raghu},
journal={ECCC preprint TR23-124},
year={2023}
}
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 \to \{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 of the first and third authors on sets of integers without 3-term arithmetic progressions into a non-arithmetic setting.
- Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka. New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms.
Accepted to the 56th ACM Symposium on Theory of Computing (STOC 2024).
[pdf] [bib] [abstract]
@article{abboud2023new,
title={New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms},
author={Abboud, Amir and Fischer, Nick and Kelley, Zander and Lovett, Shachar and Meka, Raghu},
year={2023},
eprint={2311.09095},
archivePrefix={arXiv},
primaryClass={cs.DS}
}
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^{\omega})$ time, where $\omega \lt 3$; much work has gone into bringing $\omega$ closer to $2$. Since then, a parallel line of work has sought comparably fast \emph{combinatorial} algorithms but with limited success. The naive $O(n^3)$-time algorithm was initially improved by a $\log^2{n}$ factor [Arlazarov~\emph{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^{\Omega(\sqrt[7]{\log n})}$---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 \emph{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; arXiv'23], and is related to a similar notion from the recent work on $3$-term arithmetic progression free sets [Kelley, Meka;~FOCS'23].
2023
- Shachar Lovett, Jiapeng Zhang. Streaming Lower Bounds and Asymmetric Set-Disjointness.
The 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2023).
[pdf] [bib] [abstract]
@inproceedings{lovett2023streaming,
title={Streaming Lower Bounds and Asymmetric Set-Disjointness},
author={Lovett, Shachar and Zhang, Jiapeng},
booktitle={2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)},
year={2023},
organization={IEEE}
}
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 s1(p2t) . 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.
- Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan, Csaba Szepesvári, Gellért Weisz. Exponential Hardness of Reinforcement Learning with Linear Function Approximation.
The 36th Annual Conference on Learning Theory (COLT 2023).
[pdf] [bib] [abstract]
@inproceedings{liu2023exponential,
title={Exponential Hardness of Reinforcement Learning with Linear Function Approximation},
author={Liu, Sihan and Mahajan, Gaurav and Kane, Daniel and Lovett, Shachar and Weisz, Gell{\'e}rt and Szepesv{\'a}ri, Csaba},
booktitle={The Thirty Sixth Annual Conference on Learning Theory},
pages={1588--1617},
year={2023},
organization={PMLR}
}
A fundamental question in reinforcement learning theory is: suppose the optimal value functions are linear in given features, can we learn them efficiently? This problem's counterpart in supervised learning, linear regression, can be solved both statistically and computationally efficiently. Therefore, it was quite surprising when recent work showed a computational-statistical gap for linear reinforcement learning: even though there are polynomial sample-complexity algorithms, unless NP = RP, there are no polynomial time algorithms for this setting.
In this work, we build on their result to show a computational lower bound, which is exponential in feature dimension and horizon, for linear reinforcement learning under the Randomized Exponential Time Hypothesis. To prove this we build a round-based game where in each round the learner is searching for an unknown vector in a unit hypercube. The rewards in this game are chosen such that if the learner achieves large reward, then the learner's actions can be used to simulate solving a variant of 3-SAT, where (a) each variable shows up in a bounded number of clauses (b) if an instance has no solutions then it also has no solutions that satisfy more than $(1-\varepsilon)$-fraction of clauses. We use standard reductions to show this 3-SAT variant is approximately as hard as 3-SAT. Finally, we also show a lower bound optimized for horizon dependence that almost matches the best known upper bound of $\exp(\sqrt{H}))$.
- Shachar Lovett, Jiapeng Zhang. Fractional certificates for bounded functions.
The 14th Innovations in Theoretical Computer Science (ITCS 2023).
[pdf] [bib] [abstract]
@inproceedings{lovett2023fractional,
title={Fractional Certificates for Bounded Functions},
author={Lovett, Shachar and Zhang, Jiapeng},
booktitle={14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
year={2023},
organization={Schloss Dagstuhl-Leibniz-Zentrum f{\"u}r Informatik}
}
A folklore conjecture in quantum computing is that the acceptance probability of a quantum query algorithm can be approximated by a classical decision tree, with only a polynomial increase in the number of queries. Motivated by this conjecture, Aaronson and Ambainis (Theory of Computing, 2014) conjectured that this should hold more generally for any bounded function computed by a low degree polynomial.
In this work we prove two new results towards establishing this conjecture: first, that any such polynomial has a small fractional certificate complexity; and second, that many inputs have a small sensitive block. We also give two new conjectures that, if true, would imply the Aaronson and Ambainis conjecture given our results.
On the technical side, many classical techniques used in the analysis of Boolean functions seem to fail when applied to bounded functions. Here, we develop a new technique, based on a mix of combinatorics, analysis and geometry, and which in part extends a recent technique of Knop et al. (STOC 2021) to bounded functions.
- Daniel Beaglehole, Max Hopkins, Daniel Kane, Sihan Liu, Shachar Lovett. Sampling Equilibria Fast No-Regret Learning in Structured Games.
The ACM-SIAM Symposium on Discrete Algorithms (SODA 2023).
[pdf] [bib] [abstract]
@inproceedings{beaglehole2023sampling,
title={Sampling Equilibria: Fast No-Regret Learning in Structured Games},
author={Beaglehole, Daniel and Hopkins, Max and Kane, Daniel and Liu, Sihan and Lovett, Shachar},
booktitle={Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
pages={3817--3855},
year={2023},
organization={SIAM}
}
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 \emph{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 \emph{structured} games, showing it is possible to efficiently (approximately) sample the action space in RWM in \emph{polylogarithmic} time. This gives the first efficient no-regret algorithms for problems such as the \emph{(discrete) Colonel Blotto game}, \emph{matroid congestion}, \emph{matroid security}, and basic \emph{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.
2022
- Zach Chase, Shachar Lovett. Approximate union closed conjecture.
Manuscript.
[pdf] [bib] [abstract]
@article{chase2022approximate,
title={Approximate union closed conjecture},
author={Chase, Zachary and Lovett, Shachar},
journal={arXiv preprint arXiv:2211.11689},
year={2022}
}
A set system is called union closed if for any two sets in the set system their union is also in the set system. Gilmer recently proved that in any union closed set system some element belongs to at least a 0.01 fraction of sets, and conjectured that his technique can be pushed to the constant $\frac{3-\sqrt{5}}{2}$. We verify his conjecture; show that it extends to approximate union closed set systems, where for nearly all pairs of sets their union belong to the set system; and show that for such set systems this bound is optimal.
- Abhishek Bhowmick, Shachar Lovett. Bias vs structure of polynomials in large fields, and applications in information theory.
Transactions of Information Theory, 69(2), 963-977, 2022.
[pdf] [bib] [abstract]
@article{bhowmick2022bias,
title={Bias vs Structure of Polynomials in Large Fields, and Applications in Information Theory},
author={Bhowmick, Abhishek and Lovett, Shachar},
journal={IEEE Transactions on Information Theory},
volume={69},
number={2},
pages={963--977},
year={2022},
publisher={IEEE}
}
Let $f$ be a polynomial of degree $d$ in $n$ variables over a finite field $\F$. The polynomial is said to be unbiased if the distribution of $f(x)$ for a uniform input $x \in \F^n$ is close to the uniform distribution over $\F$, 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 $n$). We also provide a generalization to nonprime fields in the large characteristic case. However, we state all our applications in the prime field setting for the sake of simplicity of presentation.
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 $n$.
Additionally, we effectively resolve the weight distribution problem for Reed-Muller codes of fixed degree over all fields, first raised in 1977 in the classic textbook by MacWilliams and Sloane [Research Problem 15.1 in Theory of Error Correcting Codes].
- Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett, Ruizhe Zhang. Eigenstripping, Spectral Decay, and Edge-Expansion on Posets.
The 26th International Workshop on Randomization and Computation (RANDOM 2022).
[pdf] [bib] [abstract]
@inproceedings{gaitonde2022eigenstripping,
author = {Gaitonde, Jason and Hopkins, Max and Kaufman, Tali and Lovett, Shachar and Zhang, Ruizhe},
title = {Eigenstripping, Spectral Decay, and Edge-Expansion on Posets},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {16:1--16:24},
year = {2022},
volume = {245},
}
Fast mixing of random walks on hypergraphs has led to myriad breakthroughs in theoretical computer science in the last five years. On the other hand, many important applications (e.g. to locally testable codes, 2-2 games) rely on a more general class of underlying structures called posets, and crucially take advantage of non-simplicial structure. These works make it clear the global expansion properties of posets depend strongly on their underlying architecture (e.g. simplicial, cubical, linear algebraic), but the overall phenomenon remains poorly understood. In this work, we quantify the advantage of different poset architectures in both a spectral and combinatorial sense, highlighting how regularity controls the spectral decay and edge-expansion of corresponding random walks.
We show that the spectra of walks on expanding posets (Dikstein, Dinur, Filmus, Harsha APPROX-RANDOM 2018) concentrate in strips around a small number of approximate eigenvalues controlled by the regularity of the underlying poset. This gives a simple condition to identify poset architectures (e.g. the Grassmann) that exhibit exponential decay of eigenvalues, versus architectures like hypergraphs whose eigenvalues decay linearly -- a crucial distinction in applications to hardness of approximation such as the recent proof of the 2-2 Games Conjecture (Khot, Minzer, Safra FOCS 2018). We show these results lead to a tight characterization of edge-expansion on posets in the $\ell_2$-regime (generalizing recent work of Bafna, Hopkins, Kaufman, and Lovett (SODA 2022)), and pay special attention to the case of the Grassmann where we show our results are tight for a natural set of sparsifications of the Grassmann graphs. We note for clarity that our results do not recover the characterization of expansion used in the proof of the 2-2 Games Conjecture which relies on $\ell_\infty$ rather than $\ell_2$-structure.
- Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan. Computational-Statistical Gaps in Reinforcement Learning.
The 35th Annual Conference on Learning Theory (COLT 2022).
[pdf] [bib] [abstract]
@inproceedings{kane2022computation,
title={Computational-Statistical Gap in Reinforcement Learning},
author={Kane, Daniel and Liu, Sihan and Lovett, Shachar and Mahajan, Gaurav},
booktitle={Proceedings of Thirty Fifth Conference on Learning Theory},
pages={1282--1302},
year={2022},
volume={178},
series={Proceedings of Machine Learning Research},
}
Reinforcement learning with function approximation has recently achieved tremendous results in applications with large state spaces. This empirical success has motivated a growing body of theoretical work proposing necessary and sufficient conditions under which efficient reinforcement learning is possible. From this line of work, a remarkably simple minimal sufficient condition has emerged for sample efficient reinforcement learning: MDPs with optimal value function V* and Q* linear in some known low-dimensional features. In this setting, recent works have designed sample efficient algorithms which require a number of samples polynomial in the feature dimension and independent of the size of state space. They however leave finding computationally efficient algorithms as future work and this is considered a major open problem in the community.
In this work, we make progress on this open problem by presenting the first computational lower bound for RL with linear function approximation: unless NP=RP, no randomized polynomial time algorithm exists for deterministic transition MDPs with a constant number of actions and linear optimal value functions. To prove this, we show a reduction from Unique-Sat, where we convert a CNF formula into an MDP with deterministic transitions, constant number of actions and low dimensional linear optimal value functions. This result also exhibits the first computational-statistical gap in reinforcement learning with linear function approximation, as the underlying statistical problem is information-theoretically solvable with a polynomial number of queries, but no computationally efficient algorithm exists unless NP=RP. Finally, we also prove a quasi-polynomial time lower bound under the Randomized Exponential Time Hypothesis.
- Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan. Realizable Learning is All You Need.
TheoretiCS, volume 3, 2024. Preliminry version in the 35th Annual Conference on Learning Theory (COLT 2022).
[pdf] [bib] [abstract]
@article{hopkins2024realizable,
TITLE = {Realizable Learning is All You Need},
AUTHOR = {Max Hopkins and Daniel M. Kane and Shachar Lovett and Gaurav Mahajan},
URL = {https://theoretics.episciences.org/13009},
DOI = {10.46298/theoretics.24.2},
JOURNAL = {{TheoretiCS}},
VOLUME = {{volume_926_title}},
YEAR = {2024},
MONTH = Feb,
KEYWORDS = {Computer Science - Machine Learning ; Statistics - Machine Learning ; 68Q32},
}
The equivalence of realizable and agnostic learnability is a fundamental phenomenon in learning theory. With variants ranging from classical settings like PAC learning and regression to recent trends such as adversarially robust and private learning, it's surprising that we still lack a unified theory; traditional proofs of the equivalence tend to be disparate, and rely on strong model-specific assumptions like uniform convergence and sample compression.
In this work, we give the first model-independent framework explaining the equivalence of realizable and agnostic learnability: a three-line blackbox reduction that simplifies, unifies, and extends our understanding across a wide variety of settings. This includes models with no known characterization of learnability such as learning with arbitrary distributional assumptions or general loss, as well as a host of other popular settings such as robust learning, partial learning, fair learning, and the statistical query model.
More generally, we argue that the equivalence of realizable and agnostic learning is actually a special case of a broader phenomenon we call property generalization: any desirable property of a learning algorithm (e.g. noise tolerance, privacy, stability) that can be satisfied over finite hypothesis classes extends (possibly in some variation) to any learnable hypothesis class.
- Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett. Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments.
The 54th Annual ACM Symposium on Theory of Computing (STOC 2022).
[pdf] [bib] [abstract]
@inproceedings{bafna2022hypercontractivity,
title={Hypercontractivity on high dimensional expanders: a Local-to-Global Approach for Higher Moments},
author={Bafna, Mitali and Hopkins, Max and Kaufman, Tali and Lovett, Shachar},
booktitle={Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing},
pages={185--194},
year={2022}
}
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.
- Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett. High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games.
The ACM-SIAM Symposium on Discrete Algorithms (SODA 2022).
[pdf] [bib] [abstract]
@inproceedings{bafna2022high,
title={High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games},
author={Bafna, Mitali and Hopkins, Max and Kaufman, Tali and Lovett, Shachar},
booktitle={Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
pages={1069--1128},
year={2022},
organization={SIAM}
}
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 [KM16], 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 [DK17], 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 $\ell_2$-characterization of edge-expansion, as well as to a new understanding of local-to-global algorithms on HDX. Towards the latter, we introduce a spectral complexity measure called Stripped Threshold Rank, and show how it can replace the (much larger) threshold rank in controlling the performance of algorithms on structured objects. Combined with a sum-of-squares proof of the former $\ell_2$-characterization, we give a concrete application of this framework to algorithms for unique games on HD-walks, in many cases improving the state of the art [RBS11, ABS15] 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 $\ell_\infty$-variant for the Grassmann graphs was recently used to resolve the 2-2 Games Conjecture [KMS18]. We give a reduction from a related $\ell_\infty$-variant to our $\ell_2$-characterization, but it loses factors in the regime of interest for hardness where the gap between $\ell_2$ and $\ell_\infty$ structure is large. Nevertheless, we open the door for further work on the use of HDX in hardness of approximation and unique games.
- Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, Jiapeng Zhang. Lifting with sunflowers.
The 13th Innovations in Theoretical Computer Science Conference (ITCS 2022).
[pdf] [bib] [abstract]
@inproceedings{lovett2022lifting,
title={Lifting with sunflowers},
author={Lovett, Shachar and Meka, Raghu and Mertz, Ian and Pitassi, Toniann and Zhang, Jiapeng},
booktitle={13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
year={2022},
organization={Schloss Dagstuhl-Leibniz-Zentrum f{\"u}r Informatik}
}
Query-to-communication lifting theorems translate lower bounds on query complexity to lower bounds for the corresponding communication model. In this paper, we give a simplified proof of deterministic lifting (in both the tree-like and dag-like settings). Whereas previous proofs used sophisticated Fourier analytic techniques, our proof uses elementary counting together with a novel connection to the sunflower lemma.
In addition to a simplified proof, our approach also gives quantitative improvements in terms of gadget size. Focusing on one of the most widely used gadgets---the index gadget---existing lifting techniques are known to require at least a quadratic gadget size. Our new approach combined with robust sunflower lemmas allows us to reduce the gadget size to near linear. We conjecture that it can be further improved to poly logarithmic, similar to the known bounds for the corresponding robust sunflower lemmas.
2021
- Max Hopkins, Daniel Kane, Shachar Lovett, Michal Moshkovitz. Bounded Memory Active Learning through Enriched Queries.
The 34th Annual Conference on Learning Theory (COLT 2021).
[pdf] [bib] [abstract]
@unpublished{hopkins2021bounded,
title={Bounded Memory Active Learning through Enriched Queries},
author={Max Hopkins and Daniel Kane and Shachar Lovett and Michal Moshkovitz},
year={2021},
eprint={2102.05047},
archivePrefix={arXiv},
primaryClass={cs.LG}
}
The explosive growth of easily-accessible unlabeled data has lead to growing interest in active learning, a paradigm in which data-hungry learning algorithms adaptively select informative examples in order to lower prohibitively expensive labeling costs. Unfortunately, in standard worst-case models of learning, the active setting often provides no improvement over non-adaptive algorithms. To combat this, a series of recent works have considered a model in which the learner may ask enriched queries beyond labels. While such models have seen success in drastically lowering label costs, they tend to come at the expense of requiring large amounts of memory. In this work, we study what families of classifiers can be learned in bounded memory. To this end, we introduce a novel streaming-variant of enriched-query active learning along with a natural combinatorial parameter called lossless sample compression that is sufficient for learning not only with bounded memory, but in a query-optimal and computationally efficient manner as well. Finally, we give three fundamental examples of classifier families with small, easy to compute lossless compression schemes when given access to basic enriched queries: axis-aligned rectangles, decision trees, and halfspaces in two dimensions.
- Sankeerth Rao Karingula, Shachar Lovett. Singularity of random integer matrices with large entries.
The 25th International Workshop on Randomization and Computation (RANDOM 2021).
[pdf] [bib] [abstract]
@InProceedings{karingula2021singularity,
author ={Karingula, Sankeerth Rao and Lovett, Shachar},
title ={Singularity of Random Integer Matrices with Large Entries},
booktitle ={Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages ={33:1--33:16},
year ={2021},
}
We study the singularity probability of random integer matrices. Concretely, the probability that a random $n \times n$ matrix, with integer entries chosen uniformly from $\{-m,\ldots,m\}$, is singular. This problem has been well studied in two regimes: large $n$ and constant $m$; or large $m$ and constant $n$. In this paper, we extend previous techniques to handle the regime where both $n,m$ are large. We show that the probability that such a matrix is singular is $m^{-cn}$ for some absolute constant $c>0$. We also provide some connections of our result to coding theory.
- Simon S. Du, Sham M. Kakade, Jason D. Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, Ruosong Wang. Bilinear Classes A Structural Framework for Provable Generalization in RL.
The 38th International Conference on Machine Learning (ICML 2021).
[pdf] [bib] [abstract]
@misc{du2021bilinear,
title={Bilinear Classes: A Structural Framework for Provable Generalization in RL},
author={Simon S. Du and Sham M. Kakade and Jason D. Lee and Shachar Lovett and Gaurav Mahajan and Wen Sun and Ruosong Wang},
year={2021},
eprint={2103.10897},
archivePrefix={arXiv},
primaryClass={cs.LG}
}
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.
- Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, Abhishek Shetty. Fractional Pseudorandom Generators from Any Fourier Level.
The 2021 Computational Complexity Conference (CCC 2021).
[pdf] [bib] [abstract]
@InProceedings{chattopadhyay2021fractional,
author = {Chattopadhyay, Eshan and Gaitonde, Jason and Lee, Chin Ho and Lovett, Shachar and Shetty, Abhishek},
title = {Fractional Pseudorandom Generators from Any {F}ourier Level},
booktitle = {36th Computational Complexity Conference (CCC 2021)},
pages = {10:1--10:24},
year = {2021},
volume = {200},
}
We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay et al. \cite{CHHL,CHLT} that exploit $L_1$ Fourier tail bounds for classes of Boolean functions to construct pseudorandom generators (PRGs). We show that given a bound on the $k$-th level of the Fourier spectrum, one can construct a PRG with a seed length whose quality scales with $k$. This interpolates previous works, which either require Fourier bounds on all levels \cite{CHHL}, or has polynomial dependence on the error parameter in the seed length \cite{CHLT}, and thus answers an open question in \cite{CHLT}. As an example, we show that for polynomial error, Fourier bounds on the first $O(\log n)$ levels is sufficient to recover the seed length in \cite{CHHL}, which requires bounds on the entire tail.
We obtain our results by an alternate analysis of fractional PRGs using Taylor's theorem and bounding the degree-$k$ Lagrange remainder term using multilinearity and random restrictions. Interestingly, our analysis relies only on the \emph{level-k unsigned Fourier sum}, which is potentially a much smaller quantity than the $L_1$ notion in previous works. By generalizing a connection established in \cite{xorlemma}, we give a new reduction from constructing PRGs to proving correlation bounds.
Finally, using these improvements we show how to obtain a PRG for $\mathbb{F}_2$ polynomials with seed length close to the state-of-the-art construction due to Viola \cite{viola2009sum}, which was not known to be possible using this framework.
- Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan. Log-rank and lifting for AND-functions.
The 53rd ACM Symposium on Theory of Computing (STOC 2021).
[pdf] [bib] [abstract]
@inproceedings{knop2021log,
title={Log-rank and lifting for AND-functions},
author={Knop, Alexander and Lovett, Shachar and McGuire, Sam and Yuan, Weiqiang},
booktitle={Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing},
pages={197--208},
year={2021}
}
Let $f: \{0, 1\}^n \to \{0, 1\}$ be a boolean function, and let $f_\land(x, y) = f(x \land y)$ denote the \emph{AND-function} of $f$, where $x \land y$ denotes bit-wise AND. We study the deterministic communication complexity of $f_{\land}$ and show that, up to a $\log n$ factor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix of $f_{\land}$. This comes within a $\log n$ factor of establishing the log-rank conjecture for AND-functions with \emph{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 $\mathbb{F}_2$-degree. Our techniques can also be used to prove (within a $\log n$ factor) a \emph{lifting theorem} for AND-functions, stating that the deterministic communication complexity of $f_{\land}$ is polynomially related to the \emph{AND-decision tree complexity} of $f$.
The results rely on a new structural result regarding boolean functions $f: \{0, 1\}^n \to \{0, 1\}$ with a sparse polynomial representation, which
may be of independent interest. We show that if the polynomial computing $f$ has few monomials then the set system of the monomials has a small hitting set, of size poly-logarithmic in its sparsity. We also establish extensions of this result to multi-linear polynomials $f: \{0, 1\}^n \to \mathbb{R}$ with a larger range.
2020
- Max Hopkins, Daniel Kane, Shachar Lovett. The Power of Comparisons for Actively Learning Linear Classifiers.
The 34th Conference on Neural Information Processing Systems (NeurIPS 2020).
[pdf] [bib] [abstract]
@article{hopkins2020power,
title={The power of comparisons for actively learning linear classifiers},
author={Hopkins, Max and Kane, Daniel and Lovett, Shachar},
journal={Advances in Neural Information Processing Systems},
volume={33},
year={2020}
}
In the world of big data, large but costly to label datasets dominate many fields. Active learning, an unsupervised 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 the passive case, and quadratically more expensive in the active case.
- Alon Gonen, Shachar Lovett, Michal Moshkovitz. Towards a combinatorial characterization of bounded memory learning.
The 34th Conference on Neural Information Processing Systems (NeurIPS 2020).
[pdf] [bib] [abstract]
@article{gonen2020combinatorial,
title={Towards a combinatorial characterization of bounded memory learning},
author={Alon Gonen and Shachar Lovett and Michal Moshkovitz},
journal={Advances in Neural Information Processing Systems},
volume={33},
year={2020}
}
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. 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.
- Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan. Point Location and Active Learning: Learning Halfspaces Almost Optimally.
The 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020).
[pdf] [bib] [abstract]
@inproceedings{hopkins2020point,
title={Point location and active learning: Learning halfspaces almost optimally},
author={Hopkins, Max and Kane, Daniel and Lovett, Shachar and Mahajan, Gaurav},
booktitle={2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)},
pages={1034--1044},
year={2020},
organization={IEEE}
}
Given a finite set $X \subset \mathbb{R}^d$ and a binary linear classifier $c: \mathbb{R}^d \to \{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 $\tilde{O}(d\log(|X|))$, improving on the previous best of $\tilde{O}(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, 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.
- Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan. Noise-tolerant, Reliable Active Classification with Comparison Queries.
The 33rd annual Conference on Learning Theory (COLT 2020).
[pdf] [bib] [abstract]
@InProceedings{hopkins2020noise,
title = {Noise-tolerant, Reliable Active Classification with Comparison Queries},
author = {Max Hopkins and Daniel Kane and Shachar Lovett and Gaurav Mahajan},
booktitle = {Proceedings of Thirty Third Conference on Learning Theory},
pages = {1957--2006},
year = {2020},
volume = {125},
}
With the explosion of massive, widely available unlabeled data in the past years, finding label and time efficient, robust learning algorithms has become ever more important in theory and in practice. We study the paradigm of active learning, in which algorithms with access to large pools of data may adaptively choose what samples to label in the hope of exponentially increasing efficiency. By introducing comparisons, an additional type of query comparing two points, we provide the first time and query efficient algorithms for learning non-homogeneous linear separators robust to bounded (Massart) noise. We further provide algorithms for a generalization of the popular Tsybakov low noise condition, and show how comparisons provide a strong reliability guarantee that is often impractical or impossible with only labels - returning a classifier that makes no errors with high probability.
- Hamed Hatami, Kaave Hosseini, Shachar Lovett. Sign rank vs Discrepancy.
The 2020 Computational Complexity Conference (CCC 2020).
[pdf] [bib] [abstract]
@inproceedings{hatami2020sign,
title={Sign Rank vs Discrepancy},
author={Hatami, Hamed and Hosseini, Kaave and Lovett, Shachar},
booktitle={35th Computational Complexity Conference (CCC 2020)},
year={2020},
organization={Schloss Dagstuhl-Leibniz-Zentrum f{\"u}r Informatik}
}
Sign-rank and discrepancy are two central notions in communication complexity. The seminal work of Babai, Frankl, and Simon from 1986 initiated an active line of research that investigates the gap between these two notions. In this article, we establish the strongest possible separation by constructing a Boolean matrix whose sign-rank is only $3$, and yet its discrepancy is $2^{-\Omega(n)}$. We note that every matrix of sign-rank $2$ has discrepancy $n^{-O(1)}$. Our result in particular implies that there are Boolean functions with $O(1)$ \emph{unbounded error} randomized communication complexity while having $\Omega(n)$ \emph{weakly unbounded error} randomized communication complexity.
- Shachar Lovett, Kewen Wu, Jiapeng Zhang. Decision list compression by mild random restrictions.
Journal of the ACM (JACM), 68(6), 1-17, 2021.
Prelminiary verion appeared in the 52nd ACM Symposium on Theory of Computing (STOC 2020).
[pdf] [bib] [abstract]
@article{lovett2021decision,
title={Decision list compression by mild random restrictions},
author={Lovett, Shachar and Wu, Kewen and Zhang, Jiapeng},
journal={Journal of the ACM (JACM)},
volume={68},
number={6},
pages={1--17},
year={2021},
publisher={ACM New York, NY}
}
A decision list is an ordered list of rules. Each rule is specified by a term, which is a conjunction of literals, and a value. Given an input, the output of a decision list is the value corresponding to the first rule whole term is satisfied by the input. Decision lists generalize both CNFs and DNFs, and have been studied both in complexity theory and in learning theory.
The size of a decision list is the number of rules, and its width is the maximal number of variables in a term. We prove that decision lists of small width can always be approximated by decision lists of small size, where we obtain sharp bounds (up to constants). This in particular resolves a conjecture of Gopalan, Meka and Reingold (Computational Complexity, 2013) on DNF sparsification.
An ingredient in our proof is a new random restriction lemma, which allows to analyze how DNFs (and more generally, decision lists) simplify if a small fraction of the variables are fixed. This is in contrast to the more commonly used switching lemma, which requires most of the variables to be fixed.
- Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang. Improved bounds for the sunflower lemma.
Annals of mathematics, volume 194 (2021), pages 795-815.
Preliminary version in the 52nd ACM Symposium on Theory of Computing (STOC 2020), best paper.
[pdf] [bib] [abstract]
@article{improved2021alweiss,
author = {Ryan Alweiss and Shachar Lovett and Kewen Wu and Jiapeng Zhang},
title = {Improved bounds for the sunflower lemma},
volume = {194},
journal = {Annals of Mathematics},
number = {3},
publisher = {Department of Mathematics of Princeton University},
pages = {795--815},
year = {2021},
}
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\H{o}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.
- Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman. XOR Lemmas for Resilient Functions Against Polynomials.
The 52nd ACM Symposium on Theory of Computing (STOC 2020).
[pdf] [bib] [abstract]
@inproceedings{chattopadhyay2020xor,
title={XOR lemmas for resilient functions against polynomials},
author={Chattopadhyay, Eshan and Hatami, Pooya and Hosseini, Kaave and Lovett, Shachar and Zuckerman, David},
booktitle={Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing},
pages={234--246},
year={2020}
}
A major challenge in complexity theory is to explicitly construct functions that have small correlation with low-degree polynomials over $\mathbb{F}_2$. We introduce a new technique to prove such correlation bounds with $\mathbb{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 $\mathbb{F}_2$. We show that for any n-variate polynomial $p$ over $\mathbb{F}_2$ of degree at most $d$, there is a small set $S \subset [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.
2019
- Shachar Lovett, Jiapeng Zhang. DNF sparsification beyond sunflowers.
The 51st ACM Symposium on Theory of Computing (STOC 2019).
[pdf] [bib] [abstract]
@inproceedings{lovett2019dnf,
title={DNF sparsification beyond sunflowers},
author={Lovett, Shachar and Zhang, Jiapeng},
booktitle={Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing},
pages={454--460},
year={2019}
}
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.
Gopalan, Meka and Reingold [Computational Complexity 2013] showed that the other direction -- DNF sparsification -- holds as well. Any DNF of width w can be approximated to within error by a DNF of size $(w log(1/\varepsilon))^{O(w)}$ . Our main interest in this work is the dependence on the width w. The same dependence of $w^w$ appears in several other open problems in combinatorics and complexity, such as the Erd\H{o}s-Rado sunflower conjecture and Mansour's conjecture. In fact, there are deep connections between these three problems. Our main result is DNF compression with an improved dependence on the width, which overcomes the ww barrier. Concretely, we show that any DNF of width w can be approximated to within error by a DNF of size $(1/\varepsilon)^{O(w)}$.
The proof centers around a new object which we call the DNF index function. Given a DNF, the DNF index function outputs for an input the first clause that satisfies it (if one exists). Our proof has two parts: a combinatorial part, where we exhibit a switching lemma for the DNF index function; and an analytic part, where we use the switching lemma to bound the noise sensitivity of the DNF index function, and then use it to obtain our DNF compression result.
- Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals. Equality Alone Does Not Simulate Randomness.
The 2019 Computational Complexity Conference (CCC 2019).
[pdf] [bib] [abstract]
@inproceedings{chattopadhyay2019equality,
title={Equality alone does not simulate randomness},
author={Chattopadhyay, Arkadev and Lovett, Shachar and Vinyals, Marc},
booktitle={34th Computational Complexity Conference (CCC 2019)},
year={2019},
organization={Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik}
}
The canonical problem that gives an exponential separation between deterministic and randomized communication complexity in the classical two-party communication model is `Equality'. In this work, we show that even allowing access to an `Equality' oracle, deterministic protocols remain exponentially weaker than randomized ones. More precisely, we exhibit a total function on $n$ bits with randomized one-sided communication complexity $O(\log n)$, but such that every deterministic protocol with access to `Equality' oracle needs $\Omega(n / \log n)$ cost to compute it.
- Shachar Lovett, Noam Solomon, Jiapeng Zhang. From DNF compression to sunflower theorems via regularity.
The 2019 Computational Complexity Conference (CCC 2019).
[pdf] [bib] [abstract]
@inproceedings{lovett2019dnf,
title={From DNF Compression to Sunflower Theorems via Regularity},
author={Lovett, Shachar and Solomon, Noam and Zhang, Jiapeng},
booktitle={34th Computational Complexity Conference (CCC 2019)},
year={2019},
organization={Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik}
}
The sunflower conjecture is one of the most well-known open problems in combinatorics. It has several applications in theoretical computer science, one of which is DNF compression, due to Gopalan, Meka and Reingold [Computational Complexity 2013]. In this paper, we show that improved bounds for DNF compression imply improved bounds for the sunflower conjecture, which is the reverse direction. The main approach is based on regularity of set systems and a structure-vs-pseudorandomness approach to the sunflower conjecture.
- Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev. Optimality of Linear Sketching under Modular Updates.
The 2019 Computational Complexity Conference (CCC 2019).
[pdf] [bib] [abstract]
@inproceedings{hosseini2019optimality,
title={Optimality of Linear Sketching Under Modular Updates},
author={Hosseini, Kaave and Lovett, Shachar and Yaroslavtsev, Grigory},
booktitle={34th Computational Complexity Conference (CCC 2019)},
year={2019},
organization={Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik}
}
We study the relation between streaming algorithms and linear sketching algorithms, in the context of binary updates. We show that for inputs in $n$ dimensions, the existence of efficient streaming algorithms which can process $\Omega(n^2)$ updates implies efficient linear sketching algorithms with comparable cost. This improves upon the previous work of Li, Nguyen and Woodruff [LNW14] and Ai, Hu, Li and Woodruff [AHLW16] which required a triple-exponential number of updates to achieve a similar result for updates over integers. We extend our results to updates modulo $p$ for integers $p \ge 2$, and to approximation instead of exact computation.
- Kaave Hosseini, Shachar Lovett. A bilinear Bogolyubov-Ruzsa lemma with poly-logarithmic bounds.
Discrete Analysis 2019:10.
[pdf] [bib] [abstract]
@article{hosseini2019bilinear,
title={A bilinear Bogolyubov-Ruzsa lemma with poly-logarithmic bounds},
author={Hosseini, Kaave and Lovett, Shachar},
journal={Discrete Analysis},
number={10},
year={2019}
}
The Bogolyubov-Ruzsa lemma, in particular the quantitative bounds obtained by Sanders, plays a central role in obtaining effective bounds for the inverse $U^3$ theorem for the Gowers norms. Recently, Gowers and Mili\'cevi\'c applied a bilinear Bogolyubov-Ruzsa lemma as part of a proof of the inverse $U^4$ theorem with effective bounds. The goal of this note is to obtain quantitative bounds for the bilinear Bogolyubov-Ruzsa lemma which are similar to those obtained by Sanders for the Bogolyubov-Ruzsa lemma.
We show that if a set $A \subset \mathbb{F}^n \times \mathbb{F}^n$ has density $\alpha$, then after a constant number of horizontal and vertical sums, the set $A$ would contain a bilinear structure of co-dimension $r=\log^{O(1)} \alpha^{-1}$. This improves the results of Gowers and Mili\'cevi\'c which obtained similar results with a weaker bound of $r=\exp(\exp(\log^{O(1)} \alpha^{-1}))$ and by Bienvenu and L\^e which obtained $r=\exp(\exp(\exp(\log^{O(1)} \alpha^{-1})))$.
- Shachar Lovett. The analytic rank of tensors is subadditive, and its applications.
Discrete Analysis 2019:7.
[pdf] [bib] [abstract]
@article{lovett2019analytic,
title={The analytic rank of tensors is subadditive, and its applications},
author={Lovett, Shachar},
journal={Discrete Analysis},
number={7},
year={2019}
}
The analytic rank of a tensor, first defined by Gowers and Wolf in the context of higher order Fourier analysis, is defined to be the logarithm of the bias of the tensor. We prove that it is a subadditive measure of rank, namely that the analytic rank of the sum of two tensors is at most the sum of their individual analytic rank.
We also give some consequences of this property. We show that the analytic rank of a tensor lower bounds the slice rank and partition rank of a tensor, quantities that arise in the study of Ramsey problems in product spaces. Furthermore, we show that the analytic rank can be used instead of the slice rank or partition rank, which suggests a new approach to study some open problems in this domain.
- Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal. Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates.
The 10th Innovations in Theoretical Computer Science (ITCS 2019).
[pdf] [bib] [abstract]
@inproceedings{chattopadhyay2018pseudorandom,
title={Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates},
author={Chattopadhyay, Eshan and Hatami, Pooya and Lovett, Shachar and Tal, Avishay}
booktitle={The 10th Innovations in Theoretical Computer Science (ITCS 2019)},
year={2019}
}
A recent work of Chattopadhyay et al. (CCC 2018) introduced a new framework for the design of pseudorandom generators for Boolean functions. It works under the assumption that the Fourier tails of the Boolean functions are uniformly bounded for all levels by an exponential function. In this work, we design an alternative pseudorandom generator that only requires bounds on the second level of the Fourier tails. It is based on a derandomization of the work of Raz and Tal (ECCC 2018) who used the above framework to obtain an oracle separation between BQP and PH.
As an application, we give a concrete conjecture for bounds on the second level of the Fourier tails for low degree polynomials over the finite field F2. If true, it would imply an efficient pseudorandom generator for AC0 with parity gates, a well-known open problem in complexity theory. As a stepping stone towards resolving this conjecture, we prove such bounds for the first level of the Fourier tails.
- Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao. Torus polynomials: an algebraic approach to ACC lower bounds.
The 10th Innovations in Theoretical Computer Science (ITCS 2019).
[pdf] [bib] [abstract]
@inproceedings{bhrushundi2018torus,
title={Torus polynomials: an algebraic approach to ACC lower bounds},
author={Bhrushundi, Abhishek and Hosseini, Kaave and Lovett, Shachar and Rao, Sankeerth},
booktitle={The 10th Innovations in Theoretical Computer Science (ITCS 2019)},
year={2019}
}
We propose an algebraic approach to proving circuit lower bounds for ACC0 by defining and studying the notion of torus polynomials. We show how currently known polynomial-based approximation results for AC0 and ACC0 can be reformulated in this framework, implying that ACC0 can be approximated by low-degree torus polynomials. Furthermore, as a step towards proving ACC0 lower bounds for the majority function via our approach, we show that MAJORITY cannot be approximated by low-degree symmetric torus polynomials. We also pose several open problems related to our framework.
2018
- Shachar Lovett. MDS matrices over small fields: A proof of the GM-MDS conjecture.
SIAM Journal of Computing, 50(4), 1248-1262, 2021.
Preliminary version appeared in the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018).
[pdf] [bib] [abstract]
@article{lovett2021sparse,
title={Sparse MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture},
author={Lovett, Shachar},
journal={SIAM Journal on Computing},
volume={50},
number={4},
pages={1248--1262},
year={2021},
publisher={SIAM}
}
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 characterization (called the MDS condition) which is necessary over any field, as well as 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, where the construction of the matrix is algebraic instead of probabilistic. This is known as the GM-MDS conjecture. Concretely, if a $k \times n$ zero pattern satisfies the MDS condition, then they conjecture that there exists an MDS matrix with this zero pattern over any field of size $|\mathbb{F}| \ge n+k-1$. In recent years, this conjecture was proven in several special cases. In this work, we resolve the conjecture.
- Xin Li, Shachar Lovett, Jiapeng Zhang. Sunflowers and Quasi-sunflowers from Randomness Extractors.
The 22th International Workshop on Randomization and Computation (RANDOM 2018).
[pdf] [bib] [abstract]
@article{li2018sunflowers,
author = {Xin Li and
Shachar Lovett and
Jiapeng Zhang},
title = {Sunflowers and Quasi-sunflowers from Randomness Extractors},
journal = {Electronic Colloquium on Computational Complexity {(ECCC)}},
volume = {25},
pages = {82},
year = {2018},
url = {https://eccc.weizmann.ac.il/report/2018/082},
}
The Erd\H{o}s-Rado sunflower theorem is a fundamental result in combinatorics, and the corresponding sunflower conjecture is a central open problem. Motivated by applications in complexity theory, Rossman (FOCS 2010) extended the result to quasi-sunflowers, where similar conjectures emerge about the optimal parameters for which it holds.
In this work, we exhibit a surprising connection between the existence of sunflowers and quasi-sunflowers in large enough set systems, and the problem of constructing (or existing) certain randomness extractors. This allows us to re-derive the known results in a systematic manner, and to reduce the relevant conjectures to the problem of obtaining improved constructions of the randomness extractors.
- Daniel Kane, Shachar Lovett, Shay Moran. Generalized comparison trees for point-location problems.
The 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018).
[pdf] [bib] [abstract]
@inproceedings{kane2018generalized,
title={Generalized comparison trees for point-location problems},
booktitle={The 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
author={Kane, Daniel and Lovett, Shachar and Moran, Shay},
year={2018},
Let $H$ be an arbitrary family of hyperplanes in $d$-dimensions. We show that the point-location problem for $H$
can be solved by a linear decision tree that only uses a special type of queries called generalized comparison queries.
These queries correspond to hyperplanes that can be written as a linear combination of two hyperplanes from $H$;
in particular, if all hyperplanes in $H$ are $k$-sparse then generalized comparisons are $2k$-sparse.
The depth of the obtained linear decision tree is polynomial in $d$ and logarithmic in $|H|$,
which is comparable to previous results in the literature that use general linear queries.
This extends the study of comparison trees from a previous work by the authors.
The main benefit is that using generalized comparison queries allows to
overcome limitations that apply for the more restricted type of comparison queries.
- Daniel Kane, Shachar Lovett, Shay Moran. Near-optimal linear decision trees for k-SUM and related problems.
Journal of the ACM (JACM), 66(3), article 16, 2019.
Preliminary version appeared in the 50th ACM Symposium on Theory of Computing (STOC 2018).
[pdf] [bib] [abstract]
@inproceedings{kane2018near,
title={Near-optimal linear decision trees for k-SUM and related problems},
author={Kane, Daniel M and Lovett, Shachar and Moran, Shay},
booktitle={Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing},
pages={554--563},
year={2018},
organization={ACM}
}
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.
- Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett. The Gram-Schmidt Walk - A Cure for the Banaszczyk Blues.
Theory of Computing 15(21), 2019, 1--27. Preliminary version appeared in the 50th ACM Symposium on Theory of Computing (STOC 2018).
[pdf] [bib] [abstract]
@article{bansal2019gram,
author = {Bansal, Nikhil and Dadush, Daniel and Garg, Shashwat and Lovett, Shachar},
title = {The Gram--Schmidt Walk: A Cure for the Banaszczyk Blues},
year = {2019},
pages = {1--27},
doi = {10.4086/toc.2019.v015a021},
publisher = {Theory of Computing},
journal = {Theory of Computing},
volume = {15},
number = {21},
URL = {http://www.theoryofcomputing.org/articles/v015a021},
}
An important result in discrepancy due to Banaszczyk states that for any set of $n$ vectors in $\mathbb{R}^m$ of $\ell_2$ norm at most $1$ and any convex body $K$ in $\mathbb{R}^m$ of Gaussian measure at least half, there exists a $\pm 1$ combination of these vectors which lies in $5K$. This result implies the best known bounds for several problems in discrepancy. Banaszczyk's proof of this result is non-constructive and a major open problem has been to give an efficient algorithm to find such a $\pm 1$ combination of the vectors.
In this paper, we resolve this question and give an efficient randomized algorithm to find a $\pm 1$ combination of the vectors which lies in $cK$ for $c>0$ an absolute constant.
This leads to new efficient algorithms for several problems in discrepancy theory.
- Marco Carmosino, Russel Impagliazzo, Shachar Lovett, Ivan Mihajlin. Hardness Amplification for Non-Commutative Arithmetic Circuits.
The 2018 Computational Complexity Conference (CCC 2018).
[pdf] [bib] [abstract]
@inproceedings{carmosino2018hardness,
title={ Hardness Amplification for Non-Commutative Arithmetic Circuits},
booktitle={The 2018 IEEE Conference on Computational Complexity (CCC 2018)},
author={Carmosino, Marco and Impagliazzo, Russell and Lovett, Shachar and Mihajlin, Ivan},
year={2018},
We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits
implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit
complexity is a threshold phenomenon: an apparently weak lower bound actually suffices to show
the strongest lower bounds we could desire.
This is part of a recent line of inquiry into why arithmetic circuit complexity, despite being a
heavily restricted version of Boolean complexity, still cannot prove super-linear lower bounds on
general devices. One can view our work as positive news (it suffices to prove weak lower bounds to
get strong ones) or negative news (it is as hard to prove weak lower bounds as it is to prove strong
ones). We leave it to the reader to determine their own level of optimism
- Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett. Pseudorandom Generators from Polarizing Random Walks.
Theory of Computing 15(10), 1-26, 2019. Preliminary version appeared in the 2018 Computational Complexity Conference (CCC 2018).
[pdf] [bib] [abstract]
@article{chattopadhyay2019pseudorandom,
author = {Chattopadhyay, Eshan and Hatami, Pooya and Hosseini, Kaave and Lovett, Shachar},
title = {Pseudorandom Generators from Polarizing Random Walks},
year = {2019},
pages = {1--26},
doi = {10.4086/toc.2019.v015a010},
publisher = {Theory of Computing},
journal = {Theory of Computing},
volume = {15},
number = {10},
URL = {http://www.theoryofcomputing.org/articles/v015a010},
}
We propose a new framework for constructing pseudorandom generators for $n$-variate Boolean functions. It is based on two new notions.
First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in $[-1,1]^n$. Next, we use a fractional pseudorandom generator as steps of a random walk in $[-1,1]^n$ that converges to $\{-1,1\}^n$. We prove that this random walk converges fast (in time logarithmic in $n$) due to polarization. As an application, we construct pseudorandom generators for Boolean functions with bounded Fourier tails. We use this to obtain a pseudorandom generator for functions with sensitivity $s$, whose seed length is polynomial in $s$. Other examples
include functions computed by branching programs of various sorts or by bounded depth circuits.
- Shachar Lovett, Sankeerth Rao, Alex Vardy. Probabilistic existence of large sets of designs.
The 2018 ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).
[pdf] [bib] [abstract]
@inproceedings{lovett2018probabilistic,
title={Probabilistic existence of large sets of designs},
author={Lovett, Shachar and Rao, Sankeerth and Vardy, Alexander},
booktitle={Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms},
pages={1545--1556},
year={2018},
organization={SIAM}
}
A new probabilistic technique for establishing the existence of certain regular combinatorial structures has been recently introduced by Kuperberg, Lovett, and Peled (STOC 2012). Using this technique, it can be shown that under certain conditions, a randomly chosen structure has the required properties of a $t$-$(n,k,\lambda)$ combinatorial design with tiny, yet positive, probability.
Herein, we strengthen both the method and the result of Kuperberg, Lovett, and Peled as follows. We modify the random choice and the analysisto show that, under the same conditions, not only does a $t$-$(n,k,\lambda)$ design exist but, in fact, with positive probability there exists a \emph{large set} of such designs - that is, a partition of the set of $k$-subsets of $[n]$ into $t$-designs $t$-$(n,k,\lambda)$ designs. Specifically, using the probabilistic approach derived herein, we prove that for all sufficiently large $n$, large sets of $t$-$(n,k,\lambda)$ designs exist whenever $k > 9t$nd the necessary divisibility conditions are satisied. This resolves the existence conjecture for large sets of designs for all $k > 9t$.
- Shachar Lovett, Avishay Tal, Jiapeng Zhang. The Robust Sensitivity of Boolean Functions.
The 2018 ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).
[pdf] [bib] [abstract]
@inproceedings{lovett2018robust,
title={The Robust Sensitivity of Boolean Functions},
author={Lovett, Shachar and Tal, Avishay and Zhang, Jiapeng},
booktitle={Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms},
pages={1822--1833},
year={2018},
organization={SIAM}
}
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.
2017
- Shachar Lovett, Jiapeng Zhang. On the impossibility of entropy reversal, and its application to zero-knowledge proofs.
The Fifteenth Theory of Cryptography Conference (TCC 2017).
[pdf] [bib] [abstract]
@inproceedings{lovett2017impossibility,
title={On the impossibility of entropy reversal, and its application to zero-knowledge proofs},
author={Lovett, Shachar and Zhang, Jiapeng},
booktitle={Theory of Cryptography Conference},
pages={31--55},
year={2017},
organization={Springer}
}
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.
- Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang. Active classification with comparison queries.
The 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017).
[pdf] [bib] [abstract]
@inproceedings{kane2017active,
title={Active classification with comparison queries},
author={Kane, Daniel and Lovett, Shachar and Moran, Shay and Zhang, Jiapeng},
booktitle={Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on},
year={2017},
publisher={IEEE},
}
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, Omega(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.
- Daniel Kane, Shachar Lovett, Sankeerth Rao. The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes.
The 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017).
[pdf] [bib] [abstract]
@inproceedings{kane2017independence,
title={The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes},
booktitle={Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on},
author={Kane, Daniel and Lovett, Shachar and Rao, Sankeerth},
year={2017},
publisher={IEEE},
}
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.
- Shachar Lovett. Additive Combinatorics and its Applications in Theoretical Computer Science.
Theory of computing, graduate survey #8.
[pdf] [bib] [abstract]
@book{gs008,
author = {Lovett, Shachar},
title = {Additive Combinatorics and its Applications in Theoretical Computer Science},
year = {2017},
pages = {1--55},
doi = {10.4086/toc.gs.2017.008},
publisher = {Theory of Computing Library},
number = {8},
series = {Graduate Surveys},
URL = {http://www.theoryofcomputing.org/library.html},
}
Additive combinatorics (or perhaps more accurately, arithmetic combinatorics) is a branch of mathematics which lies at the intersection of combinatorics, number theory, Fourier analysis and ergodic theory. It studies approximate notions of various algebraic structures, such as vector spaces or fields. In recent years, several connections between additive combinatorics and theoretical computer science have been discovered. Techniques and results from additive combinatorics have been applied to problems in coding theory, property testing, hardness of approximation, computational complexity, communication complexity, randomness extraction and pseudo-randomness. The goal of this survey is to provide an introduction to additive combinatorics for students and researchers in theoretical computer science, to illustrate some of the exciting connections to classical problems in theoretical computer science, and to describe the many open problems that remain.
- Shachar Lovett, Jiapeng Zhang. Noisy Population Recovery from Unknown Noise.
The 2017 Conference On Learning Theory (COLT 2017).
[pdf] [bib] [abstract]
@inproceedings{lovett2017noisy,
title={Noisy population recovery from unknown noise},
author={Lovett, Shachar and Zhang, Jiapeng},
booktitle={Conference on Learning Theory},
pages={1417--1431},
year={2017}
}
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.
- Kaave Hosseini, Shachar Lovett. On the structure of the spectrum of small sets.
Journal of Combinatorial Theory, Series A (148), pp. 1-14, 2017.
[pdf] [bib] [abstract]
@article{hosseini2017structure,
title={On the structure of the spectrum of small sets},
author={Hosseini, Kaave and Lovett, Shachar},
journal={Journal of Combinatorial Theory, Series A},
volume={148},
pages={1--14},
year={2017},
publisher={Elsevier}
}
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.
- Shachar Lovett, Oded Regev. A counterexample to a strong variant of the Polynomial Freiman-Ruzsa conjecture in Euclidean space.
Discrete Analysis 2017:8.
[pdf] [bib] [abstract]
@article{lovett2016counterexample,
title={A counterexample to a strong variant of the Polynomial Freiman-Ruzsa conjecture in Euclidean space},
author={Lovett, Shachar and Regev, Oded},
journal={Discrete Analysis},
year={2017}
}
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.
2016
- Hamed Hatami, Kaave Hosseini, Shachar Lovett. Structure of protocols for XOR functions.
SIAM Journal of Computing, 47(1), 208-217, 2018.
Preliminary version appeared in the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016).
[pdf] [bib] [abstract]
@article{hatami2018structure,
title={Structure of protocols for XOR functions},
author={Hatami, Hamed and Hosseini, Kaave and Lovett, Shachar},
journal={SIAM Journal on Computing},
volume={47},
number={1},
pages={208--217},
year={2018},
publisher={SIAM}
}
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.
- Esther Ezra, Shachar Lovett. On the Beck-Fiala Conjecture for Random Set Systems.
The 20th International Workshop on Randomization and Computation (RANDOM 2016).
[pdf] [bib] [abstract]
@inproceedings{ezra2016beck,
title={On the beck-fiala conjecture for random set systems},
author={Ezra, Esther and Lovett, Shachar},
booktitle={The 20th International Workshop on Randomization and Computation (RANDOM 2016)},
year={2016}
}
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.
- Daniel Dadush, Shashwat Garg, Shachar Lovett, Aleksandr Nikolov. Towards a constructive version of Banaszczyk's Vector Balancing Theorem.
Theory of Computing 15(15), 2019, 1-58.
Preliminary version appeared in the 20th International Workshop on Randomization and Computation (RANDOM 2016).
[pdf] [bib] [abstract]
@article{dadush2019towards,
author = {Dadush, Daniel and Garg, Shashwat and Lovett, Shachar and Nikolov, Aleksandar},
title = {Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem},
year = {2019},
pages = {1--58},
doi = {10.4086/toc.2019.v015a015},
publisher = {Theory of Computing},
journal = {Theory of Computing},
volume = {15},
number = {15},
URL = {http://www.theoryofcomputing.org/articles/v015a015},
}
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.
- Divesh Aggrawal, Kaave Hosseini, Shachar Lovett. Affine-malleable Extractors, Spectrum Doubling, and Application to Privacy Amplification.
The 2016 IEEE International Symposium on Information Theory (ISIT 2016).
[pdf] [bib] [abstract]
@inproceedings{aggarwal2016affine,
title={Affine-malleable extractors, spectrum doubling, and application to privacy amplification},
author={Aggarwal, Divesh and Hosseini, Kaave and Lovett, Shachar},
booktitle={Information Theory (ISIT), 2016 IEEE International Symposium on},
pages={2913--2917},
year={2016},
organization={IEEE}
}
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.
- Benny Applebaum, Shachar Lovett. Algebraic Attacks against Random Local Functions and Their Countermeasures.
SIAM Journal on Computing, 47:1, 52-79, 2018.
Preliminary version appeared in the 48th ACM Symposium on Theory of Computing (STOC 2016).
[pdf] [bib] [abstract]
@article{applebaum2018algebraic,
title={Algebraic attacks against random local functions and their countermeasures},
author={Applebaum, Benny and Lovett, Shachar},
journal={SIAM Journal on Computing},
volume={47},
number={1},
pages={52--79},
year={2018},
publisher={SIAM}
}
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.
- Kaave Hosseini, Shachar Lovett, Guy Moshkovitz, Asaf Shapira. An Improved Lower Bound for Arithmetic Regularity.
The Mathematical Proceedings of the Cambridge Philosophical Society 161 (2): 193-197, 2016.
[pdf] [bib] [abstract]
@inproceedings{hosseini2016improved,
title={An improved lower bound for arithmetic regularity},
author={Hosseini, Kaave and Lovett, Shachar and Moshkovitz, Guy and Shapira, Asaf},
booktitle={Mathematical Proceedings of the Cambridge Philosophical Society},
volume={161},
number={02},
pages={193--197},
year={2016},
organization={Cambridge Univ Press}
}
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.
- Hamed Hatami, Pooya Hatami, Shachar Lovett. General systems of linear forms: equidistribution and true complexity.
Advances in Mathematics (292), pp. 446-477, 2016.
[pdf] [bib] [abstract]
@article{hatami2016general,
title={General systems of linear forms: equidistribution and true complexity},
author={Hatami, Hamed and Hatami, Pooya and Lovett, Shachar},
journal={Advances in Mathematics},
volume={292},
pages={446--477},
year={2016},
publisher={Elsevier}
}
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.
2015
- 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).
[pdf] [bib] [abstract]
@inproceedings{anbalagan2015large,
title={Large Supports are required for Well-Supported Nash Equilibria},
author={Anbalagan, Yogesh and Huang, Hao and Lovett, Shachar and Norin, Sergey and Vetta, Adrian and Wu, Hehui},
booktitle={The 18th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'2015)},
year={2015}
}
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.
- Shachar Lovett. An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem.
Theory of computing, graduate survey #6.
[pdf] [bib] [abstract]
@book{gs006,
author = {Shachar Lovett},
title = {An Exposition of Sanders' Quasi-Polynomial Freiman-Ruzsa Theorem},
year = {2015},
pages = {1--14},
doi = {10.4086/toc.gs.2015.006},
publisher = {Theory of Computing Library},
number = {6},
series = {Graduate Surveys},
URL = {http://www.theoryofcomputing.org/library.html},
}
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.
- 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).
[pdf] [bib] [abstract]
@inproceedings{lovett2015improved,
title={Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions},
author={Lovett, Shachar and Zhang, Jiapeng},
booktitle={Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing},
pages={137--142},
year={2015},
organization={ACM}
}
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.
- Abhishek Bhowmick, Shachar Lovett. List decoding Reed-Muller codes over small fields.
IEEE Transactions on Information Theory 64(6), 2018. Preliminary version appeared in
the 47th ACM Symposium on Theory of Computing (STOC 2015).
[pdf] [bib] [abstract]
@article{bhowmick2018list,
title={The List Decoding Radius for Reed Muller codes over Small Fields},
author={Bhowmick, Abhishek and Lovett, Shachar},
journal={IEEE Transactions on Information Theory},
year={2018},
publisher={IEEE}
}
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.
- Mika Goos, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman. Rectangles Are Nonnegative Juntas.
The 47th ACM Symposium on Theory of Computing (STOC 2015).
[pdf] [bib] [abstract]
@inproceedings{goos2015rectangles,
title={Rectangles are nonnegative juntas},
author={G{\"o}{\"o}s, Mika and Lovett, Shachar and Meka, Raghu and Watson, Thomas and Zuckerman, David},
booktitle={Proceedings of the 47th Symposium on Theory of Computing (STOC)},
year={2015}
}
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.
- Abhishek Bhowmick, Shachar Lovett. Nonclassical polynomials as a barrier to polynomial lower bounds.
The 2015 Computational Complexity Conference (CCC 2015).
[pdf] [bib] [abstract]
@inproceedings{bhowmick2015nonclassical,
title={Nonclassical polynomials as a barrier to polynomial lower bounds},
author={Bhowmick, Abhishek and Lovett, Shachar},
booktitle={Proceedings of the 30th Conference on Computational Complexity},
pages={72--87},
year={2015},
organization={Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}
}
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.
2014
- 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.
[pdf] [bib] [abstract]
@article{fazeli2014nontrivial,
title={Nontrivial t-designs over finite fields exist for all t},
author={Fazeli, Arman and Lovett, Shachar and Vardy, Alexander},
journal={Journal of Combinatorial Theory, Series A},
volume={127},
pages={149--160},
year={2014},
publisher={Elsevier}
}
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.
- Shachar Lovett. Linear codes cannot approximate the network capacity within any constant factor.
Manuscript.
[pdf] [bib] [abstract]
@unpublished{lovett2014linear,
title={Linear codes cannot approximate the network capacity within any constant factor},
author={Lovett, Shachar},
booktitle={Electronic Colloquium on Computational Complexity (ECCC)},
year={2014}
}
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.
- 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).
[pdf] [bib] [abstract]
@incollection{gavinsky2014enroute,
year={2014},
booktitle={Automata, Languages, and Programming (ICALP 2014)},
volume={8572},
title={En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations},
author={Gavinsky, Dmitry and Lovett, Shachar},
pages={514-524},
}
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.
- Chaim Even-Zohar, Shachar Lovett. The Freiman-Ruzsa theorem in finite fields.
Journal of Combinatorial Theory A (125), pp. 333-341, 2014.
[pdf] [bib] [abstract]
@article{evenzohar2014freiman,
author={Chaim Even-Zohar and Shachar Lovett},
title={The Frieman-Ruzsa theorem in finite fields},
year={2014},
journal={Journal of Combinatorial Theory A},
number={125},
pages={333-341},
}
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.
- 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).
[pdf] [bib] [abstract]
@article{lovett2016communication,
title={Communication is bounded by root of rank},
author={Lovett, Shachar},
journal={Journal of the ACM (JACM)},
volume={63},
number={1},
pages={1},
year={2016},
publisher={ACM}
}
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.
- Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett. Non-malleable Codes from Additive Combinatorics.
SIAM Journal on Computing, 47(2), 524-546, 2018. Preliminary version appeared in the 46th ACM Symposium on Theory of Computing (STOC 2014).
[pdf] [bib] [abstract]
@article{aggarwal2018non,
title={Non-malleable codes from additive combinatorics},
author={Aggarwal, Divesh and Dodis, Yevgeniy and Lovett, Shachar},
journal={SIAM Journal on Computing},
volume={47},
number={2},
pages={524--546},
year={2018},
publisher={SIAM}
}
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.
- 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).
[pdf] [bib] [abstract]
@inproceedings{bachrach2014cooperative,
title={Cooperative weakest link games},
author={Bachrach, Yoram and Lev, Omer and Lovett, Shachar and Rosenschein, Jeffrey S and Zadimoghaddam, Morteza},
booktitle={Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems},
pages={589--596},
year={2014},
organization={International Foundation for Autonomous Agents and Multiagent Systems}
}
We introduce and study weakest link games, a cooperative game modelling domains where a team's value is determined by its weakest member.
- Shachar Lovett, Cris Moore, Alexander Russell. Group representations that resist random sampling.
Random Structures and Algorithms, 2014.
[pdf] [bib] [abstract]
@article{lovett2014group,
author={Shachar Lovett and Cris Moore and Alexander Russell},
title={Group representations that resist random sampling},
journal={Random Structures and Algorithms},
year={2014},
}
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.
- Dmitry Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan. A tail bound for read-k families of functions.
Random Structures and Algorithms, 2014.
[pdf] [bib] [abstract]
@article{gavinsky2014tail,
title={A tail bound for read-k families of functions},
author={Gavinsky, Dmitry and Lovett, Shachar and Saks, Michael and Srinivasan, Srikanth},
journal={Random Structures and Algorithms},
year={2014},
publisher={Wiley Online Library}
}
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$.
- Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider. 0-1 Integer Linear Programming with a Linear Number of Constraints.
Submitted.
[pdf] [bib] [abstract]
@unpublished{impagliazzo20140,
title={0-1 Integer Linear Programming with a Linear Number of Constraints},
author={Impagliazzo, Russell and Lovett, Shachar and Paturi, Ramamohan and Schneider, Stefan},
journal={arXiv preprint arXiv:1401.5512},
year={2014}
}
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.
2013
- Hamed Hatami, Shachar Lovett. Estimating the distance from testable affine-invariant properties.
The 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013).
[pdf] [bib] [abstract]
@inproceedings{hatami2013estimating,
title={Estimating the distance from testable affine-invariant properties},
author={Hatami, Hamed and Lovett, Shachar},
booktitle={Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on},
pages={237--242},
year={2013},
organization={IEEE}
}
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$.
- 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).
[pdf] [bib] [abstract]
@inproceedings{bhattacharyya2013every,
title={Every locally characterized affine-invariant property is testable},
author={Bhattacharyya, Arnab and Fischer, Eldar and Hatami, Hamed and Hatami, Pooya and Lovett, Shachar},
booktitle={Proceedings of the forty-fifth annual ACM symposium on Theory of computing},
pages={429--436},
year={2013},
organization={ACM}
}
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.
- Abhishek Bhowmick, Zeev Dvir, Shachar Lovett. New bounds for matching vector families.
The 45th ACM Symposium on Theory of Computing (STOC 2013).
[pdf] [bib] [abstract]
@inproceedings{bhowmick2013new,
title={New bounds for matching vector families},
author={Bhowmick, Abhishek and Dvir, Zeev and Lovett, Shachar},
booktitle={Proceedings of the forty-fifth annual ACM symposium on Theory of computing},
pages={823--832},
year={2013},
organization={ACM}
}
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.
- Zeev Dvir, Janos Kollar, Shachar Lovett. Variety evasive sets.
Computational Complexity, 1-21, 2012.
[pdf] [bib] [abstract]
@article{dvir2012variety,
title={Variety Evasive Sets},
author={Dvir, Zeev and Koll{\'a}r, J{\'a}nos and Lovett, Shachar},
journal={computational complexity},
pages={1--21},
year={2012},
publisher={Springer}
}
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).
- Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett. Testing low complexity affine invariant properties.
The 2013 ACM-SIAM Symposium on Discrete Algorithms (SODA 2013).
[pdf] [bib] [abstract]
@inproceedings{bhattacharyya2013testing,
title={Testing low complexity affine-invariant properties},
author={Bhattacharyya, Arnab and Fischer, Eldar and Lovett, Shachar},
booktitle={Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms},
pages={1337--1355},
year={2013},
organization={SIAM}
}
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.
2012
- 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).
[pdf] [bib] [abstract]
@inproceedings{ben2012additive,
title={An additive combinatorics approach relating rank to communication complexity},
author={Ben-Sasson, Eli and Lovett, Shachar and Ron-Zewi, Noga},
booktitle={Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on},
pages={177--186},
year={2012},
organization={IEEE}
}
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)$.
- 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).
[pdf] [bib] [abstract]
@inproceedings{beck2012large,
title={Large deviation bounds for decision trees and sampling lower bounds for AC0-circuits},
author={Beck, Chris and Impagliazzo, Russell and Lovett, Shachar},
booktitle={Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on},
pages={101--110},
year={2012},
organization={IEEE}
}
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.
- 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).
[pdf] [bib] [abstract]
@incollection{alon2012almost,
title={Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions},
author={Alon, Noga and Lovett, Shachar},
booktitle={Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques},
pages={350--361},
year={2012},
publisher={Springer}
}
We study distributions over permutations which are statistically close to being $k$-wise independent. We provide several probabilistic and explicit constructions of such distributions.
- Shachar Lovett, Raghu Meka. Constructive discrepancy minimization by walking on the edges.
SIAM Journal on Computing, 44:5, 1573-1582, 2015. Preliminary version appeared in the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012).
[pdf] [bib] [abstract]
@article{lovett2015contructive,
author = {Shachar Lovett and Raghu Meka},
title = {Constructive Discrepancy Minimization by Walking on the Edges},
journal = {SIAM Journal on Computing},
volume = {44},
number = {5},
pages = {1573-1582},
year = {2015},
}
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.
- Dmitry Gavinsky, Shachar Lovett, Srikanth Srinivasan.. Pseudorandom Generators for Read-Once ACC^0.
IEEE Conference on Computational Complexity (CCC 2012).
[pdf] [bib] [abstract]
@inproceedings{gavinsky2012pseudorandom,
title={Pseudorandom Generators for Read-Once ACC\^{} 0.},
author={Gavinsky, Dmitry and Lovett, Shachar and Srinivasan, Srikanth},
booktitle={IEEE Conference on Computational Complexity},
pages={287--297},
year={2012}
}
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.
- 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).
[pdf] [bib] [abstract]
@article{karnin2012unsupervised,
title={Unsupervised SVMs: On the complexity of the Furthest Hyperplane Problem},
author={Karnin, Zohar and Liberty, Edo and Lovett, Shachar and Schwartz, Roy and Weinstein, Omri},
journal={Journal of Machine Learning Research},
volume={1},
pages={18},
year={2012}
}
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.
- Shachar Lovett. Equivalence of polynomial conjectures in additive combinatorics.
Combinatorica 32(5), pp. 607-618, 2012.
[pdf] [bib] [abstract]
@article{lovett2012equivalence,
title={Equivalence of polynomial conjectures in additive combinatorics},
author={Lovett, Shachar},
journal={Combinatorica},
volume={32},
number={5},
pages={607--618},
year={2012},
publisher={Springer}
}
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.
- Greg Kuperberg, Shachar Lovett, Ron Peled. Probabilistic existence of regular combinatorial objects.
The 44th ACM Symposium on Theory of Computing (STOC 2012).
[pdf] [bib] [abstract]
@inproceedings{kuperberg2012probabilistic,
title={Probabilistic existence of rigid combinatorial structures},
author={Kuperberg, Greg and Lovett, Shachar and Peled, Ron},
booktitle={Proceedings of the forty-fourth annual ACM symposium on Theory of computing},
pages={1091--1106},
year={2012},
organization={ACM}
}
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.
- Zeev Dvir, Shachar Lovett. Subspace evasive sets.
The 44th ACM Symposium on Theory of Computing (STOC 2012).
[pdf] [bib] [abstract]
@inproceedings{dvir2012subspace,
title={Subspace evasive sets},
author={Dvir, Zeev and Lovett, Shachar},
booktitle={Proceedings of the forty-fourth annual ACM symposium on Theory of computing},
pages={351--358},
year={2012},
organization={ACM}
}
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.
2011
- 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).
[pdf] [bib] [abstract]
@inproceedings{kaufman2011new,
title={New extension of the Weil bound for character sums with applications to coding},
author={Kaufman, Tali and Lovett, Shachar},
booktitle={Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on},
pages={788--796},
year={2011},
organization={IEEE}
}
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.
- Shachar Lovett. Computing polynomials with few multiplications.
Theory of Computing 7(13), pp. 185-188, 2011.
[pdf] [bib] [abstract]
@article{lovett2011computing,
title={Computing Polynomials with Few Multiplications.},
author={Lovett, Shachar},
journal={Theory OF Computing},
volume={7},
number={1},
pages={185--188},
year={2011}
}
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
- 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).
[pdf] [bib] [abstract]
@incollection{lovett2011correlation,
title={Correlation Bounds for Poly-size AC0 circuits with n^{1-o(1)} Symmetric Gates},
author={Lovett, Shachar and Srinivasan, Srikanth},
booktitle={Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques},
pages={640--651},
year={2011},
publisher={Springer}
}
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.
- 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).
[pdf] [bib] [abstract]
@inproceedings{hatami2011correlation,
title={Correlation testing for affine invariant properties on F pn in the high error regime},
author={Hatami, Hamed and Lovett, Shachar},
booktitle={Proceedings of the forty-third annual ACM symposium on Theory of computing},
pages={187--194},
year={2011},
organization={ACM}
}
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.
- Arkadev Chattopadhyay, Shachar Lovett. Linear systems over finite abelian groups.
The 26th Conference on Computational Complexity (CCC 2011).
[pdf] [bib] [abstract]
@inproceedings{chattopadhyay2011linear,
title={Linear systems over finite abelian groups},
author={Chattopadhyay, Arkadev and Lovett, Shachar},
booktitle={Computational Complexity (CCC), 2011 IEEE 26th Annual Conference on},
pages={300--308},
year={2011},
organization={IEEE}
}
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.
- 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).
[pdf] [bib] [abstract]
@inproceedings{lovett2011bounded,
title={Bounded-depth circuits cannot sample good codes},
author={Lovett, Shachar and Viola, Emanuele},
booktitle={Computational Complexity (CCC), 2011 IEEE 26th Annual Conference on},
pages={243--251},
year={2011},
organization={IEEE}
}
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.
- 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.
[pdf] [bib] [abstract]
@article{hatami2011higher,
title={Higher-Order Fourier Analysis Of $\{$$\backslash$ mathbb $\{$F$\}$ \_ $\{$p$\}$\^{} n$\}$ And The Complexity Of Systems Of Linear Forms},
author={Hatami, Hamed and Lovett, Shachar},
journal={Geometric And Functional Analysis},
volume={21},
number={6},
pages={1331--1357},
year={2011},
publisher={Springer}
}
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.
2010
- 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).
[pdf] [bib] [abstract]
@article{lovett2013pseudorandom,
title={Pseudorandom generators for CC0 [p] and the Fourier spectrum of low-degree polynomials over finite fields},
author={Lovett, Shachar and Mukhopadhyay, Partha and Shpilka, Amir},
journal={computational complexity},
volume={22},
number={4},
pages={679--725},
year={2013},
publisher={Springer}
}
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.
- 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).
[pdf] [bib] [abstract]
@inproceedings{lovett2010lower,
title={A lower bound for dynamic approximate membership data structures},
author={Lovett, Shachar and Porat, Ely},
booktitle={Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on},
pages={797--804},
year={2010},
organization={IEEE}
}
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.
- Shachar Lovett. Holes in generalized Reed-Muller codes.
IEEE Transactions on Information Theory 56(6), pp. 2583-2586, 2010.
[pdf] [bib] [abstract]
@article{lovett2010holes,
title={Holes in Generalized Reed--Muller Codes},
author={Lovett, Shachar},
journal={Information Theory, IEEE Transactions on},
volume={56},
number={6},
pages={2583--2586},
year={2010},
publisher={IEEE}
}
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.
- 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).
[pdf] [bib] [abstract]
@article{kaufman2012weight,
title={Weight distribution and list-decoding size of reed--muller codes},
author={Kaufman, Tali and Lovett, Shachar and Porat, Ely},
journal={Information Theory, IEEE Transactions on},
volume={58},
number={5},
pages={2689--2696},
year={2012},
publisher={IEEE}
}
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.
2009
- Ido Ben-Eliezer, Shachar Lovett, Ariel Yadin. Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness.
Manuscript.
[pdf] [bib] [abstract]
@unpublished{beneliezer2009polynomial,
title={Polynomial threshold functions: Structure, approximation and pseudorandomness},
author={{Ben-Eliezer}, Ido and Lovett, Shachar and Yadin, Ariel},
journal={arXiv preprint arXiv:0911.3473},
year={2009}
}
We give several structural results on polynomial threshold functions. Several concurrent works established stronger results, hence this manuscript was never published.
- 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).
[pdf] [bib] [abstract]
@incollection{lovett2009pseudorandom,
title={Pseudorandom bit generators that fool modular sums},
author={Lovett, Shachar and Reingold, Omer and Trevisan, Luca and Vadhan, Salil},
booktitle={Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques},
pages={615--630},
year={2009},
publisher={Springer}
}
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$.
- 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).
[pdf] [bib] [abstract]
@article{gopalan2010complexity,
title={The complexity of Boolean functions in different characteristics},
author={Gopalan, Parikshit and Shpilka, Amir and Lovett, Shachar},
journal={computational complexity},
volume={19},
number={2},
pages={235--263},
year={2010},
publisher={Springer}
}
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$.
- Yevgeniy Dodis, Yael Tauman Kalai, Shachar Lovett. On cryptography with auxiliary input.
The 41st ACM Symposium on Theory of Computing (STOC 2009).
[pdf] [bib] [abstract]
@inproceedings{dodis2009cryptography,
title={On cryptography with auxiliary input},
author={Dodis, Yevgeniy and Kalai, Yael Tauman and Lovett, Shachar},
booktitle={Proceedings of the forty-first annual ACM symposium on Theory of computing},
pages={621--630},
year={2009},
organization={ACM}
}
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.
- 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).
[pdf] [bib] [abstract]
@article{beneliezer2012random,
title={Random low-degree polynomials are hard to approximate},
author={{Ben-Eliezer}, Ido and Hod, Rani and Lovett, Shachar},
journal={computational complexity},
volume={21},
number={1},
pages={63--81},
year={2012},
publisher={Springer}
}
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)$.
2008
- Tali Kaufman, Shachar Lovett. Worst case to average case reductions for polynomials.
The 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008).
[pdf] [bib] [abstract]
@inproceedings{kaufman2008worst,
title={Worst case to average case reductions for polynomials},
author={Kaufman, Tali and Lovett, Shachar},
booktitle={Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on},
pages={166--175},
year={2008},
organization={IEEE}
}
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.
- 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).
[pdf] [bib] [abstract]
@article{lovett2011inverse,
author = {Shachar Lovett and Roy Meshulam and Alex Samorodnitsky},
title = {Inverse Conjecture for the Gowers Norm is False},
year = {2011},
pages = {131--145},
doi = {10.4086/toc.2011.v007a009},
publisher = {Theory of Computing},
journal = {Theory of Computing},
volume = {7},
number = {9},
URL = {http://www.theoryofcomputing.org/articles/v007a009},
}
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.
- 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).
[pdf] [bib] [abstract]
@article{lovett2009unconditional,
author = {Shachar Lovett},
title = {Unconditional Pseudorandom Generators for Low Degree Polynomials},
year = {2009},
pages = {69--82},
doi = {10.4086/toc.2009.v005a003},
publisher = {Theory of Computing},
journal = {Theory of Computing},
volume = {5},
number = {3},
URL = {http://www.theoryofcomputing.org/articles/v005a003},
}
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.
- Shachar Lovett. Lower bounds for adaptive linearity tests.
The 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008).
[pdf] [bib] [abstract]
@inproceedings{lovett2008lower,
title={Lower bounds for adaptive linearity tests},
author={Lovett, Shachar},
booktitle={Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science},
pages={515--526},
year={2008}
}
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.
- 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.
[pdf] [bib] [abstract]
@article{lovett2008almost,
title={Almost Euclidean sections of the N-dimensional cross-polytope using O (N) random bits},
author={Lovett, Shachar and Sodin, Sasha},
journal={Communications in Contemporary Mathematics},
volume={10},
number={04},
pages={477--489},
year={2008},
publisher={World Scientific}
}
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.
- Shachar Lovett, Yoav Tzur. Explicit lower bound for fooling polynomials by the sum of small-bias generators.
Manuscript.
[pdf] [bib] [abstract]
@unpublished{lovett2009explicit,
title={Explicit lower bound for fooling polynomials by the sum of small-bias generators.},
author={Lovett, Shachar and Tzur, Yoav},
booktitle={Electronic Colloquium on Computational Complexity (ECCC)},
volume={16},
pages={88},
year={2009}
}
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.