University Logo Header

הפקולטה למדעי המחשב והמידע

אוניברסיטת חיפה

EN

University Logo Header
להרשמה
Amit Levi

Dr. Amit Levi

עברית | English

About▼

Dr. Amit Levi is a Senior Lecturer (Assistant Professor) in the Department of Computer Science at the University of Haifa, where he works in theoretical computer science, with a primary focus on sublinear algorithms. His research also covers learning on graphs and approximation algorithms.

Publications▼

  • Optimal mass estimation in the conditional sampling model, Adar, T., Fischer, E. & Levi, A., 2026, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026. Larsen, K. G. & Saha, B. (eds.). Association for Computing Machinery, p. 4105-4174 70 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2026-January).
  • Testing Ck-Freeness in Bounded Admissibility Graphs, Awofeso, C., Greaves, P., Lachish, O., Levi, A. & Reidl, F., 30 Jun 2025, 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025. Censor-Hillel, K., Grandoni, F., Ouaknine, J. & Puppis, G. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 15. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 334).
  • Testing vs Estimation for Index-Invariant Properties in the Huge Object Model, Chakraborty, S., Fischer, E., Ghosh, A., Levi, A., Mishra, G. & Sen, S., 15 Jun 2025, STOC 2025 - Proceedings of the 57th Annual ACM Symposium on Theory of Computing. Koucky, M. & Bansal, N. (eds.). Association for Computing Machinery, p. 1007-1018 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).
  • Improved Bounds for High-Dimensional Equivalence and Product Testing Using Subcube Queries, Adar, T., Fischer, E. & Levi, A., Sep 2024, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024. Kumar, A. & Ron-Zewi, N. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 48. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 317).
  • Support Testing in the Huge Object Model, Adar, T., Fischer, E. & Levi, A., Sep 2024, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024. Kumar, A. & Ron-Zewi, N. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 46. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 317).
  • Streaming Euclidean MST to a Constant Factor, Chen, X., Cohen-Addad, V., Jayaram, R., Levi, A. & Waingarten, E., 2 Jun 2023, STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing. Saha, B. & Servedio, R. A. (eds.). Association for Computing Machinery, p. 156-169 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).
  • Graph Attention Retrospective, Fountoulakis, K., Levi, A., Yang, S., Baranwal, A. & Jagannath, A., 2023, In: Journal of Machine Learning Research. 24, p. 1-52 52 p.
  • Learnable Graph Convolutional Attention Networks, Javaloy, A., Sánchez-Martín, P., Levi, A. & Valera, I., 2023.
  • New streaming algorithms for high dimensional EMD and MST, Chen, X., Jayaram, R., Levi, A. & Waingarten, E., 6 Sep 2022, STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Leonardi, S. & Gupta, A. (eds.). Association for Computing Machinery, p. 222-233 12 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).
  • Erasure-Resilient Sublinear-Time Graph Algorithms, Levi, A., Pallavoor, R. K. S., Raskhodnikova, S. & Varma, N., Mar 2022, In: ACM Transactions on Computation Theory. 14, 1, 1.
  • Erasure-resilient sublinear-time graph algorithms, Levi, A., Pallavoor, R. K. S., Raskhodnikova, S. & Varma, N., 1 Feb 2021, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021. Lee, J. R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 80. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 185).
  • Ordered graph limits and their applications, Ben-Eliezer, O., Fischer, E., Levi, A. & Yoshida, Y., 1 Feb 2021, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021. Lee, J. R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 42. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 185).
  • Random restrictions of high dimensional distributions and uniformity testing with subcube conditioning, Canonne, C. L., Chen, X., Kamath, G., Levi, A. & Waingarten, E., 2021, ACM-SIAM Symposium on Discrete Algorithms, SODA 2021. Marx, D. (ed.). Association for Computing Machinery, p. 321-336 16 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
  • Learning and Testing Junta Distributions with Subcube Conditioning, Chen, X., Jayaram, R., Levi, A. & Waingarten, E., 2021, In: Proceedings of Machine Learning Research. 134, p. 1060-1113 54 p.
  • Hard properties with (very) short Pcpps and their applications, Ben-Eliezer, O., Fischer, E., Levi, A. & Rothblum, R. D., Jan 2020, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020. Vidick, T. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 9. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 151).
  • Nearly optimal edge estimation with independent set queries, Chen, X., Levi, A. & Waingarten, E., 2020, 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. Chawla, S. (ed.). Association for Computing Machinery, p. 2916-2935 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2020-January).
  • Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism, Blais, E., Canonne, C. L., Eden, T., Levi, A. & Ron, D., Sep 2019, In: ACM Transactions on Computation Theory. 11, 4, 24.
  • Lower bounds for tolerant junta and unateness testing via rejection sampling of graphs, Levi, A. & Waingarten, E., 1 Jan 2019, 10th Innovations in Theoretical Computer Science, ITCS 2019. Blum, A. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 52. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 124).
  • Sublinear-time quadratic minimization via spectral decomposition of matrices, Levi, A. & Yoshida, Y., 1 Aug 2018, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018. Blais, E., Rolim, J. D. P., Steurer, D. & Jansen, K. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 17. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 116).
  • Tolerant junta testing and the connection to submodular optimization and function isomorphism, Blais, E., Canonne, C. L., Eden, T., Levi, A. & Ron, D., 2018, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Czumaj, A. (ed.). Association for Computing Machinery, p. 2113-2132 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
  • Approximately counting triangles in sublinear time, Eden, T., Levi, A., Ron, D. & Seshadhr, C., 2017, In: SIAM Journal on Computing. 46, 5, p. 1603-1646 44 p.
  • Approximately Counting Triangles in Sublinear Time, Eden, T., Levi, A., Ron, D. & Seshadhri, C., 11 Dec 2015, Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015. IEEE Computer Society, p. 614-633 20 p. 7354418. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2015-December).

Education▼

Dr. Levi earned his PhD in Computer Science from the University of Waterloo, under the supervision of Eric Blais. Before joining the University of Haifa, he was a researcher at Huawei's Noah's Ark Lab in Montreal

Research Areas▼

Property testing, graph algorithms, sampling, estimation, and algorithms for very large data structures.