Graph coloring has long stood as an important computer science problem. The different approximation techniques for the NP-complete problem represent a trade-off between approximation accuracy and efficiency. Previous work had parallelized many of these methods, however the Saturation Degree heuristic algorithm, one of the most accurate but of the slowest as well, remains hard to parallelize. This is because, the order of the program execution is assigned dynamically. In this SuperUROP project, I will use Swarm, an architecture designed in MIT for ordered parallelism, to parallelize this algorithm. Swarm is capable of speculating different graph coloring orders in parallel, and later disregard the invalid orderings, effectively parallelizing the algorithm while behaving as the serial algorithm would. This project aims to speed up the approximation of an important problem in computer science, in addition to contributing to the novel Swarm architecture.

From my point of view, research is an essential complement to classes. This research project provides me with an opportunity to work closely with two different fields I am passionate about: performance engineering and computer systems design. I am looking forward to learning more about the workflow of research, from the brainstorming stage through implementation, ending with production.