boyangh@ucsd.edu

Boyang Huang

Hi! I am a second-year master's student in the Computer Science & Engineering department at the University of California San Diego, where I'm very fortunate to work with Professor Russell Impagliazzo and Barna Saha. My research interest is in computational complexity theory and algorithm design. I'm also broadly interested in theoretical computer science and mathematics.

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.

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]

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.

[slides] [video] [ITCS]

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