Streaming algorithms for triangle counting: adversarial robustness and the weighted case

References

[1] Bar-Yossef Z, Kumar R, Sivakumar D. Reductions in streaming algorithms, with an application to counting triangles in graphs. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. 2002, 623−632

[2] Buriol L S, Frahling G, Leonardi S, Marchetti-Spaccamela A, Sohler C. Counting triangles in data streams. In: Proceedings of the 25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. 2006, 253−262

[3] Jayaram R, Kallaugher J. An optimal algorithm for triangle counting in the stream. In: Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). 2021, 11

[4] Ben-Eliezer O, Jayaram R, Woodruff D P, Yogev E . A framework for adversarially robust streaming algorithms. Journal of the ACM, 2022, 69( 2): 17

[5] Cohen E, Lyu X, Nelson J, Sarlos T, Shechner M, Stemmer U. On the robustness of countsketch to adaptive inputs. In: Proceedings of the 39th International Conference on Machine Learning. 2022, 4112−4140

[6] Cox L A Jr. Risk Analysis of Complex and Uncertain Systems. New York: Springer, 2009

[7] Hassidim A, Kaplan H, Mansour Y, Matias Y, Stemmer U . Adversarially robust streaming algorithms via differential privacy. Journal of the ACM, 2022, 69( 6): 42

[8] Kumar R, Liu P, Charikar M, Benson A R. Retrieving top weighted triangles in graphs. In: Proceedings of the 13th International Conference on Web Search and Data Mining. 2020, 295−303

RIGHTS & PERMISSIONS

Higher Education Press