Graduate student Helia Yazdanyar and her advisor, Professor Sepehr Assadi, have received the Best Paper Award at SOSA25, the eighth SIAM Symposium on Simplicity in Algorithms. Their paper, Simple Sublinear Algorithms for (Δ + 1) Vertex Coloring via Asymmetric Palette Sparsification, was recognized for its approach to simplifying sublinear algorithms for graph colouring.
SOSA is a theoretical computer science conference focused on advancing algorithm research through simplicity and elegance in design and analysis. Simpler algorithms enhance problem understanding, ease implementation, improve trust, facilitate teaching, and attract broader research engagement.
“This paper has a special place for me because it simplifies one of my main results from my graduate studies,” recalls Professor Assadi. “In 2019, with Yu Chen and my advisor, Sanjeev Khanna, we showed at a high-level that you can colour a graph, with not too many colours, without even entirely reading it or storing it, and yet be correct everywhere, even in unseen parts of the graph. This was a surprising result and led to much follow-up work. Unfortunately, the algorithms that achieved this as well as subsequent work were equally complex and hard to reason about or implement. In this new paper, Helia and I show that by looking at the problem from a different angle we can achieve the same colourability guarantee with a much simpler proof and algorithm.”
L to R: Helia Yazdanyar and Professor Sepehr Assadi
Helia Yazdanyar is a first-year graduate student in the Algorithms and Complexity group at the Cheriton School of Computer Science. Her research interests are in theoretical computer science, mainly algorithms and complexity.
Sepehr Assadi is an Associate Professor and a Faculty of Mathematics Research Chair at the Cheriton School of Computer Science. His research interest is in theoretical computer science and primarily algorithm design and complexity theory for modern models of computation. This includes sublinear algorithms and lower bounds in various models for processing massive datasets such as streaming, distributed, massively parallel, and sublinear time algorithms. He is also interested in graph theory, communication complexity, online algorithms, and algorithmic game theory.
About this award-winning research
A well-known result in graph theory states that vertices of any graph with maximum degree ∆ can be coloured with ∆ + 1 colours, where no two adjacent vertices share the same colour. Moreover, a simple algorithm can find such a colouring by reading the input once. Both this result and the algorithm behind it are often taught in undergraduate courses on these topics. The prevailing wisdom, however, suggests that this problem cannot be solved much more efficiently because, at a minimum, the algorithm must read the entire graph.
In 2019, Sepehr Assadi, Yu Chen and Sanjeev Khanna challenged this intuition and showed that, surprisingly, one can indeed do better. They developed an efficient algorithm for ∆ + 1 vertex colouring that, with the help of randomization, does not need to even read a fraction of the inputs, and yet can output a colouring that with a high probability is correct for the entirety of the graph, even the parts never seen by the algorithm. In more technical terms, they designed an algorithm that, on n-vertex graphs, finds a ∆ + 1 colouring with high probability in O(n^1.5) time, regardless of the number of edges. Such an algorithm is often called a sublinear algorithm, as the resources it uses can even be sublinear in the size of the input it operates on.
The key to this result was the palette sparsification theorem, introduced by the authors. It states that in every graph G with maximum degree ∆, sampling a list of O(log n) colours from {1,...,∆ + 1} for every vertex independently and uniformly, with high probability, allows for finding a (∆ + 1) vertex colouring of G by colouring each vertex only from its sampled list.
The palette sparsification theorem naturally leads to sublinear algorithms for ∆ + 1 colouring in various areas but with an important caveat: all its known proofs require complex arguments and, more importantly, finding the colouring of the graph from the sampled lists efficiently requires a considerably complicated algorithm.
In their new work, Helia and Professor Assadi show that a natural weakening of the palette sparsification theorem addresses this drawback while still leading to sublinear algorithms of similar quality. In particular, they prove an asymmetric palette sparsification theorem that allows for list sizes of the vertices to have different sizes and only bounds the average size of these lists.
The benefit of this weaker requirement is that we can now easily show the graph can be (∆ + 1) coloured from the sampled lists even using standard textbook algorithms. This also means that this new algorithm can be incorporated into undergraduate coursework.
To learn more about the research on which this article is based, please see Sepehr Assadi and Helia Yazdanyar. Simple Sublinear Algorithms for (Δ + 1) Vertex Coloring via Asymmetric Palette Sparsification. 2025 Symposium on Simplicity in Algorithms (SOSA 2025). Society for Industrial and Applied Mathematics.