4 papers · 1 filter
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…
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…
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…
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…