Mars Xiang and Max Jiang are joint recipients of the 2026 Germain-Erdős Undergraduate Award in Mathematical Research. Now in its third year, the award recognizes undergraduate students who have made outstanding contributions to fundamental mathematical research. Established through a donation from David Ash (BMath ’87), the award is named in honour of two pioneering mathematicians, Sophie Germain and Paul Erdős.

As joint recipients, Mars and Max share the $2,500 prize.

They received the honour for their work on a longstanding open problem in graph streaming algorithms: determining the best possible approximation ratio for the maximum matching problem using single-pass semi-streaming algorithms. Conducted with Professor Sepehr Assadi, their research resulted in a paper accepted for presentation at STOC 2026, the 58^th ACM Symposium on Theory of Computing, widely regarded as one of the two premier conferences in theoretical computer science.

“This project addresses a question I consider significantly challenging even for PhD-level research, yet Mars and Max handled it with exceptional success,” said Professor Assadi. “Had it not been for their brilliance, dedication, perseverance and creative thinking, we would not have been able to move past several hurdles that stopped us — as well as other researchers — from making progress on this fundamental question.”

About this award-winning research

Graph streaming algorithms are designed to process massive graphs whose edges arrive sequentially as a stream of data. Because these algorithms are restricted to using limited memory, they cannot store the entire graph. First introduced in 2004, the model has become increasingly important for processing enormous datasets in areas such as networks, communications and large-scale computing systems.

Under Professor Assadi’s supervision, Mars and Max focused on one of the field’s most important unresolved questions: how well can we approximate the maximum matching problem in graph streams? A simple algorithm for this problem achieves a 0.5-approximation by maintaining a maximal matching greedily. Despite more than two decades of study, this has remained the best-known algorithm for this problem. At this point, determining the best approximation ratio possible for maximum matching in graph streams is widely considered one of the most tantalizing open questions in this area of research.

In their work with Professor Assadi, Mars and Max made a significant improvement on understanding this problem from the lower bound side also known as impossibility results: proving that achieving a certain approximation ratio is not possible for semi-streaming algorithms. The state-of-the-art result here, due to Kapralov at SODA 2021, proved that no semi-streaming algorithm can achieve an approximation ratio better than 0.59 using a highly complicated argument spanning nearly 150 pages.

The main result of the team now improves this impossibility result to rule out even a 0.55-approximation with the additional benefit of using a considerably simpler and shorter proof. The main new approach in this work is reducing the problem to a constant-size optimization problem they termed “blueprint construction,” which involves creating certain constant-size graphs with non-standard restrictions on which combinations of edges can be present, while maximizing the number of edges.

In the first part of their work, they devised a framework that can turn any given blueprint into a hard family of graphs for semi-streaming algorithms and rule out approximation ratios for the original problem depending on the “quality” of the blueprints. The second part of their work then involves construction of several new blueprints that eventually allowed them to establish their main impossibility result of 0.55-approximation for the semi-streaming matching problem.

“The real strength of this new framework is that one can now bypass all complications of prior approaches in using extremal graph theory and information theory arguments, and focus solely on constructing blueprints that are simply constant-size graphs,” said Professor Assadi. He is hopeful that this new approach can eventually lead to fully settling the original open question.

After more than a year of working closely and intensely on the problem, the team prepared a paper titled Semi-Streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints, which was accepted for presentation at STOC 2026, where it will be presented by Mars and Max in June 2026.