8 citations · 9 across the 4 of their papers we have counts for
5 papers
On Limitations of the Transformer Architecture
Binghui Peng, Srini Narayanan, Christos Papadimitriou
What are the root causes of hallucinations in large language models (LLMs)? We use Communication Complexity to prove that the Transformer layer is incapable of composing functions…
The complexity of non-stationary reinforcement learning
Christos Papadimitriou, Binghui Peng
The problem of continual learning in the domain of reinforcement learning, often called non-stationary reinforcement learning, has been identified as an important challenge to the…
Extremal combinatorics, iterated pigeonhole arguments, and generalizations of PPP
Amol Pasarkar, Mihalis Yannakakis, Christos Papadimitriou
We study the complexity of computational problems arising from existence theorems in extremal combinatorics. For some of these problems, a solution is guaranteed to exist based on…
Memory Bounds for Continual Learning
Xi Chen, Christos Papadimitriou, Binghui Peng
Continual learning, or lifelong learning, is a formidable current challenge to machine learning. It requires the learner to solve a sequence of different learning tasks, one af…
Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics
Jason Milionis, Christos Papadimitriou, Georgios Piliouras +1
Under what conditions do the behaviors of players, who play a game repeatedly, converge to a Nash equilibrium? If one assumes that the players' behavior is a discrete-time or conti…