Scholars 2010

2010 Future - Computers and Telecommunications

Lovett Shachar

Personal Details:
Weizmann Institute of Science, Department of Computer Science 

Title of Research:
"Low-degree Polynomials and Applications in Theoretical Computer Science" 

 

Shachar Lovett is an Assistant Professor in the CSE department in UC San Diego. He contributes to the Theory of Computation group and assists with the theory seminar.

He has 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. He is supported by an NSF CAREER award 1350481, an NSF CCF award 1614023, and a Sloan fellowship.

http://cseweb.ucsd.edu/~slovett/home.html

His most recent publications include:

  1. Daniel Kane, Shachar Lovett, Shay Moran. Generalized comparison trees for point-location problems
    Accepted to the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018).
    [pdf]    [bib]    [abstract]
  2. Daniel Kane, Shachar Lovett, Shay Moran. Near-optimal linear decision trees for k-SUM and related problems
    Accepted to the 50th ACM Symposium on Theory of Computing (STOC 2018).
    [pdf]    [bib]    [abstract]
  3. Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett. The Gram-Schmidt Walk - A Cure for the Banaszczyk Blues
    Accepted to the 50th ACM Symposium on Theory of Computing (STOC 2018).
    [pdf]    [bib]    [abstract]
  4. Marco Carmosino, Russel Impagliazzo, Shachar Lovett, Ivan Mihajlin. Hardness Amplification for Non-Commutative Arithmetic Circuits
    Accepted to the 2018 IEEE Conference on Computational Complexity (CCC 2018).
    [pdf]    [bib]    [abstract]
  5. Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett. Pseudorandom Generators from Polarizing Random Walks
    Accepted to the 2018 IEEE Conference on Computational Complexity (CCC 2018).
    [pdf]    [bib]    [abstract]
  6. 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]
  7. 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]