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

• Language Generation with Infinite Contamination
• Anay Mehrotra, Grigoris Velegkas, Xifan Yu, Felix Zhou
• [Preprint] [Arxiv]
•  
• Language Identification in the Limit with Computational Trace
• Binghui Peng, Amin Saberi, Grigoris Velegkas
• [Preprint]
•  
• 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

• 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