15 papers
Improved Pseudorandom Codes from Permuted Puzzles
Miranda Christ, Noah Golowich, Sam Gunn +2
Watermarks are an essential tool for identifying AI-generated content. Recently, Christ and Gunn (CRYPTO '24) introduced pseudorandom error-correcting codes (PRCs), which are equiv…
Learning with Simulators: No Regret in a Computationally Bounded World
Sasha Voitovych, Abhishek Shetty, Noah Golowich +1
Understanding the minimal assumptions necessary for generalization is the fundamental question in learning theory. Unfortunately, most results rely heavily on independence (or some…
The Power of Test-Time Training for Approximate Sampling
Noah Golowich, Ankur Moitra, Dhruv Rohatgi
Efficiently sampling from a complex probability distribution is a fundamental problem which has become increasingly pertinent in recent years with the rise of generative AI, as sop…
On the Complexity of Correlated Equilibria Beyond Normal-Form Games
Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina +3
Correlated equilibria are a fundamental solution concept in game theory. However, despite decades of research, the complexity beyond games of polynomial type -- such as extensive-f…
Reject, Resample, Repeat: Understanding Parallel Reasoning in Language Model Inference
Noah Golowich, Fan Chen, Dhruv Rohatgi +4
Inference-time methods that aggregate and prune multiple samples have emerged as a powerful paradigm for steering large language models, yet we lack any principled understanding of…
Subliminal Effects in Your Data: A General Mechanism via Log-Linearity
Ishaq Aden-Ali, Noah Golowich, Allen Liu +3
Training modern large language models (LLMs) has become a veritable smorgasbord of algorithms and datasets designed to elicit particular behaviors, making it critical to develop te…