Maya Bechler-Speicher

We show that transformers with linear width can solve many graph problems using constant depth, revealing a trade-off where increasing width enables shallower, faster models—though some tasks still demand quadratic width.

We prove the incompleteness of Spectrally-enhanced GNNs on graphs with a simple spectrum.