**Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang.**Active classification with comparison queries.*Submitted*.**Abhishek Bhowmick, Shachar Lovett.**Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory.*Submitted*.**Daniel Kane, Shachar Lovett, Shay Moran.**Near-optimal linear decision trees for k-SUM and related problems.*Submitted*.**Shachar Lovett, Jiapeng Zhang.**On the impossibility of entropy reversal, and its application to zero-knowledge proofs.*Submitted*.**Shachar Lovett, Sankeerth Rao, Alex Vardy.**Probabilistic existence of large sets of designs.*Submitted*.**Shachar Lovett, Avishay Tal, Jiapeng Zhang.**Robust sensitivity.*Submitted*.**Daniel Kane, Shachar Lovett, Sankeerth Rao.**The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes.*Submitted*.**Shachar Lovett, Jiapeng Zhang.**Noisy Population Recovery from Unknown Noise.*Accepted to the 2017 Conference On Learning Theory*(COLT 2017).**Kaave Hosseini, Shachar Lovett.**On the structure of the spectrum of small sets.*Journal of Combinatorial Theory, Series A*(148), pp. 1-14, 2017.**Shachar Lovett, Oded Regev.**A counterexample to a strong variant of the Polynomial Freiman-Ruzsa conjecture in Euclidean space.*Discrete Analysis 2017:8*.**Hamed Hatami, Kaave Hosseini, Shachar Lovett.**Structure of protocols for XOR functions.*Accepted to the 57th Annual IEEE Symposium on Foundations of Computer Science*(FOCS 2016).**Esther Ezra, Shachar Lovett.**On the Beck-Fiala Conjecture for Random Set Systems.*Accepted to the 20th International Workshop on Randomization and Computation*(RANDOM 2016).**Daniel Dadush, Shashwat Garg, Shachar Lovett, Aleksandr Nikolov.**Towards a constructive version of Banaszczyk's Vector Balancing Theorem.*Accepted to the 20th International Workshop on Randomization and Computation*(RANDOM 2016).**Divesh Aggrawal, Kaave Hosseini, Shachar Lovett.**Affine-malleable Extractors, Spectrum Doubling, and Application to Privacy Amplification.*Accepted to the 2016 IEEE International Symposium on Information Theory*(ISIT 2016).**Benny Applebaum, Shachar Lovett.**Algebraic Attacks against Random Local Functions and Their Countermeasures.*The 48th ACM Symposium on Theory of Computing*(STOC 2016).**Hamed Hatami, Pooya Hatami, Shachar Lovett.**General systems of linear forms: equidistribution and true complexity.*Advances in Mathematics*(292), pp. 446-477, 2016.**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).**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).**Shachar Lovett.**An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem.*Theory of computing, graduate survey #6*.**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).**Abhishek Bhowmick, Shachar Lovett.**List decoding Reed-Muller codes over small fields.*The 47th ACM Symposium on Theory of Computing*(STOC 2015).**Mika Goos, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman.**Rectangles Are Nonnegative Juntas.*The 47th ACM Symposium on Theory of Computing*(STOC 2015).**Abhishek Bhowmick, Shachar Lovett.**Nonclassical polynomials as a barrier to polynomial lower bounds.*The 2015 IEEE Conference on Computational Complexity*(CCC 2015).**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.**Shachar Lovett.**Linear codes cannot approximate the network capacity within any constant factor.*Manuscript*.**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).**Chaim Even-Zohar, Shachar Lovett.**The Freiman-Ruzsa theorem in finite fields.*Journal of Combinatorial Theory A*(125), pp. 333-341, 2014.**Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett.**Non-malleable Codes from Additive Combinatorics.*The 46th ACM Symposium on Theory of Computing*(STOC 2014).**Kaave Hosseini, Shachar Lovett, Guy Moshkovitz, Asaf Shapira.**An Improved Lower Bound for Arithmetic Regularity.

To appear in*the Mathematical Proceedings of the Cambridge Philosophical Society*.**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).**Shachar Lovett, Cris Moore, Alexander Russell.**Group representations that resist random sampling.*Random Structures and Algorithms, 2014.***Dmitry Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan.**A tail bound for read-k families of functions.*Random Structures and Algorithms, 2014.***Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider.**0-1 Integer Linear Programming with a Linear Number of Constraints.*Submitted*.**Hamed Hatami, Shachar Lovett.**Estimating the distance from testable affine-invariant properties.*The 54th Annual IEEE Symposium on Foundations of Computer Science*(FOCS 2013).**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).**Abhishek Bhowmick, Zeev Dvir, Shachar Lovett.**New bounds for matching vector families.*The 45th ACM Symposium on Theory of Computing*(STOC 2013).**Zeev Dvir, Janos Kollar, Shachar Lovett.**Variety evasive sets.*Computational Complexity, 1-21, 2012.***Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett.**Testing low complexity affine invariant properties.*The 2013 ACM-SIAM Symposium on Discrete Algorithms*(SODA 2013).**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).**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).**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).**Shachar Lovett, Raghu Meka.**Constructive discrepancy minimization by walking on the edges.*SIAM Journal on Computing, 44:5, 1573-1582, 2015. Preliminary version appeared at the 53rd Annual IEEE Symposium on Foundations of Computer Science*(FOCS 2012).**Dmitry Gavinsky, Shachar Lovett, Srikanth Srinivasan..**Pseudorandom Generators for Read-Once ACC^0.*IEEE Conference on Computational Complexity*(CCC 2012).**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).**Shachar Lovett.**Equivalence of polynomial conjectures in additive combinatorics.*Combinatorica 32*(5), pp. 607-618, 2012.**Greg Kuperberg, Shachar Lovett, Ron Peled.**Probabilistic existence of regular combinatorial objects.*The 44th ACM Symposium on Theory of Computing*(STOC 2012).**Zeev Dvir, Shachar Lovett.**Subspace evasive sets.*The 44th ACM Symposium on Theory of Computing*(STOC 2012).**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).**Shachar Lovett.**Computing polynomials with few multiplications.*Theory of Computing 7*(13), pp. 185-188, 2011.**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).**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).**Arkadev Chattopadhyay, Shachar Lovett.**Linear systems over finite abelian groups.*The 26th Conference on Computational Complexity*(CCC 2011).**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).**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.**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).**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).**Shachar Lovett.**Holes in generalized Reed-Muller codes.*IEEE Transactions on Information Theory 56*(6), pp. 2583-2586, 2010.**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).**Ido Ben-Eliezer, Shachar Lovett, Ariel Yadin.**Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness.*Manuscript*.**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).**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).**Yevgeniy Dodis, Yael Tauman Kalai, Shachar Lovett.**On cryptography with auxiliary input.*The 41st ACM Symposium on Theory of Computing*(STOC 2009).**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).**Tali Kaufman, Shachar Lovett.**Worst case to average case reductions for polynomials.*The 49th Annual IEEE Symposium on Foundations of Computer Science*(FOCS 2008).**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).**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).**Shachar Lovett.**Lower bounds for adaptive linearity tests.*The 25th International Symposium on Theoretical Aspects of Computer Science*(STACS 2008).**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.**Shachar Lovett, Yoav Tzur.**Explicit lower bound for fooling polynomials by the sum of small-bias generators.*Manuscript*.