Computer Sciences PhD student Ben Young has been awarded the 2025 Best Student ICALP Paper at the 52nd EATCS International Colloquium on Automata, Languages, and Programming (ICALP) in Aarhus, Denmark. Young is advised by Professor Jin-Yi Cai and is part of the Theory of Computing Group. Cai says of Young, “Ben is brilliant! Working with him is a lot of fun. I enjoyed working with all my students and we often write joint papers.” Cai continued, saying that for this paper, “Ben had the key idea, and therefore he is the sole author. (I had to write a justification to the university to justify why I can pay for his trip to present the work while not a coauthor.)”
In Young’s words:
This paper builds upon earlier work with my advisor, Professor Jin-Yi Cai. I had the idea when I came across a theorem in a 2012 paper by the Dutch mathematician Guus Regts. I realized that this theorem said something very similar to a theorem we used in our earlier work, but in a different context. This context turned out to be relevant to an open conjecture made by Professor Cai’s collaborator Mingji Xia, which my paper resolves. As I am the only author of the paper, this makes the paper eligible for ICALP’s best student paper award.
A graph, in the context of the paper, is a collection of vertices (nodes), some of which are connected by edges. To visualize a graph, consider a flight map, where the vertices are cities and edges (drawn as lines on the map) indicate direct flights between cities. In general, graphs are useful for modeling two-way relationships between objects. For example, consider the problem of matching n job applicants to n jobs, where each applicant is only qualified for a subset of jobs. To model this scenario, create a graph with one vertex for each applicant and one vertex for each job, with an edge between an applicant and a job if the applicant is qualified for the job. An assignment of every job to a qualified applicant is a perfect matching: a choice of n edges connecting each job to an applicant such that every vertex – both applicant and job – touches exactly one chosen edge. For another example, consider a tournament with n players, each of whom must play a game against some subset of other players. Model each player as a vertex, with an edge between players who must play each other. We would like to determine whether all games can be completed within r rounds, where each player plays at most one game per round. Equivalently, can the edges of the graph be colored with r different colors (with an edge’s color representing the round in which the corresponding game is played) such that no vertex touches two edges of the same color?
Holant problems capture the counting versions of these problems: Instead of “does there exist a perfect matching or edge coloring in the graph?”, we ask “how many different perfect matchings or edge colorings does the graph contain?” In both examples above, every vertex must satisfy a certain condition based on the edges it touches. In this way, each vertex defines a function whose input is these edges and whose output is True or False, and if every function outputs True, we have found a perfect matching or edge coloring. In the Holant (counting) version of these problems, each function returns a number instead of True or False. There has been extensive research devoted to determining for which functions the corresponding Holant problem can be solved efficiently, and for which functions it cannot. This research has close ties to classical simulation of quantum computers and to statistical physics models of interacting particles.
The paper studies a related phenomenon called Holant-indistinguishability. For example, let F be the function that counts perfect matchings. By a technique called holographic transformation, we can turn F into another function G that returns numbers that apparently refer to a totally different problem – they can even be negative or irrational – but such that, when each vertex of a graph is assigned G, we still obtain the same number. That is, F and G are indistinguishable. Now we can use any algorithm solving the Holant problem for G to count perfect matchings, and vice-versa. In 2010, Mingji Xia asked the opposite question: If G is any function indistinguishable from F, is there a holographic transformation between F and G? While in general the answer is no, the paper shows that, in one important case, the answer is yes. It achieves this via a totally new proof technique: it first breaks F and G into smaller parts, then finds holographic transformations between each part and stitches these together into a transformation between the whole F and G.
Congratulations, Ben!