Publications:

• Support Testing in the Huge Object Model

Tomer Adar, Eldar Fischer, Amit Levi

Manuscript, 2023

• Streaming Euclidean MST to a constant factor

Vincent Cohen-Addad, Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten

55th Annual ACM Symposium on Theory of Computing (STOC) 2023.

• Learnable Graph Convolutional Attention Networks

Adrian Javaloy, Pablo Sanchez-Martin, Amit Levi, Isabel Valera

11th International Conference on Learning Representations (ICLR) 2023.

• Graph Attention Retrospective

Kimon Fountoulakis, Amit Levi, Shenghao Yang, Aseem Baranwal, Aukosh Jagannath

Journal of Machine learning research (JMLR), volume 24, 2023.

Best paper award at GroundedML workshop at ICLR 2022. 

• New Streaming Algorithms for High Dimensional EMD and MST

Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten

54th Annual ACM Symposium on Theory of Computing (STOC) 2022.

• Learning and Testing Junta Distributions with Subcube Conditioning

Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten

34th Annual Conference on Learning Theory (COLT) 2021.

• Erasure-Resilient Sublinear-Time Graph Algorithms

Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma

12th Innovations in Theoretical Computer Science (ITCS) 2021.

• Limits of Ordered Graphs and their Applications

Omri Ben-Eliezer, Eldar Fischer, Amit Levi and Yuichi Yoshida

12th Innovations in Theoretical Computer Science (ITCS) 2021.

• Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning

Clement Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten

32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2021.

• Sentinel: universal analysis and insight for data systems

Brad Glasbergen, Michael Abebe, Khuzaima Daudjee, Amit Levi

VLDB 2020.

• Hard properties with (very) short PCPPs and their applications

Omri Ben-Eliezer, Eldar Fischer, Amit Levi, Ron D. Rothblum

11th Innovations in Theoretical Computer Science (ITCS) 2020.

• Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs

Amit Levi and Erik Waingarten

10th Innovations in Theoretical Computer Science (ITCS) 2019. 

• Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices

Amit Levi and Yuichi Yoshida

21st International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2018. 

• Tolerant Junta Testing and The Connection to Submodular Minimization and Function Isomorphism

Eric Blais, Clement Canonne, Talya Eden, Amit Levi, and Dana Ron 

ACM Transactions on Computation Theory (TOCT) 11 (4), 2019 (Preliminary version in SODA 2018).

• Approximately Counting Triangles in Sublinear Time

Talya Eden, Amit Levi, Dana Ron, and C. Seshadhri 

SIAM Journal on Computing (SICOMP) 46 (5), 2017 (Preliminary version in FOCS 2015).

• On the Converse of Talagrand's Influence Inequality

Saleet Klein, Amit Levi, Muli Safra, Clara Shikhelman and Yinon Spinka

Manuscript, 2015