Prantar Ghosh, DIMACS

Abstract

A streaming algorithm is called adversarially robust if it provides correct outputs even when the stream updates are chosen by an adaptive adversary based on past outputs given by the algorithm. There has been a surge in interest for such algorithms over the last couple of years. I shall begin this talk by describing this model and then address the natural question of exhibiting a separation between classical and robust streaming. We shall see how this question leads to the problem of streaming graph coloring, where we need to maintain a proper vertex-coloring of a streaming graph using as few colors as possible. In the classical streaming model, Assadi, Chen, and Khanna showed that an n-vertex graph with maximum degree Δ can be colored with Δ+1 colors in O(n polylog(n)) space, i.e., semi-streaming space. We shall show that an adversarially robust algorithm running under a similar space bound must spend almost Ω(Δ^2) colors, and that robust O(Δ)-coloring requires a linear amount of space, namely Ω(nΔ). These lower bounds not only establish the first separation between adversarially robust algorithms and ordinary randomized algorithms for a natural problem on insertion-only streams, but also the first separation between randomized and deterministic coloring algorithms for graph streams, since deterministic algorithms are automatically robust. I shall also go over some complementary upper bounds: in particular, there are robust coloring algorithms using O(Δ^2.5) colors in semi-streaming space and O(Δ^2) colors in O(n√Δ) space.
This is based on a couple of joint works: one with Amit Chakrabarti and Manuel Stoeckl, and another with Sepehr Assadi, Amit, and Manuel. 

Please note this talk will be over Zoom:
https://rutgers.zoom.us/j/94994409309?pwd=S0FvMFMrbW5RTlhyRTBWRGV2MGtOUT09
Meeting ID: 949 9440 9309

Password: 725976

See: https://theory.cs.rutgers.edu/theory_seminar