I am a Senior Research Scientist at Google Research in Mountain View, where I work on problems related to LLM reasoning and the content ecosystem. I received my PhD in Computer Science from Yale University. My advisor was Amin Karbasi.
My research focuses on learning theory and mechanism design. In summer 2023, I was a research intern at Google Research in Mountain View, hosted by
Andres Perlroth and Gagan Aggarwal.
From October 2023 until May 2024 I was a student researcher at Google Research hosted by Yuan Deng.
In summer 2024, I was a research intern at Google Research in New York hosted by William Kong.
Before coming to Yale, I completed my undergrad studies at NTUA majoring in computer science and electrical engineering, where I worked with Dimitris Fotakis.
email: gvelegkas41 AT gmail DOT com
Selected Publications
See the complete list by year.
2027
-
On Language Generation in the Limit with Bounded Memory
Jon Kleinberg, Anay Mehrotra, Amin Saberi, Grigoris Velegkas
[SODA 2027; to appear] [arXiv]
2026
-
On the Learning Curves of Revenue Maximization
Steve Hanneke, Alkis Kalavasis, Shay Moran, Grigoris Velegkas
[STOC 2026] [arXiv] -
Forging Self-Funded Marketplaces among Strategic Agents
Yuan Deng, Vasilis Gkatzelis, Xizhi Tan, Grigoris Velegkas, Song Zuo
[EC 2026; extended abstract] [arXiv]
2025
-
On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode Collapse
Alkis Kalavasis, Anay Mehrotra, Grigoris Velegkas
[STOC 2025] [Arxiv]
2024
-
Replicable Learning of Large-Margin Halfspaces
Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas, Felix Zhou
[ICML 2024 (Spotlight)] [Arxiv]
2023
-
Optimal Learners for Realizable Regression: PAC Learning and Online Learning
Idan Attias, Steve Hanneke, Alkis Kalavasis, Amin Karbasi, Grigoris Velegkas
[NeurIPS 2023 (Oral Presentation)] [Arxiv]
2022
-
Universal Rates for Interactive Learning
Steve Hanneke, Amin Karbasi, Shay Moran, Grigoris Velegkas
[NeurIPS 2022 (Oral Presentation)] [NeurIPS Proceedings]
Complete Publications
Authors are listed in alphabetical order, unless denoted by (*).
2027
-
On Language Generation in the Limit with Bounded Memory
Jon Kleinberg, Anay Mehrotra, Amin Saberi, Grigoris Velegkas
[SODA 2027; to appear] [arXiv]
2026
-
Majority-of-Three is an Optimal PAC Learner
Grigoris Velegkas
[NeurIPS 2026; to appear] [OpenReview] -
Learning Distributions from Multiple Data Providers
Jon Kleinberg, Amin Saberi, Xizhi Tan, Grigoris Velegkas
[NeurIPS 2026; to appear] [arXiv] -
Pointwise Lipschitz Continuous Graph Algorithms
Quanquan C. Liu, Grigoris Velegkas, Yuichi Yoshida, Felix Zhou
[NeurIPS 2026; to appear] [arXiv] -
Forging Self-Funded Marketplaces among Strategic Agents
Yuan Deng, Vasilis Gkatzelis, Xizhi Tan, Grigoris Velegkas, Song Zuo
[EC 2026; extended abstract] [arXiv] -
Language Generation with Infinite Contamination
Anay Mehrotra, Grigoris Velegkas, Xifan Yu, Felix Zhou
[COLT 2026] [Proceedings] -
Differentially Private Language Generation and Identification in the Limit
Anay Mehrotra, Grigoris Velegkas, Xifan Yu, Felix Zhou
[COLT 2026; extended abstract] [Proceedings] -
On the Learning Curves of Revenue Maximization
Steve Hanneke, Alkis Kalavasis, Shay Moran, Grigoris Velegkas
[STOC 2026] [arXiv] -
A Theory of Data Acquisition and Pricing at Scale
Andrew Ilyas, Amin Saberi, Grigoris Velegkas
[ICML 2026] [Proceedings] -
Language Generation with Feedback: Queries and Mistakes
Steve Hanneke, Amin Karbasi, Anay Mehrotra, Grigoris Velegkas
[ICML 2026] [Proceedings] -
Language Identification in the Limit with Computational Trace
Binghui Peng, Amin Saberi, Grigoris Velegkas
[ICLR 2026] [Proceedings] -
On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability
Alkis Kalavasis, Anay Mehrotra, Grigoris Velegkas
[ALT 2026] [Proceedings]
2025
-
On Agnostic PAC Learning in the Small Error Regime
Julian Asilis, Mikael Møller Høgsgaard, Grigoris Velegkas
[NeurIPS 2025 (Spotlight)] [Arxiv] -
On Union-Closedness of Language Generation
Steve Hanneke, Amin Karbasi, Anay Mehrotra, Grigoris Velegkas
[NeurIPS 2025] [Arxiv] -
(Im)possibility of Automated Hallucination Detection in Large Language Models
Amin Karbasi, Omar Montasser, John Sous, Grigoris Velegkas
[COLM 2025] [Arxiv] -
Procurement Auctions via Approximately Optimal Submodular Optimization
Yuan Deng, Amin Karbasi, Vahab Mirrokni, Renato Paes Leme, Grigoris Velegkas, Song Zuo
[ICML 2025 (Spotlight)] [Arxiv] -
On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode Collapse
Alkis Kalavasis, Anay Mehrotra, Grigoris Velegkas
[STOC 2025] [Arxiv] -
Understanding Aggregations of Proper Learners in Multiclass Classification
Julian Asilis, Mikael Møller Høgsgaard, Grigoris Velegkas
[ALT 2025] [Arxiv]
2024
-
Injecting Undetectable Backdoors in Deep Learning and Language Models
Alkis Kalavasis, Amin Karbasi, Argyris Oikonomou, Katerina Sotiraki, Grigoris Velegkas, Manolis Zampetakis
[NeurIPS 2024] [Arxiv] -
Randomized Truthful Auctions with Learning Agents
Gagan Aggarwal, Anupam Gupta, Andres Perlroth, Grigoris Velegkas
[NeurIPS 2024] [Arxiv] -
Universal Rates for Active Learning
Steve Hanneke, Amin Karbasi, Shay Moran, Grigoris Velegkas
[NeurIPS 2024] [NeurIPS Proceedings] -
On the Computational Landscape of Replicable Learning
Alkis Kalavasis, Amin Karbasi, Grigoris Velegkas, Felix Zhou
[NeurIPS 2024] [Arxiv] -
Universal Rates for Regression: Separations between Cut-Off and Absolute Loss
Idan Attias, Steve Hanneke, Alkis Kalavasis, Amin Karbasi, Grigoris Velegkas
[COLT 2024] [COLT Proceedings] -
Replicable Learning of Large-Margin Halfspaces
Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas, Felix Zhou
[ICML 2024 (Spotlight)] [Arxiv] -
User Response in Ad Auctions: An MDP Formulation of Long-term Revenue Optimization
Yang Cai, Zhe Feng, Christopher Liaw, Aranyak Mehta, Grigoris Velegkas
[WWW 2024] [WWW Proceedings]
2023
-
Optimal Learners for Realizable Regression: PAC Learning and Online Learning
Idan Attias, Steve Hanneke, Alkis Kalavasis, Amin Karbasi, Grigoris Velegkas
[NeurIPS 2023 (Oral Presentation)] [Arxiv] -
Replicable Clustering
Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni, Grigoris Velegkas, Felix Zhou
[NeurIPS 2023] [Arxiv] -
Replicability in Reinforcement Learning
Amin Karbasi, Grigoris Velegkas, Lin F. Yang, Felix Zhou
[NeurIPS 2023] [Arxiv] -
Statistical Indistinguishability of Learning Algorithms
Alkis Kalavasis, Amin Karbasi, Shay Moran, Grigoris Velegkas
[ICML 2023] [Arxiv] -
Replicable Bandits
Hossein Esfandiari, Alkis Kalavasis, Amin Karbasi, Andreas Krause, Vahab Mirrokni, Grigoris Velegkas
[ICLR 2023] [Arxiv]
2022
-
Universal Rates for Interactive Learning
Steve Hanneke, Amin Karbasi, Shay Moran, Grigoris Velegkas
[NeurIPS 2022 (Oral Presentation)] [NeurIPS Proceedings] -
Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes
Alkis Kalavasis(*), Grigoris Velegkas(*), Amin Karbasi
[NeurIPS 2022] [Arxiv] -
Reinforcement Learning with Logarithmic Regret and Policy Switches
Grigoris Velegkas(*), Zhuoran Yang, Amin Karbasi
[NeurIPS 2022] [NeurIPS Proceedings] -
Is Selling Complete Information (Approximately) Optimal?
Dirk Bergemann, Yang Cai, Grigoris Velegkas, Mingfei Zhao
[EC 2022] [Arxiv]
2021
Teaching
Co-Instructor, Stanford University · Autumn 2026
MS&E 319: Efficient Generative Language Models
Co-taught with Amin Karbasi, Anay Mehrotra, and Amin Saberi.
Community & Service
Organizing & Mentoring
- Workshop co-organizer: Understanding Large Language Models via a TCS Lens, STOC 2026, June 25–26, 2026, with Anay Mehrotra and Amin Saberi.
- Workshop co-organizer: Language Generation Day, Stanford University, March 6, 2026, with Anay Mehrotra and Amin Saberi.
- Reading-group co-organizer: REFORM, Stanford University, Spring 2026, with Anay Mehrotra and Amin Saberi.
- Intern mentoring: Felix Zhou, Ioannis Anagnostides, and Weiqiang Zheng (Google, summer 2026).
- Mentor: Fall 2026 Learning Theory Alliance (LeT-All) Virtual Workshop, November 16, 2026.
Academic Service
- Area chair: Conference on Language Modeling (COLM), 2026.
- Program committee: ITCS 2027; ALT 2027; EC 2025–2026; WINE 2025–2026; COLT 2025–2026.
- Journal reviewer: ACM Transactions on Economics and Computation (TEAC); Journal of Machine Learning Research (JMLR); Proceedings of the National Academy of Sciences (PNAS).
- Conference reviewer / subreviewer: The ACM Web Conference (WWW), 2027; NeurIPS, ICML, ICLR, FOCS, STOC, SODA, WINE.
Awards
- Leventis Foundation Scholarship for Academic Excellence, 2024-2025
- Onassis Foundation Scholarship for Academic Excellence, 2020-2024
- Bodossaki Foundation Scholarship for Academic Excellence, 2020-2024
- Gerondelis Foundation Scholarship for Academic Excellence, 2019-2020
- Eurobank "A great moment for education" Award, 2013
Selected Talks
2026
-
Reliable Language Generation
Simons Institute for the Theory of Computing, Trustworthy AI: From Hallucinations to Reliable Autonomy · October 5, 2026
[Talk] [Video] -
On the Learning Curves of Revenue Maximization
Stanford Theory Lunch · April 30, 2026
2025
-
Language Identification, Generation, and Hallucination Detection in the Limit
FLaNN online seminar · October 20, 2025
[Video] -
Language Generation in the Limit
COLT tutorial · June 30, 2025
Validity–breadth trade-off, with Anay Mehrotra
[Tutorial and materials] -
Understanding the Trade-Offs Between Hallucinations and Mode Collapse in Language Generation
MIT CSAIL, Algorithms & Complexity Seminar · May 1, 2025
[Talk]