Ashish Sabharwal

We show that slightly increasing transformers' depth with the input length increases their expressive power under standard complexity conjectures.

We exactly characterize the expressive power of transformers with padding tokens as $\mathsf{TC}^0$, and we also characterize transformers with looping and padding.

We present AutoDiscovery, a method for open-ended scientific discovery that uses Bayesian surprise and Monte Carlo tree search to sample diverse hypotheses at scale that are likely to lead to discoveries that are suprising both to LLMs and humans.