{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,27]],"date-time":"2026-08-27T23:10:24Z","timestamp":1787872224759,"version":"build-2784847793"},"publisher-location":"New York, NY, USA","reference-count":146,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316361","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T08:19:08Z","timestamp":1561018748000},"page":"265-276","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Polynomial pass lower bounds for graph streaming algorithms"],"prefix":"10.1145","author":[{"given":"Sepehr","family":"Assadi","sequence":"first","affiliation":[{"name":"Princeton University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yu","family":"Chen","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Amir Abboud Keren Censor-Hillel Seri Khoury and Ami Paz. 2019. Smaller Cuts Higher Lower Bounds. CoRR abs\/1901.01630 (2019).  Amir Abboud Keren Censor-Hillel Seri Khoury and Ami Paz. 2019. Smaller Cuts Higher Lower Bounds. CoRR abs\/1901.01630 (2019)."},{"key":"e_1_3_2_1_2_1","volume-title":"20nd International Colloquium, ICALP93","author":"Ablayev Farid M.","year":"1993"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095156"},{"key":"e_1_3_2_1_4_1","unstructured":"Kook Jin Ahn Sudipto Guha and Andrew McGregor. 2012.  Kook Jin Ahn Sudipto Guha and Andrew McGregor. 2012."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213560"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_3_2_1_8_1","volume-title":"Welfare Maximization with Limited Interaction. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015","author":"Alon Noga","year":"2015"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085121"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056116"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Sepehr Assadi Yu Chen and Sanjeev Khanna. 2019. Polynomial Pass Lower Bounds for Graph Streaming Algorithms. CoRR abs\/1904.04720 (2019).  Sepehr Assadi Yu Chen and Sanjeev Khanna. 2019. Polynomial Pass Lower Bounds for Graph Streaming Algorithms. CoRR abs\/1904.04720 (2019).","DOI":"10.1145\/3313276.3316361"},{"key":"e_1_3_2_1_12_1","unstructured":"Sepehr Assadi Yu Chen and Sanjeev Khanna. 2019.  Sepehr Assadi Yu Chen and Sanjeev Khanna. 2019."},{"key":"e_1_3_2_1_13_1","volume-title":"Vertex Coloring. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019","author":"Sublinear Algorithms","year":"2019"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175460"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897576"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039799"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884528"},{"key":"e_1_3_2_1_18_1","unstructured":"1345\u20131364.  1345\u20131364."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.15"},{"key":"e_1_3_2_1_20_1","unstructured":"Eric Balkanski Adam Breuer and Yaron Singer. 2018. Non-monotone Submodular Maximization in Exponentially Fewer Iterations. CoRR abs\/1807.11462. To appear in NIPS 2018. (2018).   Eric Balkanski Adam Breuer and Yaron Singer. 2018. Non-monotone Submodular Maximization in Exponentially Fewer Iterations. CoRR abs\/1807.11462. To appear in NIPS 2018. (2018)."},{"key":"e_1_3_2_1_21_1","volume-title":"Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016","author":"Balkanski Eric","year":"2016"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055406"},{"key":"e_1_3_2_1_23_1","unstructured":"Eric Balkanski Aviad Rubinstein and Yaron Singer. 2018.  Eric Balkanski Aviad Rubinstein and Yaron Singer. 2018."},{"key":"e_1_3_2_1_24_1","unstructured":"An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. CoRR abs\/1804.06355. To appear in SODA 2019. (2018).  An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. CoRR abs\/1804.06355. To appear in SODA 2019. (2018)."},{"key":"e_1_3_2_1_25_1","unstructured":"Eric Balkanski and Yaron Singer. 2017.  Eric Balkanski and Yaron Singer. 2017."},{"key":"e_1_3_2_1_26_1","volume-title":"Samples. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017","author":"Submodular Minimizing","year":"2017"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188752"},{"key":"e_1_3_2_1_28_1","unstructured":"1138\u20131151.  1138\u20131151."},{"key":"e_1_3_2_1_29_1","unstructured":"Polynomial Pass Lower Bounds for Graph Streaming Algorithms STOC \u201919 June 23\u201326 2019 Phoenix AZ USA  Polynomial Pass Lower Bounds for Graph Streaming Algorithms STOC \u201919 June 23\u201326 2019 Phoenix AZ USA"},{"key":"e_1_3_2_1_30_1","unstructured":"Eric Balkanski and Yaron Singer. 2018.  Eric Balkanski and Yaron Singer. 2018."},{"key":"e_1_3_2_1_31_1","unstructured":"Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimization. CoRR abs\/1808.03880 (2018).  Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimization. CoRR abs\/1808.03880 (2018)."},{"key":"e_1_3_2_1_32_1","volume-title":"43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Proceedings. 209\u2013218","author":"Bar-Yossef Ziv"},{"key":"e_1_3_2_1_33_1","volume-title":"Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Bar-Yossef Ziv","year":"2002"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806701"},{"key":"e_1_3_2_1_35_1","unstructured":"MohammadHossein Bateni Hossein Esfandiari and Vahab S. Mirrokni. 2017.  MohammadHossein Bateni Hossein Esfandiari and Vahab S. Mirrokni. 2017."},{"key":"e_1_3_2_1_36_1","volume-title":"Optimal Streaming Algorithms for Coverage Problems. In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2017, Washington DC, USA","author":"Almost","year":"2017"},{"key":"e_1_3_2_1_37_1","volume-title":"Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In 31st International Symposium on Distributed Computing, DISC 2017","author":"Becker Ruben","year":"2017"},{"key":"e_1_3_2_1_38_1","unstructured":"Suman K. Bera and Amit Chakrabarti. 2017.  Suman K. Bera and Amit Chakrabarti. 2017."},{"key":"e_1_3_2_1_39_1","volume-title":"Tighter Space Bounds for Counting Triangles and Other Substructures in Graph Streams. In 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017","author":"Towards","year":"2017"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2312005.2312058"},{"key":"e_1_3_2_1_41_1","unstructured":"Mark Braverman Faith Ellen Rotem Oshman Toniann Pitassi and Vinod Vaikuntanathan. 2013.  Mark Braverman Faith Ellen Rotem Oshman Toniann Pitassi and Vinod Vaikuntanathan. 2013."},{"key":"e_1_3_2_1_42_1","volume-title":"Tight Bound for Set Disjointness in the Message-Passing Model. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October","author":"A","year":"2013"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488628"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175451"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488629"},{"key":"e_1_3_2_1_46_1","unstructured":"Mark Braverman and Rotem Oshman. 2017.  Mark Braverman and Rotem Oshman. 2017."},{"key":"e_1_3_2_1_47_1","volume-title":"Communication Tradeoff for Multi-Party Set Disjointness. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017","author":"A Rounds","year":"2017"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.86"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611501"},{"key":"e_1_3_2_1_50_1","volume-title":"Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010","author":"Chakrabarti Amit","year":"2010"},{"key":"e_1_3_2_1_51_1","unstructured":"Amit Chakrabarti Graham Cormode and Andrew McGregor. 2008.  Amit Chakrabarti Graham Cormode and Andrew McGregor. 2008."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374470"},{"key":"e_1_3_2_1_53_1","unstructured":"641\u2013650.  641\u2013650."},{"key":"e_1_3_2_1_54_1","unstructured":"Amit Chakrabarti and Sagar Kale. 2014.  Amit Chakrabarti and Sagar Kale. 2014."},{"key":"e_1_3_2_1_55_1","volume-title":"IPCO 2014, Bonn, Germany, June 23-25, 2014. Proceedings. 210\u2013221","author":"Meets Streaming Submodular Maximization"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884529"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055419"},{"key":"e_1_3_2_1_58_1","volume-title":"Tribes Is Hard in the Message Passing Model. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015","author":"Chattopadhyay Arkadev","year":"2015"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"e_1_3_2_1_60_1","volume-title":"ISCO 2018","author":"Cormode Graham","year":"2018"},{"key":"e_1_3_2_1_61_1","unstructured":"Graham Cormode Jacques Dark and Christian Konrad. 2018. Independent Sets in Vertex-Arrival Streams. CoRR abs\/1807.08331 (2018).  Graham Cormode Jacques Dark and Christian Konrad. 2018. Independent Sets in Vertex-Arrival Streams. CoRR abs\/1807.08331 (2018)."},{"key":"e_1_3_2_1_62_1","unstructured":"Graham Cormode and Hossein Jowhari. 2017.  Graham Cormode and Hossein Jowhari. 2017."},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"crossref","unstructured":"A second look at counting triangles in graph streams (corrected). Theor. Comput. Sci. 683 (2017) 22\u201330.  A second look at counting triangles in graph streams (corrected). Theor. Comput. Sci. 683 (2017) 22\u201330.","DOI":"10.1016\/j.tcs.2016.06.020"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579361"},{"key":"e_1_3_2_1_65_1","volume-title":"DISC 2014, Austin, TX, USA, October 12-15, 2014. Proceedings. 484\u2013498","author":"Demaine Erik D.","year":"2014"},{"key":"e_1_3_2_1_66_1","unstructured":"Shahar Dobzinski Noam Nisan and Sigal Oren. 2014.  Shahar Dobzinski Noam Nisan and Sigal Oren. 2014."},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591815"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808668"},{"key":"e_1_3_2_1_69_1","volume-title":"17th Annual European Symposium, September 7-9, 2009. Proceedings. 492\u2013503","author":"Eggert Sebastian","year":"2009"},{"key":"e_1_3_2_1_70_1","volume-title":"41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I. 453\u2013464","author":"Emek Yuval","year":"2014"},{"key":"e_1_3_2_1_71_1","unstructured":"Alina Ene and Huy L. Nguyen. 2018.  Alina Ene and Huy L. Nguyen. 2018."},{"key":"e_1_3_2_1_72_1","unstructured":"Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time. CoRR abs\/1804.05379. To appear in SODA 2019. (2018).  Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time. CoRR abs\/1804.05379. To appear in SODA 2019. (2018)."},{"key":"e_1_3_2_1_73_1","unstructured":"Alina Ene Huy L. Nguyen and Adrian Vladu. 2018. Submodular Maximization with Packing Constraints in Parallel. CoRR abs\/1808.09987 (2018).  Alina Ene Huy L. Nguyen and Adrian Vladu. 2018. Submodular Maximization with Packing Constraints in Parallel. CoRR abs\/1808.09987 (2018)."},{"key":"e_1_3_2_1_74_1","unstructured":"Matthew Fahrbach Vahab S. Mirrokni and Morteza Zadimoghaddam. 2018.  Matthew Fahrbach Vahab S. Mirrokni and Morteza Zadimoghaddam. 2018."},{"key":"e_1_3_2_1_75_1","unstructured":"Non-monotone Submodular Maximization with Nearly Optimal Adaptivity Complexity. CoRR abs\/1808.06932 (2018).  Non-monotone Submodular Maximization with Nearly Optimal Adaptivity Complexity. CoRR abs\/1808.06932 (2018)."},{"key":"e_1_3_2_1_76_1","unstructured":"Matthew Fahrbach Vahab S. Mirrokni and Morteza Zadimoghaddam. 2018.  Matthew Fahrbach Vahab S. Mirrokni and Morteza Zadimoghaddam. 2018."},{"key":"e_1_3_2_1_77_1","unstructured":"Submodular Maximization with Optimal Approximation Adaptivity and Query Complexity. CoRR abs\/1807.07889. To appear in SODA 2019. (2018).  Submodular Maximization with Optimal Approximation Adaptivity and Query Complexity. CoRR abs\/1807.07889. To appear in SODA 2019. (2018)."},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683155"},{"key":"e_1_3_2_1_80_1","unstructured":"Dmitry Gavinsky Julia Kempe Iordanis Kerenidis Ran Raz and Ronald de Wolf. 2007.  Dmitry Gavinsky Julia Kempe Iordanis Kerenidis Ran Raz and Ronald de Wolf. 2007."},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250866"},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095157"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_3_2_1_85_1","volume-title":"34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings. 704\u2013715","author":"Guha Sudipto","year":"2007"},{"key":"e_1_3_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_62"},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2013.37"},{"key":"e_1_3_2_1_88_1","volume-title":"37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I. 641\u2013652","author":"Halld\u00f3rsson Bjarni V.","year":"2010"},{"key":"e_1_3_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0051-5"},{"key":"e_1_3_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_38"},{"key":"e_1_3_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902287"},{"key":"e_1_3_2_1_92_1","unstructured":"Nicholas James Alexander Harvey. 2008.  Nicholas James Alexander Harvey. 2008."},{"key":"e_1_3_2_1_93_1","unstructured":"Matchings matroids and submodular functions. Ph.D. Dissertation. Massachusetts Institute of Technology.  Matchings matroids and submodular functions. Ph.D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_3_2_1_94_1","volume-title":"Sn. In Proceedings of the Nineteenth Annual ACMSIAM Symposium on Discrete Algorithms, SODA 2008","author":"Harvey Nicholas J. A.","year":"2008"},{"key":"e_1_3_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897638"},{"key":"e_1_3_2_1_96_1","unstructured":"489\u2013498.  489\u2013498."},{"key":"e_1_3_2_1_97_1","volume-title":"IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012","author":"Ivanyos G\u00e1bor","year":"2012"},{"key":"e_1_3_2_1_98_1","unstructured":"Satoru Iwata Lisa Fleischer and Satoru Fujishige. 2000.  Satoru Iwata Lisa Fleischer and Satoru Fujishige. 2000."},{"key":"e_1_3_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335317"},{"key":"e_1_3_2_1_100_1","unstructured":"Satoru Iwata and James B. Orlin. 2009.  Satoru Iwata and James B. Orlin. 2009."},{"key":"e_1_3_2_1_101_1","volume-title":"Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009","author":"A","year":"2009"},{"key":"e_1_3_2_1_102_1","unstructured":"Rahul Jain Jaikumar Radhakrishnan and Pranab Sen. 2003.  Rahul Jain Jaikumar Radhakrishnan and Pranab Sen. 2003."},{"key":"e_1_3_2_1_103_1","volume-title":"30th International Colloquium, ICALP 2003, June 30 - July 4, 2003. Proceedings. 300\u2013315","author":"Communication A Direct Sum"},{"key":"e_1_3_2_1_104_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780640"},{"key":"e_1_3_2_1_105_1","volume-title":"11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005, Proceedings. 710\u2013716","author":"Jowhari Hossein","year":"2005"},{"key":"e_1_3_2_1_106_1","unstructured":"Sagar Kale and Sumedh Tirodkar. 2017.  Sagar Kale and Sumedh Tirodkar. 2017."},{"key":"e_1_3_2_1_107_1","volume-title":"APPROX\/RANDOM 2017","author":"Two Maximum Matching","year":"2017"},{"key":"e_1_3_2_1_108_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405044"},{"key":"e_1_3_2_1_109_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.121"},{"key":"e_1_3_2_1_110_1","unstructured":"Michael Kapralov and David P. Woodruff. 2014.  Michael Kapralov and David P. Woodruff. 2014."},{"key":"e_1_3_2_1_111_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611497"},{"key":"e_1_3_2_1_112_1","unstructured":"Christian Konrad Fr\u00e9d\u00e9ric Magniez and Claire Mathieu. 2012.  Christian Konrad Fr\u00e9d\u00e9ric Magniez and Claire Mathieu. 2012."},{"key":"e_1_3_2_1_113_1","volume-title":"APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings. 231\u2013242","author":"Few Passes Maximum Matching"},{"key":"e_1_3_2_1_114_1","unstructured":"Ilan Kremer Noam Nisan and Dana Ron. 1995.  Ilan Kremer Noam Nisan and Dana Ron. 1995."},{"key":"e_1_3_2_1_115_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225277"},{"key":"e_1_3_2_1_116_1","unstructured":"Ravi Kumar Benjamin Moseley Sergei Vassilvitskii and Andrea Vattani. 2013.  Ravi Kumar Benjamin Moseley Sergei Vassilvitskii and Andrea Vattani. 2013."},{"key":"e_1_3_2_1_117_1","volume-title":"25th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA \u201913","author":"Fast","year":"2013"},{"key":"e_1_3_2_1_118_1","volume-title":"Copenhagen","author":"Kutzkov Konstantin","year":"2014"},{"key":"e_1_3_2_1_119_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.68"},{"key":"e_1_3_2_1_120_1","unstructured":"List of Open Problems in Sublinear Algorithms: Problem 14 {n. d.}. List of Open Problems in Sublinear Algorithms: Problem 14. https:\/\/sublinear.info\/14.  List of Open Problems in Sublinear Algorithms: Problem 14 {n. d.}. List of Open Problems in Sublinear Algorithms: Problem 14. https:\/\/sublinear.info\/14."},{"key":"e_1_3_2_1_121_1","unstructured":"List of Open Problems in Sublinear Algorithms: Problem 22 {n. d.}. List of Open Problems in Sublinear Algorithms: Problem 22. https:\/\/sublinear.info\/22.  List of Open Problems in Sublinear Algorithms: Problem 22 {n. d.}. List of Open Problems in Sublinear Algorithms: Problem 22. https:\/\/sublinear.info\/22."},{"key":"e_1_3_2_1_122_1","unstructured":"List of Open Problems in Sublinear Algorithms: Problem 29 {n. d.}. List of Open Problems in Sublinear Algorithms: Problem 29. https:\/\/sublinear.info\/29.  List of Open Problems in Sublinear Algorithms: Problem 29 {n. d.}. List of Open Problems in Sublinear Algorithms: Problem 29. https:\/\/sublinear.info\/29."},{"key":"e_1_3_2_1_123_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_1_124_1","unstructured":"Andrew McGregor. 2005.  Andrew McGregor. 2005."},{"key":"e_1_3_2_1_125_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_15"},{"key":"e_1_3_2_1_126_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_3_2_1_127_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902283"},{"key":"e_1_3_2_1_128_1","unstructured":"Andrew McGregor and Hoa T. Vu. 2017.  Andrew McGregor and Hoa T. Vu. 2017."},{"key":"e_1_3_2_1_129_1","volume-title":"Streaming Algorithms for the Maximum Coverage Problem. In 20th International Conference on Database Theory, ICDT 2017, March 21-24","author":"Better","year":"2017"},{"key":"e_1_3_2_1_130_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225093"},{"key":"e_1_3_2_1_131_1","unstructured":"J. Ian Munro and Mike Paterson. 1978.  J. Ian Munro and Mike Paterson. 1978."},{"key":"e_1_3_2_1_132_1","volume-title":"Sorting with Limited Storage. In 19th Annual Symposium on Foundations of Computer Science","author":"Selection","year":"1978"},{"key":"e_1_3_2_1_133_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1994.1025"},{"key":"e_1_3_2_1_134_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103463"},{"key":"e_1_3_2_1_135_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90069-2"},{"key":"e_1_3_2_1_136_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301413"},{"key":"e_1_3_2_1_137_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"e_1_3_2_1_138_1","volume-title":"Computing Exact Minimum Cuts Without Knowing the Graph. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018","author":"Rubinstein Aviad","year":"2018"},{"key":"e_1_3_2_1_139_1","volume-title":"Proceedings of the SIAM International Conference on Data Mining, SDM","author":"Saha Barna","year":"2009"},{"key":"e_1_3_2_1_140_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970397"},{"key":"e_1_3_2_1_141_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1989"},{"key":"e_1_3_2_1_142_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133038"},{"key":"e_1_3_2_1_143_1","volume-title":"42nd International Colloquium, ICALP 2015, July 6-10, 2015, Proceedings, Part I. 1082\u20131093","author":"Weinstein Omri"},{"key":"e_1_3_2_1_144_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804414"},{"key":"e_1_3_2_1_145_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.30"},{"key":"e_1_3_2_1_146_1","first-page":"151","article-title":"Pointer chasing via triangular discrimination","volume":"23","author":"Yehudayoff Amir","year":"2016","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","location":"Phoenix AZ USA","acronym":"STOC '19","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316361","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316361","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:54:32Z","timestamp":1750190072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316361"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":146,"alternative-id":["10.1145\/3313276.3316361","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316361","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}