Hello! I am a Research Scientist at Google Research in Mountain View. 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
Preprints
Authors are listed in alphabetical order, unless denoted by (*).
- Characterizations of Language Generation With Breadth
- Alkis Kalavasis, Anay Mehrotra, Grigoris Velegkas
-
[Preprint]
[Arxiv]
-
- Pointwise Lipschitz Continuous Graph Algorithms via Proximal Gradient Analysis
- Quanquan Liu, Grigoris Velegkas, Yuichi Yoshida, Felix Zhou
-
[Preprint]
[Arxiv]
-
Publications
Authors are listed in alphabetical order, unless denoted by (*).
- 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]
-
- 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]
-
- 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]
-
- 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]
-
- An Efficient ε-BIC to BIC Transformation and Its Application to Black-Box Reduction in Revenue Maximization
- Yang Cai, Argyris Oikonomou, Grigoris Velegkas, Mingfei Zhao
-
[SODA 2021]
[Arxiv]
-
- How to Sell Information Optimally: an Algorithmic Study
- Yang Cai, Grigoris Velegkas
-
[ITCS 2021]
[Arxiv]
-
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