{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:32:02Z","timestamp":1755999122711,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":32,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,18]],"date-time":"2023-06-18T00:00:00Z","timestamp":1687046400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Google Research Scholar Gift"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1907738, CCF-2006589, CCF-2047061"],"award-info":[{"award-number":["CCF-1907738, CCF-2006589, CCF-2047061"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,18]]},"DOI":"10.1145\/3584372.3588681","type":"proceedings-article","created":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T22:21:22Z","timestamp":1685744482000},"page":"141-153","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-8914-5995","authenticated-orcid":false,"given":"Sepehr","family":"Assadi","sequence":"first","affiliation":[{"name":"Rutgers University, Piscataway, NJ, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3633-9180","authenticated-orcid":false,"given":"Amit","family":"Chakrabarti","sequence":"additional","affiliation":[{"name":"Dartmouth College, Hanover, NH, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-9172-6553","authenticated-orcid":false,"given":"Prantar","family":"Ghosh","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, NJ, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8189-0516","authenticated-orcid":false,"given":"Manuel","family":"Stoeckl","sequence":"additional","affiliation":[{"name":"Dartmouth College, Hanover, NH, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,18]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Smaller cuts, higher lower bounds. CoRR abs\/1901.01630","author":"Abboud A.","year":"2019","unstructured":"Abboud, A., Censor-Hillel, K., Khoury, S., and Paz, A. Smaller cuts, higher lower bounds. CoRR abs\/1901.01630 (2019)."},{"key":"e_1_3_2_1_2_1","first-page":"1","volume-title":"Virtual Conference","volume":"176","author":"Alon N.","year":"2020","unstructured":"Alon, N., and Assadi, S. Palette sparsification beyond (\u0394+1) vertex coloring. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2020, August 17--19, 2020, Virtual Conference (2020), vol. 176 of LIPIcs, pp. 6:1--6:22."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520016"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.48"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520005"},{"key":"e_1_3_2_1_6_1","volume-title":"A framework for adversarial streaming via differential privacy and difference estimators. CoRR abs\/2107.14527","author":"Attias I.","year":"2021","unstructured":"Attias, I., Cohen, E., Shechner, M., and Stemmer, U. A framework for adversarial streaming via differential privacy and difference estimators. CoRR abs\/2107.14527 (2021)."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3404504"},{"key":"e_1_3_2_1_8_1","volume-title":"Adversarially robust streaming via dense--sparse trade-offs. CoRR abs\/2109.03785","author":"Ben-Eliezer O.","year":"2021","unstructured":"Ben-Eliezer, O., Eden, T., and Onak, K. Adversarially robust streaming via dense--sparse trade-offs. CoRR abs\/2109.03785 (2021)."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387658"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387643"},{"key":"e_1_3_2_1_11_1","first-page":"1","volume-title":"47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8--11, 2020, Saarbr\u00fccken, Germany (Virtual Conference)","volume":"168","author":"Bera S. K.","year":"2020","unstructured":"Bera, S. K., Chakrabarti, A., and Ghosh, P. Graph coloring via degeneracy in streaming and other space-conscious models. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8--11, 2020, Saarbr\u00fccken, Germany (Virtual Conference) (2020), vol. 168 of LIPIcs, pp. 11:1--11:21."},{"key":"e_1_3_2_1_12_1","volume-title":"Coloring in graph streams. CoRR abs\/1807.07640","author":"Bera S. K.","year":"2018","unstructured":"Bera, S. K., and Ghosh, P. Coloring in graph streams. CoRR abs\/1807.07640 (2018)."},{"key":"e_1_3_2_1_13_1","first-page":"1","volume-title":"ITCS 2021, January 6--8, 2021, Virtual Conference","volume":"185","author":"Bhattacharya A.","year":"2021","unstructured":"Bhattacharya, A., Bishnu, A., Mishra, G., and Upasana, A. Even the easiest(?) graph coloring problem is not easy in streaming! In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6--8, 2021, Virtual Conference (2021), vol. 185 of LIPIcs, pp. 15:1--15:19."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175267"},{"key":"e_1_3_2_1_15_1","volume-title":"Adversarial robustness of streaming algorithms through importance sampling. CoRR abs\/2106.14952","author":"Braverman V.","year":"2021","unstructured":"Braverman, V., Hassidim, A., Matias, Y., Schain, M., Silwal, S., and Zhou, S. Adversarial robustness of streaming algorithms through importance sampling. CoRR abs\/2106.14952 (2021)."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"e_1_3_2_1_17_1","first-page":"98","volume-title":"Proceedings of the SIGPLAN '82 Symposium on Compiler Construction","author":"Chaitin G. J.","year":"1982","unstructured":"Chaitin, G. J. Register allocation & spilling via graph coloring. In Proceedings of the SIGPLAN '82 Symposium on Compiler Construction, Boston, Massachusetts, USA, June 23--25, 1982 (1982), J. R. White and F. E. Allen, Eds., ACM, pp. 98--105."},{"key":"e_1_3_2_1_18_1","first-page":"1","volume-title":"Proc. 13th Conference on Innovations in Theoretical Computer Science","author":"Chakrabarti A.","year":"2022","unstructured":"Chakrabarti, A., Ghosh, P., and Stoeckl, M. Adversarially robust coloring for graph streams. In Proc. 13th Conference on Innovations in Theoretical Computer Science (2022), pp. 37:1--37:23."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188964"},{"key":"e_1_3_2_1_20_1","first-page":"4112","volume-title":"International Conference on Machine Learning, ICML 2022, 17--23 July 2022, Baltimore, Maryland, USA (2022), vol. 162 of Proceedings of Machine Learning Research, PMLR","author":"Cohen E.","unstructured":"Cohen, E., Lyu, X., Nelson, J., Sarl\u00f3s, T., Shechner, M., and Stemmer, U. On the robustness of countsketch to adaptive inputs. In International Conference on Machine Learning, ICML 2022, 17--23 July 2022, Baltimore, Maryland, USA (2022), vol. 162 of Proceedings of Machine Learning Research, PMLR, pp. 4112--4140."},{"key":"e_1_3_2_1_21_1","first-page":"1","volume-title":"Proc. 46th International Colloquium on Automata, Languages and Programming","author":"Cormode G.","year":"2019","unstructured":"Cormode, G., Dark, J., and Konrad, C. Independent sets in vertex-arrival streams. In Proc. 46th International Colloquium on Automata, Languages and Programming (2019), pp. 45:1--45:14."},{"key":"e_1_3_2_1_22_1","first-page":"1009","volume-title":"Proc. 62nd Annual IEEE Symposium on Foundations of Computer Science","author":"Ghaffari M.","year":"2021","unstructured":"Ghaffari, M., and Kuhn, F. Deterministic distributed vertex coloring: Simpler, faster, and without network decomposition. In Proc. 62nd Annual IEEE Symposium on Foundations of Computer Science (2021), pp. 1009--1020."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520023"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/645921.673143"},{"key":"e_1_3_2_1_25_1","volume-title":"Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Hassidim A.","year":"2020","unstructured":"Hassidim, A., Kaplan, H., Mansour, Y., Matias, Y., and Stemmer, U. Adversarially robust streaming algorithms via differential privacy. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6--12, 2020, virtual (2020)."},{"key":"e_1_3_2_1_26_1","first-page":"94","volume-title":"CRYPTO 2021, Virtual Event, August 16--20, 2021, Proceedings, Part III","volume":"12827","author":"Kaplan H.","year":"2021","unstructured":"Kaplan, H., Mansour, Y., Nissim, K., and Stemmer, U. Separating adaptive streaming from oblivious streaming using the bounded storage model. In Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16--20, 2021, Proceedings, Part III (2021), vol. 12827 of Lecture Notes in Computer Science, Springer, pp. 94--121."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.76"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0548(86)90061-4"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498232"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835760"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch32"},{"key":"e_1_3_2_1_32_1","volume-title":"Proc. 62nd Annual IEEE Symposium on Foundations of Computer Science","author":"Woodruff D. P.","year":"2021","unstructured":"Woodruff, D. P., and Zhou, S. Tight bounds for adversarially robust streams and sliding windows via difference estimators. In Proc. 62nd Annual IEEE Symposium on Foundations of Computer Science (2021), p. to appear."}],"event":{"name":"SIGMOD\/PODS '23: International Conference on Management of Data","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"],"location":"Seattle WA USA","acronym":"SIGMOD\/PODS '23"},"container-title":["Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584372.3588681","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/abs\/10.1145\/3584372.3588681","content-type":"text\/html","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3584372.3588681","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3584372.3588681","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:29Z","timestamp":1750178789000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3584372.3588681"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,18]]},"references-count":32,"alternative-id":["10.1145\/3584372.3588681","10.1145\/3584372"],"URL":"https:\/\/doi.org\/10.1145\/3584372.3588681","relation":{},"subject":[],"published":{"date-parts":[[2023,6,18]]},"assertion":[{"value":"2023-06-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}