Logo
Vasilis Kontonis vkonton[at]gmail.com

I am a Senior Researcher at Microsoft Research in New York City, working on AI as part of AI Frontiers. Previously, I was an IFML Postdoctoral Fellow at UT Austin, hosted by Adam Klivans and Raghu Meka. I received my PhD in Computer Science from the University of Wisconsin-Madison, where I was advised by Christos Tzamos. Prior to UW-Madison, I studied Electrical and Computer Engineering at the National Technical University of Athens, where I was advised by Dimitris Fotakis.

Here is my CV.

News

Publications

  1. Scaling Discovery through Test-Time Communication
    w/ J. Park, S. Garg, A. Krishnamurthy, D. Papailiopoulos
    Preprint, 2026

  2. MEMENTO: Teaching LLMs to Manage Their Own Context
    w/ Y. Zeng, S. Garg, L. Chen, H. Tang, Z. Wang, A. Awadallah, E. Horvitz, J. Langford, D. Papailiopoulos
    Selected for Oral Presentation
    COLM 2026

  3. Wait, Wait, Wait… Why Do Reasoning Models Loop?
    w/ C. Pipis, S. Garg, V. Shrivastava, A. Krishnamurthy, D. Papailiopoulos
    Spotlight Presentation
    ICML 2026

  4. Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions
    w/ J. Kim, K. Shah, S. M. Kakade, S. Chen
    Outstanding Paper Award
    ICML 2025

  5. Learning General Gaussian Mixtures with Efficient Score Matching
    w/ S. Chen, K. Shah
    COLT 2025

  6. Online Linear Classification with Massart Noise
    w/ I. Diakonikolas, C. Tzamos, N. Zarifis
    ICML 2025

  7. Oracle-Efficient Truncated Statistics
    w/ K. Karatapanis, C. Tzamos
    ICLR 2025

  8. Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
    w/ G. Chandrasekaran, A. Klivans, R. Meka, K. Stavropoulos
    Best Paper Award COLT 2024
    IPAM 2024 Long Talk Video

  9. Active Learning with Simple Questions
    w/ M. Ma, C. Tzamos
    COLT 2024

  10. Agnostically Learning Multi-index Models with Queries
    w/ I. Diakonikolas, D. Kane, C. Tzamos, N. Zarifis
    FOCS 2024
    Journal version: SIAM Journal on Computing, 2026

  11. Super Non-singular Decompositions of Polynomials and their
    Application to Robustly Learning Low-degree PTFs
    w/ I. Diakonikolas, D M. Kane, S. Liu, N. Zarifis
    STOC 2024

  12. Efficient Discrepancy Testing for Learning with Distribution Shift
    w/ G. Chandrasekaran, A. Klivans, K. Stavropoulos, A. Vasilyan
    NeurIPS 2024

  13. Active Classification with Few Queries under Misspecification
    w/ C. Tzamos, M. Ma
    Spotlight Presentation
    NeurIPS 2024

  14. Learning Noisy Halfspaces with a Margin: Massart is no Harder than Random
    w/ G. Chandrasekaran, K. Stavropoulos, K. Tian
    Spotlight Presentation
    NeurIPS 2024

  15. Optimizing Solution-Samplers for Combinatorial Problems:
    The Landscape of Policy Gradient Methods
    w/ C. Caramanis, D. Fotakis, A. Kalavasis, C. Tzamos
    Selected for Oral Presentation
    NeurIPS 2023

  16. SLaM: Student-Label Mixing for Distillation with Unlabeled Examples
    w/ F. Iliopoulos, K. Trinh, C. Baykal, G. Menghani, V. Erik
    NeurIPS 2023

  17. The Gain from Ordering in Online Learning
    w/ M. Ma, C. Tzamos
    NeurIPS 2023

  18. Efficient Testable Learning of Halfspaces with Adversarial Label Noise
    w/ I. Diakonikolas, D M. Kane, S. Liu, N. Zarifis
    NeurIPS 2023

  19. Self Directed Linear Classification
    w/ I. Diakonikolas, C. Tzamos, N. Zarifis
    COLT 2023

  20. Weighted Distillation with Unlabeled Examples
    w/ F. Iliopoulos, C. Baykal, G. Menghani, K. Trinh, V. Erik
    NeurIPS 2022

  21. Linear Label Ranking with Bounded Noise
    w/ D. Fotakis, A. Kalavasis, C. Tzamos
    Selected for Oral Presentation
    NeurIPS 2022

  22. Learning General Halfspaces with Adversarial Label Noise via Online Gradient Descent
    w/ I. Diakonikolas, C. Tzamos, N. Zarifis
    ICML 2022

  23. Learning a Single Neuron with Adversarial Label Noise via Gradient Descent
    w/ I. Diakonikolas, C. Tzamos, N. Zarifis
    COLT 2022

  24. Learning General Halfspaces with General Massart Noise under the Gaussian Distribution
    w/ I. Diakonikolas, D. Kane, C. Tzamos, N. Zarifis
    STOC 2022

  25. A Statistical Taylor Theorem and Extrapolation of Truncated Densities
    w/ C. Daskalakis, C. Tzamos, M. Zampetakis
    COLT 2021

  26. Agnostic Proper Learning of Halfspaces under Gaussian Marginals
    w/ I. Diakonikolas, D. Kane, C. Tzamos, N. Zarifis
    COLT 2021

  27. Efficient Algorithms for Learning from Coarse Labels
    w/ D. Fotakis, A. Kalavasis, C. Tzamos
    COLT 2021

  28. Learning Online Algorithms with Distributional Advice
    w/ I. Diakonikolas, C. Tzamos, A. Vakilian, N. Zarifis
    ICML 2021

  29. A Polynomial Time Algorithm For Learning Halfspaces with Tsybakov Noise
    w/ I. Diakonikolas, D. Kane, C. Tzamos, N. Zarifis
    STOC 2021

  30. Learning Halfspaces with Tsybakov Noise
    w/ I. Diakonikolas, C. Tzamos, N. Zarifis
    STOC 2021
    Conference version merged with the above paper

  31. Non-Convex SGD Learns Halfspaces with Adversarial Label Noise
    w/ I. Diakonikolas, C. Tzamos, N. Zarifis
    NeurIPS 2020

  32. Learning Halfspaces with Massart Noise Under Structured Distributions
    w/ I. Diakonikolas, C. Tzamos, N. Zarifis
    COLT 2020

  33. Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks
    w/ I. Diakonikolas, D. Kane, N. Zarifis
    COLT 2020

  34. Efficient Truncated Statistics with Unknown Truncation
    w/ C. Tzamos, M. Zampetakis
    FOCS 2019

  35. Removing Bias in Maching Learning via Truncated Statistics
    w/ C. Daskalakis, C. Tzamos, M. Zampetakis
    Manuscript

  36. Opinion Dynamics with Limited Information
    w/ D. Fotakis, V. Kandiros, S. Skoulakis
    WINE 2018

  37. Learning Powers of Poisson Binomial Distributions
    w/ D. Fotakis, P. Krysta, P. Spirakis
    Manuscript

Service

Talks