Michael Chen, Atieh Bastan, A. Pavan, N. V. Vinodchandran
We study the sample complexity of list replicable algorithms for estimating the biases of $d$ coins. An algorithm is $(k,\varepsilon,δ)$-list replicable if for every bias vector $\mathbf{p}\in[0,1]^d$, there is a set of outputs $L_{\mathbf{p}}\subseteq \mathbb{R}^d$ of at most $k$ elements such that every $\mathbf{y}\in L_{\mathbf{p}}$ satisfies $\lVert\mathbf{y}-\mathbf{p}\rVert_\infty\leq\varepsilon$, and the algorithm output is in $L_{\mathbf{p}}$ with probability at least $1-δ$. Prior work gave a $(d+1,\varepsilon,δ)$-list replicable algorithm with sample complexity $\widetilde{O}\left(\frac{d^3}{\varepsilon^2}\right)$, but no nontrivial sample complexity lower bound was known. We establish the first non-trivial sample complexity lower bound for this problem and give an improved algorithm that matches it up to polylogarithmic factors. Together, these results determine the optimal sample complexity for list size $d+1$ to be $\widetildeΘ\left(\frac{d^2}{\varepsilon^2}\right)$, showing that the quadratic dependence on dimension is inherent up to polylogarithmic factors. More generally, for every $k\in[d+1,2^d]$, we establish matching upper and lower bounds of $\widetildeΘ\left(\frac{d^2}{\varepsilon^2\log k}\right)$ on the total sample complexity.
Siqiao Huang, Partha Kaushik, Michael Chen, Hengkai Pan, Kaiwen Geng, Omar Chehab, Fernando Moreno-Pino, Max Simchowitz
Effective world modeling requires compressing salient history information that facilitates future prediction. However, most existing approaches inherit tokenization and conditioning mechanisms from video generation, where objectives are centered around perceptual realism rather than predictive utility. This discrepancy limits the world model's effectiveness, especially in environments dominated by visual nuisances or task-irrelevant background details. To this end, we introduce Compression Forcing (CF), a general framework that aligns history compression with the predictive objective of world modeling. Compression Forcing features Dynamics-Aware Tokenization (DAT), a novel tokenization method that compresses history observations into a sequence ordered by decreasing dynamics saliency. Built on a diffusion backbone, this structure enables Hierarchical History Guidance (HG-H), allowing selective amplification of dynamics-salient information during inference. Extensive experiments across various environments demonstrate improved prediction fidelity, physical realism, and downstream decision-making performance, establishing Compression Forcing as a highly flexible and effective approach for world modeling.
David Jurgens University of Michigan - Ann Arbor, Michael Chen, Lina Iyer
Annotated data remains essential for training and evaluating NLP systems. Large language models have broadened the kinds of data researchers need, including multimodal and agentic system data. Here, we introduce Potato 2.0, a major update to our open source annotation platform designed for easy deployment, customization, and fully reproducible and shareable annotation designs. Potato offers broad support for many types of annotations in NLP, including 39 different types of annotation tasks, support for text, audio, image, and video modalities, or mixtures thereof. Potato 2.0 includes robust support for labeling agentic system outputs through reading common trace formats, or live interaction and annotation with agents in multiple settings, such as chatting, web-browsing, and coding. Potato also includes multiple AI-assistance features to help annotators more easily label data. Finally, Potato introduces a new agentic AI-in-the-loop workflow where a single human annotator collaborates with an LLM through iterative prompt refinement, uncertainty-driven instance selection, and progressive autonomy—enabling efficient dataset creation without a large annotation team.
尚无 AI 解读，展示原文摘要
cs.CL · cs.AI · cs.CV
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 3: System Demonstrations) · 2026 · 正式发表