2 citations · 8 across the 30 of their papers we have counts for
37 papers
Query Feedback and Teaching for Stable and Certifiable Language Generation
Farnam Mansouri, Alireza F. Pour, Grigoris Velegkas +1
Language generation in the limit studies whether a learner observing an enumeration of an unknown target language can eventually generate only valid, previously unseen elements. We…
Cogentic: Multi-Agent Orchestration for Automated Proof Discovery
Yang Cai, Vineet Gupta, Yanchen Jiang +4
We present Cogentic, a multi-agent harness for automated proof discovery on open research problems. While frontier language models can generate strong mathematical ideas in a singl…
Efficiency of Generalized Proportional First-Price Auctions Under Auto-bidding
Yang Cai, Vineet Gupta, Yanchen Jiang +4
Auto-bidding is now widely adopted in online advertising platforms, allowing advertisers to specify high-level campaign objectives--such as maximizing total value subject to a retu…
Improved Revenue Guarantees for Selling Separately and Bundling
Yang Cai, Vineet Gupta, Yanchen Jiang +4
We study how much revenue a seller can lose by restricting attention to selling separately or grand bundling, in the setting of a single additive buyer with independent item values…
The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets
Yang Cai, Vineet Gupta, Yanchen Jiang +5
We study Bulow-Klemperer-style competition complexity in two-sided double auctions with unit-demand buyers drawn i.i.d. from and unit-supply sellers drawn i.i.d. from…
Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant
Yang Cai, Vineet Gupta, Yanchen Jiang +4
Prediction with expert advice is a fundamental problem in online learning. When the time horizon is known in advance, the minimax cumulative regret over experts is asymptot…
Efficient Online Inverse Optimization with Regret
Yang Cai, Anupam Gupta, Vineet Gupta +7
We give a deterministic algorithm for online inverse linear optimization with regret , uniform in the horizon and time per round. A bound of this order was obtaine…
Forging Self-Funded Marketplaces among Strategic Agents
Yuan Deng, Vasilis Gkatzelis, Xizhi Tan +2
We introduce the problem of designing mechanisms that incentivize strategic agents to form self-funded marketplaces. In our model, if agent exerts effort , they i…
From Compensation Design to Budget-Feasible Mechanisms: A Constant Approximation for Subadditive Valuations
Ioannis Anagnostides, Kshipra Bhawalkar, Christopher Liaw +3
Budget-feasible mechanism design is a classic framework introduced by Singer, but there is still a wide gap between existing upper and lower bounds. In this paper, we significantly…
Learning Distributions from Multiple Data Providers
Jon Kleinberg, Amin Saberi, Xizhi Tan +1
Motivated by learning from heterogeneous and overlapping data providers, we study a stylized model of distribution learning from restricted conditional samples. The goal is to lear…
Compensation Design
Ioannis Anagnostides, Kshipra Bhawalkar, Christopher Liaw +5
We introduce compensation design, the problem of designing payment rules that incentivize high-quality contributions in decentralized environments. Here, a budget-constrained princ…
On Language Generation in the Limit with Bounded Memory
Jon Kleinberg, Anay Mehrotra, Amin Saberi +1
We study language generation in the limit under bounded memory. In this task, a learner observes examples from an unknown target language one at a time and must eventually output o…
What is Learnable in Valiant's Theory of the Learnable?
Steve Hanneke, Anay Mehrotra, Grigoris Velegkas +1
Valiant's 1984 paper is widely credited with introducing the PAC learning model, but it, in fact, introduced a different model: unlike PAC learning, the learner receives only posit…
On the Learning Curves of Revenue Maximization
Steve Hanneke, Alkis Kalavasis, Shay Moran +1
Learning curves are a fundamental primitive in supervised learning, describing how an algorithm's performance improves with more data and providing a quantitative measure of its ge…
Differentially Private Language Generation and Identification in the Limit
Anay Mehrotra, Grigoris Velegkas, Xifan Yu +1
We initiate the study of language generation in the limit, a model recently introduced by Kleinberg and Mullainathan [KM24], under the constraint of differential privacy. We consid…
Language Generation with Infinite Contamination
Anay Mehrotra, Grigoris Velegkas, Xifan Yu +1
We study language generation in the limit, where an algorithm observes an adversarial enumeration of strings from an unknown target language and must eventually generate new, u…
On Union-Closedness of Language Generation
Steve Hanneke, Amin Karbasi, Anay Mehrotra +1
We investigate language generation in the limit - a model by Kleinberg and Mullainathan [NeurIPS 2024] and extended by Li, Raman, and Tewari [COLT 2025]. While Kleinberg and Mullai…
(Im)possibility of Automated Hallucination Detection in Large Language Models
Amin Karbasi, Omar Montasser, John Sous +1
Is automated hallucination detection possible? In this work, we introduce a theoretical framework to analyze the feasibility of automatically detecting hallucinations produced by l…
On Agnostic PAC Learning in the Small Error Regime
Julian Asilis, Mikael Møller Høgsgaard, Grigoris Velegkas
Binary classification in the classic PAC model exhibits a curious phenomenon: Empirical Risk Minimization (ERM) learners are suboptimal in the realizable case yet optimal in the ag…
On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability
Alkis Kalavasis, Anay Mehrotra, Grigoris Velegkas
We study language generation in the limit - introduced by Kleinberg and Mullainathan [KM24] - building on classical works of Gold [Gol67] and Angluin [Ang79]. [KM24]'s main result…
Procurement Auctions via Approximately Optimal Submodular Optimization
Yuan Deng, Amin Karbasi, Vahab Mirrokni +3
We study procurement auctions, where an auctioneer seeks to acquire services from strategic sellers with private costs. The quality of services is measured by a submodular function…
Randomized Truthful Auctions with Learning Agents
Gagan Aggarwal, Anupam Gupta, Andres Perlroth +1
We study a setting where agents use no-regret learning algorithms to participate in repeated auctions. \citet{kolumbus2022auctions} showed, rather surprisingly, that when bidders p…
On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode Collapse
Alkis Kalavasis, Anay Mehrotra, Grigoris Velegkas
Specifying all desirable properties of a language model is challenging, but certain requirements seem essential. Given samples from an unknown language, the trained model should pr…
Understanding Aggregations of Proper Learners in Multiclass Classification
Julian Asilis, Mikael Møller Høgsgaard, Grigoris Velegkas
Multiclass learnability is known to exhibit a properness barrier: there are learnable classes which cannot be learned by any proper learner. Binary classification faces no such bar…