boyangh@ucsd.edu

Boyang Huang

Hi! I am a second-year PhD student in the Computer Science department at Yale University, where I'm very fortunate to work with Professors Daniel Spielman and Manolis Zampetakis. My research interests lie in algorithm design, optimization, and learning theory. I'm also broadly interested in theoretical computer science and mathematics.

Before coming to Yale, I was a master's student at UC San Diego where I received invaluable guidance and mentorship from Professors Russell Impagliazzo and Barna Saha.

Prior to UCSD, I received undergraduate degrees in computer science and honors mathematics from the University of Michigan Ann Arbor.

I am deeply thankful to all my research advisors, mentors, and collaborators for guiding me into theory research. I am also extremely grateful to all my previous professors and instructors for introducing me to the beautiful world of mathematics.

[CV] [Google Scholar]

Research

All co-authors are listed in alphabetical order.

Subquadratic Algorithms and Hardness for Attention with Any Temperature
with Shreya Gupta, Barna Saha, Yinzhan Xu, and Chris Ye.
The Fourteenth International Conference on Learning Representations (ICLR), 2026.
[abstract] [arXiv] [ICLR]

Despite the popularity of the Transformer architecture, the standard algorithm for computing Attention suffers from quadratic time complexity in context length \(n\). Alman and Song showed that when the head dimension \(d = \Theta(\log n)\), subquadratic Attention is possible if and only if the inputs have small entries bounded by \(B = o(\sqrt{\log n})\) in absolute values, under the Strong Exponential Time Hypothesis (\(\mathsf{SETH}\)). Equivalently, subquadratic Attention is possible if and only if the softmax is applied with high temperature for \(d=\Theta(\log n)\). Running times of these algorithms depend exponentially on \(B\) and thus they do not lead to even a polynomial-time algorithm outside the specific range of \(B\).

This naturally leads to the question: when can Attention be computed efficiently without strong assumptions on temperature? Are there fast attention algorithms that scale polylogarithmically with entry size \(B\)? In this work, we resolve this question and characterize when fast Attention for arbitrary temperatures is possible. First, for all constant \(d = O(1)\), we give the first subquadratic \(\tilde{O}(n^{2 - 1/d} \cdot \mathrm{polylog}(B))\) time algorithm for Attention with large \(B\). Our result holds even for matrices with large head dimension if they have low rank. Combined with a reduction from Gradient Computation to Attention, we obtain a subquadratic algorithm for the full LLM training process. Furthermore, we show that any substantial improvement on our algorithm is unlikely. In particular, we show that even when \(d = 2^{\Theta(\log^* n)}\), Attention requires \(n^{2 - o(1)}\) time under \(\mathsf{SETH}\).

Finally, in the regime where \(d = \mathrm{poly}(n)\), the standard algorithm requires \(O(n^{2} d)\) time while previous lower bounds only ruled out algorithms with truly subquadratic time in \(n\). We close this gap and show that the standard algorithm is optimal under popular fine-grained complexity assumptions.

The Computational Complexity of Factored Graphs
with Shreya Gupta, Russell Impagliazzo, Stanley Woo, and Chris Ye.
16th Innovations in Theoretical Computer Science (ITCS) conference, 2025.
[abstract] [arXiv] [slides] [video] [ITCS]

While graphs and abstract data structures can be large and complex, practical instances are often regular or highly structured. If the instance has sufficient structure, we might hope to compress the object into a more succinct representation. An efficient algorithm (with respect to the compressed input size) could then lead to more efficient computations than algorithms taking the explicit, uncompressed object as input. This leads to a natural question: when does knowing the input instance has a more succinct representation make computation easier?

We initiate the study of the computational complexity of problems on factored graphs: graphs that are given as a formula of products and unions on smaller graphs. For any graph problem, we define a parameterized version that takes factored graphs as input, parameterized by the number of (smaller) ordinary graphs used to construct the factored graph. In this setting, we characterize the parameterized complexity of several natural graph problems, exhibiting a variety of complexities. We show that a decision version of lexicographically first maximal independent set is XP-complete, and therefore unconditionally not fixed-parameter tractable (FPT). On the other hand, we show that clique counting is FPT. Finally, we show that reachability is XNL-complete. Moreover, XNL is contained in FPT if and only if NL is contained in some fixed polynomial time.

The Greedy Coin Change Problem
with Shreya Gupta and Russell Impagliazzo.
[abstract] [arXiv]

The Coin Change problem, also known as the Change-Making problem, is a well-studied combinatorial optimization problem, which involves minimizing the number of coins needed to make a specific change amount using a given set of coin denominations. A natural and intuitive approach to this problem is the greedy algorithm. While the greedy algorithm is not universally optimal for all sets of coin denominations, it yields optimal solutions under most real-world coin systems currently in use, making it an efficient heuristic with broad practical applicability. Researchers have been studying ways to determine whether a given coin system guarantees optimal solutions under the greedy approach, but surprisingly little attention has been given to understanding the general computational behavior of the greedy algorithm applied to the coin change problem.

To address this gap, we introduce the Greedy Coin Change problem and formalize its decision version: given a target amount \(W\) and a set of denominations \(C\), determine whether a specific coin is included in the greedy solution. We prove that this problem is P-complete under log-space reductions, which implies it is unlikely to be efficiently parallelizable or solvable in limited space.

Boyang Huang

Research

Teaching

UCSD

UM

Miscellany