Rui Shi

Streaming Hypergraph Coloring via Palette Sparsification

For every fixed $k\ge2$, we give a randomized one-pass insertion-only algorithm that colors an $n$-vertex $k$-uniform hypergraph of maximum degree $\Delta$ with $O(\Delta^{1/(k-1)})$ colors using $\widetilde O_k(n)$ bits of working memory. As a graph-theoretic result of independent interest, we also prove a tight palet...