From the 2 of 14 linked papers with an AI index.
14 papers
Optimal Unambiguous DNFs and Alon-Saks-Seymour
Chirag Pabbaraju
We construct unambiguous DNFs having width but -certificate complexity . By utilizing the special structure of these DNFs, we prove a lifting theorem with a cons…
Language Identification with Succinct Machine-Independent Traces
Moses Charikar, Jon Kleinberg, Chirag Pabbaraju
The paper shows that language identification in the limit can be achieved using compact, machine‑independent computational traces that use only a small alphabet derived directly fr…
Globally Consistent Coloring Schemes for Language Identification
Moses Charikar, Jon Kleinberg, Chirag Pabbaraju
The paper shows that a single terminal bit attached to each example string is sufficient to identify any countable collection of infinite languages in Gold's language identificatio…
Space-Efficient Language Generation in the Limit
Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov +2
We initiate a resource-aware theory of \textit{language generation in the limit} under the minimal constraint of space efficiency. In our framework, a learner observes an adversari…
Learning with Monotone Adversarial Corruptions
Kasper Green Larsen, Chirag Pabbaraju, Abhishek Shetty
We study the extent to which standard machine learning algorithms rely on exchangeability and independence of data by introducing a monotone adversarial corruption model. In this m…
From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization
Moses Charikar, Chirag Pabbaraju, Ambuj Tewari
Curvature adaptivity is a classical theme in online optimization: for convex Lipschitz losses, adaptive methods interpolate between the optimal regret for general con…