Language Generation in the Limit

This seminar talk explores the fundamental aspects of language generation problems in computer science. Dive into Jon Kleinberg's research on language generation in the limit, presented at the Computer Science/Discrete Mathematics Seminar I at the Institute for Advanced Study. Examine how, despite the complexity of large language models, the basic specifications of language generation can be simply stated: given finite training samples from an unknown language, produce valid new strings not present in the training data. Learn about models where an adversary enumerates strings of an unknown target language from a list of candidate languages, and discover how certain non-trivial guarantees for language generation are possible in this setting. Compare these findings with contrasting negative results from Gold and Angluin in language learning models, suggesting that identifying a language differs fundamentally from generating from it. The talk covers joint research with Sendhil Mullainathan and Fan Wei, offering insights into theoretical computer science and discrete mathematics.