Shachar Lovett

ORCID

Publication Activity (10 Years)

Years Active: 2007-2024
Publications (10 Years): 142

Top Venues

Electron. Colloquium Comput. Complex.

CoRR

STOC

SIAM J. Comput.

Publications

Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan
Realizable Learning is All You Need. TheoretiCS 3 (2024)
Zander Kelley, Shachar Lovett, Raghu Meka
Explicit Separations between Randomized and Deterministic Number-on-Forehead Communication. STOC (2024)
Hamed Hatami, Kaave Hosseini, Shachar Lovett, Anthony Ostuni
Refuting Approaches to the Log-Rank Conjecture for XOR Functions. ICALP (2024)
Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. STOC (2024)
Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. Electron. Colloquium Comput. Complex. (2023)
Hamed Hatami, Kaave Hosseini, Shachar Lovett, Anthony Ostuni
Refuting approaches to the log-rank conjecture for XOR functions. Electron. Colloquium Comput. Complex. (2023)
Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan
Do PAC-Learners Learn the Marginal Distribution? CoRR (2023)
Daniel Beaglehole, Max Hopkins, Daniel Kane, Sihan Liu, Shachar Lovett
Sampling Equilibria: Fast No-Regret Learning in Structured Games. SODA (2023)
Hamed Hatami, Kaave Hosseini, Shachar Lovett, Anthony Ostuni
Refuting approaches to the log-rank conjecture for XOR functions. CoRR (2023)
Shachar Lovett, Jiapeng Zhang
Streaming Lower Bounds and Asymmetric Set-Disjointness. FOCS (2023)
Zander Kelley, Shachar Lovett, Raghu Meka
Explicit separations between randomized and deterministic Number-on-Forehead communication. CoRR (2023)
Shachar Lovett, Jiapeng Zhang
Fractional Certificates for Bounded Functions. ITCS (2023)
Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. CoRR (2023)
Shachar Lovett, Jiapeng Zhang
Streaming Lower Bounds and Asymmetric Set-Disjointness. CoRR (2023)
Zander Kelley, Shachar Lovett, Raghu Meka
Explicit separations between randomized and deterministic Number-on-Forehead communication. Electron. Colloquium Comput. Complex. (2023)
Abhishek Bhowmick, Shachar Lovett
Bias vs Structure of Polynomials in Large Fields, and Applications in Information Theory. IEEE Trans. Inf. Theory 69 (2) (2023)
Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan, Csaba Szepesvári, Gellért Weisz
Exponential Hardness of Reinforcement Learning with Linear Function Approximation. CoRR (2023)
Sihan Liu, Gaurav Mahajan, Daniel Kane, Shachar Lovett, Gellért Weisz, Csaba Szepesvári
Exponential Hardness of Reinforcement Learning with Linear Function Approximation. COLT (2023)
Shachar Lovett, Jiapeng Zhang
Streaming Lower Bounds and Asymmetric Set-Disjointness. Electron. Colloquium Comput. Complex. (2023)
Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan
Computational-Statistical Gap in Reinforcement Learning. COLT (2022)
Daniel Kane, Sihan Liu, Shachar Lovett, Gaurav Mahajan
Computational-Statistical Gaps in Reinforcement Learning. CoRR (2022)
Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, Jiapeng Zhang
Lifting with Sunflowers. ITCS (2022)
Kaave Hosseini, Hamed Hatami, Shachar Lovett
Sign-Rank vs. Discrepancy. Theory Comput. 18 (2022)
Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett, Ruizhe Zhang
Eigenstripping, Spectral Decay, and Edge-Expansion on Posets. CoRR (2022)
Shachar Lovett, Jiapeng Zhang
Fractional certificates for bounded functions. Electron. Colloquium Comput. Complex. (2022)
Xin Li, Shachar Lovett, Jiapeng Zhang
Sunflowers and Robust Sunflowers from Randomness Extractors. Theory Comput. 18 (2022)
Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett
High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games. SODA (2022)
Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett
Hypercontractivity on high dimensional expanders. STOC (2022)
Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett, Ruizhe Zhang
Eigenstripping, Spectral Decay, and Edge-Expansion on Posets. APPROX/RANDOM (2022)
Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan
Realizable Learning is All You Need. COLT (2022)
Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan
Realizable Learning is All You Need. CoRR (2021)
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. ICML (2021)
Max Hopkins, Daniel Kane, Shachar Lovett, Michal Moshkovitz
Bounded Memory Active Learning through Enriched Queries. COLT (2021)
Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, Abhishek Shetty
Fractional Pseudorandom Generators from Any Fourier Level. Computational Complexity Conference (2021)
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. CoRR (2021)
Shachar Lovett
Sparse MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture. SIAM J. Comput. 50 (4) (2021)
Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan
Guest Column: Models of computation between decision trees and communication. SIGACT News 52 (2) (2021)
Shachar Lovett, Kewen Wu, Jiapeng Zhang
Decision List Compression by Mild Random Restrictions. J. ACM 68 (6) (2021)
Max Hopkins, Daniel Kane, Shachar Lovett, Michal Moshkovitz
Bounded Memory Active Learning through Enriched Queries. CoRR (2021)
Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett
Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments. Electron. Colloquium Comput. Complex. 28 (2021)
Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan
Log-rank and lifting for AND-functions. STOC (2021)
Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett
Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments. CoRR (2021)
Sankeerth Rao Karingula, Shachar Lovett
Singularity of Random Integer Matrices with Large Entries. APPROX-RANDOM (2021)
Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan
Point Location and Active Learning: Learning Halfspaces Almost Optimally. FOCS (2020)
Sankeerth Rao Karingula, Shachar Lovett
Codes over integers, and the singularity of random matrices with large entries. Electron. Colloquium Comput. Complex. 27 (2020)
Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang
Improved bounds for the sunflower lemma. STOC (2020)
Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan
Point Location and Active Learning: Learning Halfspaces Almost Optimally. CoRR (2020)
Hamed Hatami, Kaave Hosseini, Shachar Lovett
Sign Rank vs Discrepancy. Computational Complexity Conference (2020)
Alon Gonen, Shachar Lovett, Michal Moshkovitz
Towards a combinatorial characterization of bounded memory learning. CoRR (2020)
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman
XOR lemmas for resilient functions against polynomials. STOC (2020)
Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, Abhishek Shetty
Fractional Pseudorandom Generators from Any Fourier Level. CoRR (2020)
Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan
Log-rank and lifting for AND-functions. CoRR (2020)
Max Hopkins, Daniel Kane, Shachar Lovett
The Power of Comparisons for Actively Learning Linear Classifiers. NeurIPS (2020)
Shachar Lovett, Sankeerth Rao, Alexander Vardy
Probabilistic existence of large sets of designs. J. Comb. Theory, Ser. A 176 (2020)
Shachar Lovett, Raghu Meka, Jiapeng Zhang
Improved lifting theorems via robust sunflowers. Electron. Colloquium Comput. Complex. 27 (2020)
Max Hopkins, Tali Kaufman, Shachar Lovett
High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games. Electron. Colloquium Comput. Complex. 27 (2020)
Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan
Log-rank and lifting for AND-functions. Electron. Colloquium Comput. Complex. 27 (2020)
Alon Gonen, Shachar Lovett, Michal Moshkovitz
Towards a Combinatorial Characterization of Bounded-Memory Learning. NeurIPS (2020)
Sankeerth Rao Karingula, Shachar Lovett
Codes over integers, and the singularity of random matrices with large entries. CoRR (2020)
Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan
Noise-tolerant, Reliable Active Classification with Comparison Queries. COLT (2020)
Shachar Lovett, Kewen Wu, Jiapeng Zhang
Decision list compression by mild random restrictions. STOC (2020)
Max Hopkins, Tali Kaufman, Shachar Lovett
High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games. CoRR (2020)
Max Hopkins, Daniel Kane, Shachar Lovett, Gaurav Mahajan
Noise-tolerant, Reliable Active Classification with Comparison Queries. CoRR (2020)
Shachar Lovett, Jiapeng Zhang
DNF sparsification beyond sunflowers. STOC (2019)
Max Hopkins, Daniel M. Kane, Shachar Lovett
The Power of Comparisons for Actively Learning Linear Classifiers. CoRR (2019)
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett
Pseudorandom Generators from Polarizing Random Walks. Theory Comput. 15 (2019)
Hamed Hatami, Pooya Hatami, Shachar Lovett
Higher-order Fourier Analysis and Applications. Found. Trends Theor. Comput. Sci. 13 (4) (2019)
Esther Ezra, Shachar Lovett
On the Beck-Fiala conjecture for random set systems. Random Struct. Algorithms 54 (4) (2019)
Shachar Lovett, Kewen Wu, Jiapeng Zhang
Decision list compression by mild random restrictions. Electron. Colloquium Comput. Complex. 26 (2019)
Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett
The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues. Theory Comput. 15 (2019)
Shachar Lovett, Noam Solomon, Jiapeng Zhang
From DNF compression to sunflower theorems via regularity. CoRR (2019)
Daniel M. Kane, Shachar Lovett, Shay Moran
Near-optimal Linear Decision Trees for k-SUM and Related Problems. J. ACM 66 (3) (2019)
Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang
Improved bounds for the sunflower lemma. CoRR (2019)
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman
XOR Lemmas for Resilient Functions Against Polynomials. Electron. Colloquium Comput. Complex. 26 (2019)
Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao
Torus Polynomials: An Algebraic Approach to ACC Lower Bounds. ITCS (2019)
Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang
Improved bounds for the sunflower lemma. Electron. Colloquium Comput. Complex. 26 (2019)
Hamed Hatami, Kaave Hosseini, Shachar Lovett
Sign rank vs Discrepancy. Electron. Colloquium Comput. Complex. 26 (2019)
Shachar Lovett, Noam Solomon, Jiapeng Zhang
From DNF Compression to Sunflower Theorems via Regularity. Computational Complexity Conference (2019)
Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev
Optimality of Linear Sketching Under Modular Updates. Computational Complexity Conference (2019)
Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals
Equality Alone Does not Simulate Randomness. Computational Complexity Conference (2019)
Shachar Lovett, Noam Solomon, Jiapeng Zhang
From DNF compression to sunflower theorems via regularity. Electron. Colloquium Comput. Complex. 26 (2019)
Daniel Dadush, Shashwat Garg, Shachar Lovett, Aleksandar Nikolov
Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem. Theory Comput. 15 (2019)
Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal
Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates. ITCS (2019)
Daniel Kane, Shachar Lovett, Sankeerth Rao
The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes. SIAM J. Comput. 48 (4) (2019)
Shachar Lovett, Kewen Wu, Jiapeng Zhang
Decision list compression by mild random restrictions. CoRR (2019)
Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev
Optimality of Linear Sketching under Modular Updates. Electron. Colloquium Comput. Complex. 25 (2018)
Shachar Lovett
A proof of the GM-MDS conjecture. Electron. Colloquium Comput. Complex. 25 (2018)
Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao
Torus polynomials: an algebraic approach to ACC lower bounds. Electron. Colloquium Comput. Complex. 25 (2018)
Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev
Optimality of Linear Sketching under Modular Updates. CoRR (2018)
Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal
Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates. Electron. Colloquium Comput. Complex. 25 (2018)
Xin Li, Shachar Lovett, Jiapeng Zhang
Sunflowers and Quasi-Sunflowers from Randomness Extractors. APPROX-RANDOM (2018)
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett
Pseudorandom Generators from Polarizing Random Walks. Electron. Colloquium Comput. Complex. 25 (2018)
Shachar Lovett, Jiapeng Zhang
DNF sparsification beyond sunflowers. Electron. Colloquium Comput. Complex. 25 (2018)
Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin
Hardness Amplification for Non-Commutative Arithmetic Circuits. Electron. Colloquium Comput. Complex. 25 (2018)
Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals
Equality Alone Does Not Simulate Randomness. Electron. Colloquium Comput. Complex. 25 (2018)
Benny Applebaum, Shachar Lovett
Algebraic Attacks against Random Local Functions and Their Countermeasures. SIAM J. Comput. 47 (1) (2018)
Daniel M. Kane, Shachar Lovett, Shay Moran
Generalized comparison trees for point-location problems. CoRR (2018)
Shachar Lovett, Avishay Tal, Jiapeng Zhang
The Robust Sensitivity of Boolean Functions. SODA (2018)
Daniel M. Kane, Shachar Lovett, Shay Moran
Generalized comparison trees for point-location problems. Electron. Colloquium Comput. Complex. 25 (2018)
Nikhil Bansal, Daniel Dadush, Shashwat Garg, Shachar Lovett
The gram-schmidt walk: a cure for the Banaszczyk blues. STOC (2018)

Shachar Lovett.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Shachar Lovett