Publications, preprints and expositions

Sorted by first publication date    (With summaries)

    Preprints
  1. Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang. Active classification with comparison queries.
    Submitted.
  2. Abhishek Bhowmick, Shachar Lovett. Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory.
    Submitted.
  3. Daniel Kane, Shachar Lovett, Shay Moran. Near-optimal linear decision trees for k-SUM and related problems.
    Submitted.
  4. Shachar Lovett, Jiapeng Zhang. On the impossibility of entropy reversal, and its application to zero-knowledge proofs.
    Submitted.
  5. Shachar Lovett, Sankeerth Rao, Alex Vardy. Probabilistic existence of large sets of designs.
    Submitted.
  6. Shachar Lovett, Avishay Tal, Jiapeng Zhang. Robust sensitivity.
    Submitted.
  7. Daniel Kane, Shachar Lovett, Sankeerth Rao. The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes.
    Submitted.

  8. 2017
  9. Shachar Lovett, Jiapeng Zhang. Noisy Population Recovery from Unknown Noise.
    Accepted to the 2017 Conference On Learning Theory (COLT 2017).
  10. Kaave Hosseini, Shachar Lovett. On the structure of the spectrum of small sets.
    Journal of Combinatorial Theory, Series A (148), pp. 1-14, 2017.
  11. Shachar Lovett, Oded Regev. A counterexample to a strong variant of the Polynomial Freiman-Ruzsa conjecture in Euclidean space.
    Discrete Analysis 2017:8.

  12. 2016
  13. 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).
  14. 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).
  15. 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).
  16. 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).
  17. Benny Applebaum, Shachar Lovett. Algebraic Attacks against Random Local Functions and Their Countermeasures.
    The 48th ACM Symposium on Theory of Computing (STOC 2016).
  18. Hamed Hatami, Pooya Hatami, Shachar Lovett. General systems of linear forms: equidistribution and true complexity.
    Advances in Mathematics (292), pp. 446-477, 2016.
  19. 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).

  20. 2015
  21. 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).
  22. Shachar Lovett. An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem.
    Theory of computing, graduate survey #6.
  23. 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).
  24. Abhishek Bhowmick, Shachar Lovett. List decoding Reed-Muller codes over small fields.
    The 47th ACM Symposium on Theory of Computing (STOC 2015).
  25. Mika Goos, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman. Rectangles Are Nonnegative Juntas.
    The 47th ACM Symposium on Theory of Computing (STOC 2015).
  26. Abhishek Bhowmick, Shachar Lovett. Nonclassical polynomials as a barrier to polynomial lower bounds.
    The 2015 IEEE Conference on Computational Complexity (CCC 2015).

  27. 2014
  28. 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.
  29. Shachar Lovett. Linear codes cannot approximate the network capacity within any constant factor.
    Manuscript.
  30. 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).
  31. Chaim Even-Zohar, Shachar Lovett. The Freiman-Ruzsa theorem in finite fields.
    Journal of Combinatorial Theory A (125), pp. 333-341, 2014.
  32. Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett. Non-malleable Codes from Additive Combinatorics.
    The 46th ACM Symposium on Theory of Computing (STOC 2014).
  33. 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.
  34. 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).
  35. Shachar Lovett, Cris Moore, Alexander Russell. Group representations that resist random sampling.
    Random Structures and Algorithms, 2014.
  36. Dmitry Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan. A tail bound for read-k families of functions.
    Random Structures and Algorithms, 2014.
  37. Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider. 0-1 Integer Linear Programming with a Linear Number of Constraints.
    Submitted.

  38. 2013
  39. Hamed Hatami, Shachar Lovett. Estimating the distance from testable affine-invariant properties.
    The 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013).
  40. 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).
  41. Abhishek Bhowmick, Zeev Dvir, Shachar Lovett. New bounds for matching vector families.
    The 45th ACM Symposium on Theory of Computing (STOC 2013).
  42. Zeev Dvir, Janos Kollar, Shachar Lovett. Variety evasive sets.
    Computational Complexity, 1-21, 2012.
  43. Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett. Testing low complexity affine invariant properties.
    The 2013 ACM-SIAM Symposium on Discrete Algorithms (SODA 2013).

  44. 2012
  45. 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).
  46. 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).
  47. 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).
  48. 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).
  49. Dmitry Gavinsky, Shachar Lovett, Srikanth Srinivasan.. Pseudorandom Generators for Read-Once ACC^0.
    IEEE Conference on Computational Complexity (CCC 2012).
  50. 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).
  51. Shachar Lovett. Equivalence of polynomial conjectures in additive combinatorics.
    Combinatorica 32(5), pp. 607-618, 2012.
  52. Greg Kuperberg, Shachar Lovett, Ron Peled. Probabilistic existence of regular combinatorial objects.
    The 44th ACM Symposium on Theory of Computing (STOC 2012).
  53. Zeev Dvir, Shachar Lovett. Subspace evasive sets.
    The 44th ACM Symposium on Theory of Computing (STOC 2012).

  54. 2011
  55. 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).
  56. Shachar Lovett. Computing polynomials with few multiplications.
    Theory of Computing 7(13), pp. 185-188, 2011.
  57. 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).
  58. 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).
  59. Arkadev Chattopadhyay, Shachar Lovett. Linear systems over finite abelian groups.
    The 26th Conference on Computational Complexity (CCC 2011).
  60. 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).
  61. 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.

  62. 2010
  63. 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).
  64. 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).
  65. Shachar Lovett. Holes in generalized Reed-Muller codes.
    IEEE Transactions on Information Theory 56(6), pp. 2583-2586, 2010.
  66. 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).

  67. 2009
  68. Ido Ben-Eliezer, Shachar Lovett, Ariel Yadin. Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness.
    Manuscript.
  69. 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).
  70. 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).
  71. Yevgeniy Dodis, Yael Tauman Kalai, Shachar Lovett. On cryptography with auxiliary input.
    The 41st ACM Symposium on Theory of Computing (STOC 2009).
  72. 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).

  73. 2008
  74. Tali Kaufman, Shachar Lovett. Worst case to average case reductions for polynomials.
    The 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008).
  75. 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).
  76. 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).
  77. Shachar Lovett. Lower bounds for adaptive linearity tests.
    The 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008).
  78. 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.
  79. Shachar Lovett, Yoav Tzur. Explicit lower bound for fooling polynomials by the sum of small-bias generators.
    Manuscript.
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.