12 papers
Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarchy
Xiaoyu Li, Andi Han, Jiaojiao Jiang +1
Language generation in the limit asks for valid unseen elements from every exhaustive positive presentation of an unknown infinite language. We characterize this task for arbitrary…
Optimistic Rates for Multiclass PAC Learning
Xiaoyu Li, Andi Han, Jiaojiao Jiang +1
Worst-case multiclass bounds do not become smaller when the best classifier is already nearly correct: what is missing is an optimistic rate, a guarantee whose fluctuation scales w…
On Computational Hardness of Mistake-Bounded Language Generation: A Random-Oracle Query Separation
Xiaoyu Li, Andi Han, Dai Shi +2
Generation in the limit guarantees eventual generation for every countable collection of infinite languages in the model of Kleinberg and Mullainathan [KM24], while closure dimensi…
The Exact Worst-Case Tail Probability under Bounded Kurtosis
Xiaoyu Li, Andi Han, Jiaojiao Jiang +1
We determine exactly what a kurtosis bound buys for one-sided tail control. For the class of real random variables with mean , variance , and fourth moment a…
Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model
Xiaoyu Li, Junwei Yu, Jiaojiao Jiang +2
The John ellipsoid of a symmetric polytope , , is computed by a long line…
Flood and Harvest: The Provable Necessity of Trivia for Generating Valuable Mathematics via the Lens of Language Generation in the Limit
Xiaoyu Li, Andi Han, Dai Shi +3
AI systems coupled to proof assistants now generate formal mathematics at scale, and the gap between what a checker can verify and what a mathematician would value has become the b…