- 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**.*Submitted*.

[pdf] [bib] [abstract] - Max Hopkins, Daniel Kane, Shachar Lovett, Michal Moshkovitz.
**Bounded Memory Active Learning through Enriched Queries**.*Submitted*.

[pdf] [bib] [abstract] - Sankeerth Rao Karingula, Shachar Lovett.
**Codes over integers, and the singularity of random matrices with large entries**.*Submitted*.

[pdf] [bib] [abstract] - Max Hopkins, Tali Kaufman, Shachar Lovett.
**High Dimensional Expanders Random Walks, Pseudorandomness, and Unique Games**.*Submitted*.

[pdf] [bib] [abstract] - Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, Jiapeng Zhang.
**Lifting with sunflowers**.*Submitted*.

[pdf] [bib] [abstract] - Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, Abhishek Shetty.
**Fractional Pseudorandom Generators from Any Fourier Level**.*Accepted to the 2021 Computational Complexity Conference*(CCC 2021).

[pdf] [bib] [abstract] - Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan.
**Log-rank and lifting for AND-functions**.*Accepted to the 52st ACM Symposium on Theory of Computing*(STOC 2021).

[pdf] [bib] [abstract] - 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] - 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] - Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan.
**Point Location and Active Learning: Learning Halfspaces Almost Optimally**.*The 59th Annual IEEE Symposium on Foundations of Computer Science*(FOCS 2020).

[pdf] [bib] [abstract] - 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] - Hamed Hatami, Kaave Hosseini, Shachar Lovett.
**Sign rank vs Discrepancy**.*The 2020 Computational Complexity Conference*(CCC 2020).

[pdf] [bib] [abstract] - Shachar Lovett, Kewen Wu, Jiapeng Zhang.
**Decision list compression by mild random restrictions**.*The 51st ACM Symposium on Theory of Computing*(STOC 2020).

[pdf] [bib] [abstract] - Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang.
**Improved bounds for the sunflower lemma**.*The 51st ACM Symposium on Theory of Computing*(STOC 2020), best paper.

[pdf] [bib] [abstract] - Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman.
**XOR Lemmas for Resilient Functions Against Polynomials**.*The 51st ACM Symposium on Theory of Computing*(STOC 2020).

[pdf] [bib] [abstract] - Abhishek Bhowmick, Shachar Lovett.
**Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory**.*Accepted to Journal of Combinatorial Theory A*(JCTA).

[pdf] [bib] [abstract] - Shachar Lovett, Jiapeng Zhang.
**DNF sparsification beyond sunflowers**.*The 50th ACM Symposium on Theory of Computing*(STOC 2019).

[pdf] [bib] [abstract] - Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals.
**Equality Alone Does Not Simulate Randomness**.*The 2019 Computational Complexity Conference*(CCC 2019).

[pdf] [bib] [abstract] - Shachar Lovett, Noam Solomon, Jiapeng Zhang.
**From DNF compression to sunflower theorems via regularity**.*The 2019 Computational Complexity Conference*(CCC 2019).

[pdf] [bib] [abstract] - Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev.
**Optimality of Linear Sketching under Modular Updates**.*The 2019 Computational Complexity Conference*(CCC 2019).

[pdf] [bib] [abstract] - Kaave Hosseini, Shachar Lovett.
**A bilinear Bogolyubov-Ruzsa lemma with poly-logarithmic bounds**.*Discrete Analysis 2019:10.*

[pdf] [bib] [abstract] - Shachar Lovett.
**The analytic rank of tensors is subadditive, and its applications**.*Discrete Analysis 2019:7.*

[pdf] [bib] [abstract] - 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] - 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] - Shachar Lovett.
**MDS matrices over small fields: A proof of the GM-MDS conjecture**.*The 57th Annual IEEE Symposium on Foundations of Computer Science*(FOCS 2018).

[pdf] [bib] [abstract] - 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] - 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] - 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 in the 50th ACM Symposium on Theory of Computing*(STOC 2018).

[pdf] [bib] [abstract] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - Shachar Lovett.
**Additive Combinatorics and its Applications in Theoretical Computer Science**.*Theory of computing, graduate survey #8*.

[pdf] [bib] [abstract] - Shachar Lovett, Jiapeng Zhang.
**Noisy Population Recovery from Unknown Noise**.*The 2017 Conference On Learning Theory*(COLT 2017).

[pdf] [bib] [abstract] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - Shachar Lovett.
**An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem**.*Theory of computing, graduate survey #6*.

[pdf] [bib] [abstract] - 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] - 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] - 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] - Abhishek Bhowmick, Shachar Lovett.
**Nonclassical polynomials as a barrier to polynomial lower bounds**.*The 2015 Computational Complexity Conference*(CCC 2015).

[pdf] [bib] [abstract] - 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] - Shachar Lovett.
**Linear codes cannot approximate the network capacity within any constant factor**.*Manuscript*.

[pdf] [bib] [abstract] - 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] - 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] - 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] - 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] - 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] - Shachar Lovett, Cris Moore, Alexander Russell.
**Group representations that resist random sampling**.*Random Structures and Algorithms, 2014.*

[pdf] [bib] [abstract] - 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] - Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider.
**0-1 Integer Linear Programming with a Linear Number of Constraints**.*Submitted*.

[pdf] [bib] [abstract] - 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] - 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] - 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] - Zeev Dvir, Janos Kollar, Shachar Lovett.
**Variety evasive sets**.*Computational Complexity, 1-21, 2012.*

[pdf] [bib] [abstract] - 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] - 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] - 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] - 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] - 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] - Dmitry Gavinsky, Shachar Lovett, Srikanth Srinivasan..
**Pseudorandom Generators for Read-Once ACC^0**.*IEEE Conference on Computational Complexity*(CCC 2012).

[pdf] [bib] [abstract] - 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] - Shachar Lovett.
**Equivalence of polynomial conjectures in additive combinatorics**.*Combinatorica 32*(5), pp. 607-618, 2012.

[pdf] [bib] [abstract] - 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] - Zeev Dvir, Shachar Lovett.
**Subspace evasive sets**.*The 44th ACM Symposium on Theory of Computing*(STOC 2012).

[pdf] [bib] [abstract] - 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] - Shachar Lovett.
**Computing polynomials with few multiplications**.*Theory of Computing 7*(13), pp. 185-188, 2011.

[pdf] [bib] [abstract] - 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] - 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] - Arkadev Chattopadhyay, Shachar Lovett.
**Linear systems over finite abelian groups**.*The 26th Conference on Computational Complexity*(CCC 2011).

[pdf] [bib] [abstract] - 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] - 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] - 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] - 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] - Shachar Lovett.
**Holes in generalized Reed-Muller codes**.*IEEE Transactions on Information Theory 56*(6), pp. 2583-2586, 2010.

[pdf] [bib] [abstract] - 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] - Ido Ben-Eliezer, Shachar Lovett, Ariel Yadin.
**Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness**.*Manuscript*.

[pdf] [bib] [abstract] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - Shachar Lovett.
**Lower bounds for adaptive linearity tests**.*The 25th International Symposium on Theoretical Aspects of Computer Science*(STACS 2008).

[pdf] [bib] [abstract] - 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] - Shachar Lovett, Yoav Tzur.
**Explicit lower bound for fooling polynomials by the sum of small-bias generators**.*Manuscript*.

[pdf] [bib] [abstract]