2 papers
cs.LG2024
Lower bounds on transformers with infinite precision
Alexander Kozachinskiy
In this note, we use the VC dimension technique to prove the first lower bound against one-layer softmax transformers with infinite precision. We do so for two tasks: function comp…
cs.GT2022
Infinite Separation between General and Chromatic Memory
Alexander Kozachinskiy
In this paper, we construct a winning condition over a finite set of colors such that, first, every finite arena has a strategy with 2 states of general memory which is optimal…