@inproceedings{469bd7b09201498f9c0d6c15e648eeaf,

title = "Deterministic graph coloring in the streaming model",

abstract = "Recent breakthroughs in graph streaming have led to design of semi-streaming algorithms for various graph coloring problems such as ({"}+1)-coloring, degeneracy-coloring, coloring triangle-free graphs, and others. These algorithms are all randomized in crucial ways and whether or not there is any deterministic analogue of them has remained an important open question in this line of work. We settle this fundamental question by proving that there is no deterministic single-pass semi-streaming algorithm that given a graph G with maximum degree {"}, can output a proper coloring of G using any number of colors which is sub-exponential in {"}. Our proof is based on analyzing the multi-party communication complexity of a related communication game, using random graph theory type arguments that may be of independent interest. We complement our lower bound by showing that one extra pass over the input allows one to recover an O({"}2) coloring via a deterministic semi-streaming algorithm. This result is extended to an O({"}) coloring in O(log{"}) passes even in dynamic streams.",

keywords = "Graph coloring, deterministic algorithms, lower bounds, streaming",

author = "Sepehr Assadi and Andrew Chen and Glenn Sun",

note = "Publisher Copyright: {\textcopyright} 2022 ACM.; 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022 ; Conference date: 20-06-2022 Through 24-06-2022",

year = "2022",

month = sep,

day = "6",

doi = "10.1145/3519935.3520016",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "261--274",

editor = "Stefano Leonardi and Anupam Gupta",

booktitle = "STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing",

}