Hi! I am an Assistant Professor in the CSE department in UC San Diego.
I am part of the Theory of Computation group and help
run the theory seminar.
I have a broad interest in theoretical computer science and mathematics. In particular
computational complexity, randomness and pseudo-randomness, algebraic constructions,
coding theory, discrete mathematics and additive combinatorics.
I am supported by an NSF CAREER award 1350481, an NSF CCF award 1614023, and a Sloan fellowship.
Sasha Kulikov and I created a website that aggregates information on all Theory CS events: cstheory-events.org
Current teaching (previous years):
Recent publications: (full list, including preprints)
- Shachar Lovett, Jiapeng Zhang. Noisy Population Recovery from Unknown Noise. Accepted to COLT 2017.
- Shachar Lovett, Oded Regev. A counterexample to a strong variant of the Polynomial Freiman-Ruzsa conjecture in Euclidean space. Discrete Analysis 2017:8.
- Kaave Hosseini, Shachar Lovett. On the structure of the spectrum of small sets. Journal of Combinatorial Theory (A), 2017.
- Hamed Hatami, Kaave Hosseini, Shachar Lovett. Structure of protocols for XOR functions. FOCS 2016.
- Esther Ezra, Shachar Lovett. On the Beck-Fiala Conjecture for Random Set Systems. RANDOM 2016.
- Daniel Dadush, Shashwat Garg, Shachar Lovett, Aleksandr Nikolov. Towards a constructive version of Banaszczyk's Vector Balancing Theorem. RANDOM 2016.
- Benny Applebaum, Shachar Lovett. Algebraic Attacks against Random Local Functions and Their Countermeasures. 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).
- 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.
Email: slovett (at) cs.ucsd.edu
Office: CSE 4234
Snail mail: University of California, San Diego
Computer Science & Engineering Department
9500 Gilman Drive, Mail code 0404
La Jolla, CA 92093-0404, USA