• Parter M and Petruschka A. (2023). Near-optimal distributed computation of small vertex cuts. Distributed Computing. 10.1007/s00446-023-00455-z. 37:2. (67-88). Online publication date: 1-Jun-2024.

    https://link.springer.com/10.1007/s00446-023-00455-z

  • Izumi T, Emek Y, Wadayama T and Masuzawa T. Deterministic Fault-Tolerant Connectivity Labeling Scheme. Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing. (190-199).

    https://doi.org/10.1145/3583668.3594584

  • Besta M, Fischer M, Kalavri V, Kapralov M and Hoefler T. (2023). Practice of Streaming Processing of Dynamic Graphs: Concepts, Models, and Systems. IEEE Transactions on Parallel and Distributed Systems. 34:6. (1860-1876). Online publication date: 1-Jun-2023.

    https://doi.org/10.1109/TPDS.2021.3131677

  • Assadi S, Kol G and Zhang Z. (2022). Rounds vs Communication Tradeoffs for Maximal Independent Sets 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). 10.1109/FOCS54457.2022.00115. 978-1-6654-5519-0. (1193-1204).

    https://ieeexplore.ieee.org/document/9996898/

  • Czumaj A, Jiang S, Krauthgamer R, Vesely P and Yang M. (2022). Streaming Facility Location in High Dimension via Geometric Hashing 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). 10.1109/FOCS54457.2022.00050. 978-1-6654-5519-0. (450-461).

    https://ieeexplore.ieee.org/document/9996956/

  • Elkin M and Trehan C. Brief Announcement: (1+ε)-Approximate Shortest Paths in Dynamic Streams.. Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing. (57-59).

    https://doi.org/10.1145/3519270.3538469

  • Filtser A and Le H. Locality-sensitive orderings and applications to reliable spanners. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. (1066-1079).

    https://doi.org/10.1145/3519935.3520042

  • Sarkar B and Bhattacharyya M. (2020). Spectral Algorithms for Streaming Graph Analysis: A Survey. Annals of Data Science. 10.1007/s40745-020-00301-0. 8:4. (667-681). Online publication date: 1-Dec-2021.

    https://link.springer.com/10.1007/s40745-020-00301-0

  • Dory M and Parter M. Fault-Tolerant Labeling and Compact Routing Schemes. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. (445-455).

    https://doi.org/10.1145/3465084.3467929

  • Dory M, Fischer O, Khoury S and Leitersdorf D. Constant-Round Spanners and Shortest Paths in Congested Clique and MPC. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. (223-233).

    https://doi.org/10.1145/3465084.3467928

  • Biswas A, Dory M, Ghaffari M, Mitrović S and Nazari Y. Massively Parallel Algorithms for Distance Approximation and Spanners. Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures. (118-128).

    https://doi.org/10.1145/3409964.3461784

  • Assadi S and Raz R. (2020). Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). 10.1109/FOCS46700.2020.00040. 978-1-7281-9621-3. (342-353).

    https://ieeexplore.ieee.org/document/9317947/

  • McGregor A and Vu H. (2019). Better Streaming Algorithms for the Maximum Coverage Problem. Theory of Computing Systems. 63:7. (1595-1619). Online publication date: 1-Oct-2019.

    https://doi.org/10.1007/s00224-018-9878-x

  • Kapralov M and Krachun D. An optimal space lower bound for approximating MAX-CUT. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. (277-288).

    https://doi.org/10.1145/3313276.3316364

  • Assadi S, Chen Y and Khanna S. Polynomial pass lower bounds for graph streaming algorithms. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. (265-276).

    https://doi.org/10.1145/3313276.3316361

  • Huang Z and Peng P. (2019). Dynamic Graph Stream Algorithms in o(n) Space. Algorithmica. 81:5. (1965-1987). Online publication date: 1-May-2019.

    https://doi.org/10.1007/s00453-018-0520-8

  • Assadi S, Bateni M, Bernstein A, Mirrokni V and Stein C. Coresets Meet EDCS. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. (1616-1635).

    /doi/10.5555/3310435.3310533

  • Kallaugher J, Kapralov M and Price E. (2018). The Sketching Complexity of Graph and Hypergraph Counting 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). 10.1109/FOCS.2018.00059. 978-1-5386-4230-6. (556-567).

    https://ieeexplore.ieee.org/document/8555137/

  • Assadi S and Khanna S. Tight bounds on the round complexity of the distributed maximum coverage problem. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. (2412-2431).

    /doi/10.5555/3174304.3175460

  • Assadi S and Khanna S. Randomized Composable Coresets for Matching and Vertex Cover. Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures. (3-12).

    https://doi.org/10.1145/3087556.3087581

  • Kapralov M, Khanna S, Sudan M and Velingker A. (1 + Ω(1))-approximation to MAX-CUT requires linear space. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. (1703-1722).

    /doi/10.5555/3039686.3039798

  • Dolgorsuren B, Xu W, Khan K, Jeong B and Lee Y. SP2. Proceedings of the Sixth International Conference on Emerging Databases: Technologies, Applications, and Theory. (43-50).

    https://doi.org/10.1145/3007818.3007837

  • Abraham I, Durfee D, Koutis I, Krinninger S and Peng R. (2016). On Fully Dynamic Graph Sparsifiers 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). 10.1109/FOCS.2016.44. 978-1-5090-3933-3. (335-344).

    http://ieeexplore.ieee.org/document/7782947/

  • Chitnis R, Cormode G, Esfandiari H, Hajiaghayi M, McGregor A, Monemizadeh M and Vorotnikova S. Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams. Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms. (1326-1344).

    /doi/10.5555/2884435.2884527

  • Bhattacharya S, Henzinger M, Nanongkai D and Tsourakakis C. Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams. Proceedings of the forty-seventh annual ACM symposium on Theory of Computing. (173-182).

    https://doi.org/10.1145/2746539.2746592

  • Guha S, McGregor A and Tench D. Vertex and Hyperedge Connectivity in Dynamic Graph Streams. Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. (241-247).

    https://doi.org/10.1145/2745754.2745763

  • Kapralov M, Khanna S and Sudan M. Streaming lower bounds for approximating MAX-CUT. Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. (1263-1282).

    /doi/10.5555/2722129.2722213

  • McGregor A, Tench D, Vorotnikova S and Vu H. (2015). Densest Subgraph in Dynamic Graph Streams. Mathematical Foundations of Computer Science 2015. 10.1007/978-3-662-48054-0_39. (472-482).

    http://link.springer.com/10.1007/978-3-662-48054-0_39

  • McGregor A. (2015). Graph Sketching. Encyclopedia of Algorithms. 10.1007/978-3-642-27848-8_796-1. (1-5).

    https://link.springer.com/10.1007/978-3-642-27848-8_796-1

  • Kapralov M, Lee Y, Musco C, Musco C and Sidford A. Single Pass Spectral Sparsification in Dynamic Streams. Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. (561-570).

    https://doi.org/10.1109/FOCS.2014.66