Publications (10)
Active Learning Polynomial Threshold Functions
Omri Ben-Eliezer, Max Hopkins, Chutong Yang +1
We initiate the study of active learning polynomial threshold functions (PTFs). While traditional lower bounds imply that even univariate quadratics cannot be non-trivially activel…
Fast attention mechanisms: a tale of parallelism
Jingwen Liu, Hantao Yu, Clayton Sanford +2
Transformers have the representational capacity to simulate Massively Parallel Computation (MPC) algorithms, but they suffer from quadratic time complexity, which severely limits t…
Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming
Josh Alman, Ethan Turok, Hantao Yu +1
Generalizing work of Künnemann, Paturi, and Schneider [ICALP 2017], we study a wide class of high-dimensional dynamic programming (DP) problems in which one must find the shortest…
On the Computational Hardness of Transformers
Barna Saha, Yinzhan Xu, Christopher Ye +1
The transformer has revolutionized modern AI across language, vision, and beyond. It consists of layers, each running attention heads in parallel and feeding the combined o…
Two Heads Are Better than One: Simulating Large Transformers with Small Ones
Hantao Yu, Josh Alman
The quadratic complexity of self-attention prevents transformers from scaling effectively to long input sequences. On the other hand, modern GPUs and other specialized hardware acc…
Minimum Edge-Outerplanar Embeddings are Polynomial-Time Computable
Hantao Yu
We prove that the minimum edge-outerplanarity of a planar graph can be computed in polynomial time, resolving an open problem of Bentz (2009). The proof was initially produced by G…
Improving the Leading Constant of Matrix Multiplication
Josh Alman, Hantao Yu
Algebraic matrix multiplication algorithms are designed by bounding the rank of matrix multiplication tensors, and then using a recursive method. However, designing algorithms in t…
Fundamental Limitations on Subquadratic Alternatives to Transformers
Josh Alman, Hantao Yu
The Transformer architecture is widely deployed in many popular and impactful Large Language Models. At its core is the attention mechanism for calculating correlations between pai…
Optimal chain density, entropy, and space-time tradeoffs for the TSP
Alexandr Andoni, Justin Dallant, László Kozma +1
The paper determines the optimal trade‑off between the size of a set system and its full‑chain density, yielding a near‑optimal constant γ≈3.1819 that governs the space‑time produc…
Robust Empirical Risk Minimization with Tolerance
Robi Bhattacharjee, Max Hopkins, Akash Kumar +2
Developing simple, sample-efficient learning algorithms for robust classification is a pressing issue in today's tech-dominated world, and current theoretical techniques requiring…