6 papers
In Search of Melchior's Ordinary Points
Jonathan Lenchner, Rik Sengupta
In 1893, James Joseph Sylvester posed the following problem: given n points in the plane, not all collinear, must there be a line determined by two of the points that does not pass…
On the Expressive Power of Transformers
Phokion Kolaitis, Rik Sengupta
Multi-layer transformers form the critical component of essentially all large language models (LLMs) in use today. Because of their ubiquity and computational capability, there is…
Separating quantum circuits from classical LLMs
Srinivasan Arunachalam, Arkopal Dutt, Hari Krovi +1
Modern large language models - transformers and diffusion language models - are built around two canonical algorithmic tasks: prediction and generation. We prove unconditional sepa…
Who Wins the Multi-Structural Game?
Ronald Fagin, Neil Immerman, Phokion Kolaitis +2
Combinatorial games played between two players, called Spoiler and Duplicator, have often been used to capture syntactic properties of formal logical languages. For instance, the w…
On the Number of Quantifiers Needed to Define Boolean Functions
Marco Carmosino, Ronald Fagin, Neil Immerman +3
The number of quantifiers needed to express first-order (FO) properties is captured by two-player combinatorial games called multi-structural games. We analyze these games on binar…
Parallel Play Saves Quantifiers
Marco Carmosino, Ronald Fagin, Neil Immerman +4
The number of quantifiers needed to express first-order properties is captured by two-player combinatorial games called multi-structural (MS) games. We play these games on linear o…