Please note: This PhD seminar will take place in DC 1304 and online.
Helia Yazdanyar, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Sepehr Assadi
Graph streaming algorithms are well understood when we allow many colors, but far less is known about how to estimate the chromatic number. In this talk, I will present recent progress on the question: how much space is required to distinguish whether an input graph is q-colorable or requires significantly more than q colors?
Our work develops upper and lower bounds across three natural streaming models: adversarial, random-order, and dynamic. In this talk, we will focus primarily on the adversarial setting, where we prove space lower bounds for distinguishing q- vs 2^{\Omega(q)}-colorable graphs. A key component of the proof is a new graph construction we introduce — cluster packing graphs — which enables us to characterize space requirements in this regime. I will also briefly discuss our results for random-order streams, where we obtain upper and lower bounds for distinguishing q- vs q^t-colorable graphs.
Download the paper on which this seminar is based.
To attend this PhD seminar in person, please go to DC 1304. You can also attend virtually on Zoom.