Theory Talk - Chase Hutton
November 17, 2026 2:30PM—3:30PM
Location:
In Person
-
Luis Von Ahn Awesome Classroom, Gates Hillman 4101
Speaker:
CHASE HUTTON,
Master's Student, Department of Computer Science, University of Maryland
https://terpconnect.umd.edu/~chutton6/
Deterministic parallel algorithms often perform more total operations (work) than their randomized counterparts. Luby's classical randomized algorithms for maximal independent set (MIS) and (Δ+1)-coloring, for example, run in O(n + m) expected work. In contrast, deterministic algorithms have long incurred an extra polylogarithmic factor, and even the most recent state of the art still loses a poly(log log n) factor in work. Whether deterministic algorithms for MIS and (Δ+1)-coloring can match the linear work bounds of the sequential greedy algorithms has remained open.
In this talk, I'll present simple deterministic parallel algorithms for both problems that run in O(n + m) work and polylogarithmic depth. These are the first work-efficient deterministic algorithms for either problem.
—
Chase Hutton is a Computer Science Masters student at the University of Maryland interested in theoretical computer science.
For More Information:
korinna@cmu.edu