{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:48:54Z","timestamp":1780822134032,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":24,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"David and Lucile Packard Fellowship","award":[""],"award-info":[{"award-number":[""]}]},{"name":"NSF","award":["CCF-1954927"],"award-info":[{"award-number":["CCF-1954927"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585231","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"267-280","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Sublinear Time Algorithms and Complexity of Approximate Maximum Matching"],"prefix":"10.1145","author":[{"given":"Soheil","family":"Behnezhad","sequence":"first","affiliation":[{"name":"Northeastern University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammad","family":"Roghani","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aviad","family":"Rubinstein","sequence":"additional","affiliation":[{"name":"Stanford University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_2_1_2_1","volume-title":"48th International Colloquium on Automata, Languages, and Programming, ICALP","author":"Assadi Sepehr","year":"2021","unstructured":"Sepehr Assadi and Soheil Behnezhad . 2021. Beating Two-Thirds For Random-Order Streaming Matching . In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021 , July 12-16, 2021, Glasgow, Scotland (Virtual Conference), Nikhil Bansal, Emanuela Merelli, and James Worrell (Eds.) (LIPIcs , Vol. 198). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 19:1\u201319: 13 . Sepehr Assadi and Soheil Behnezhad. 2021. Beating Two-Thirds For Random-Order Streaming Matching. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), Nikhil Bansal, Emanuela Merelli, and James Worrell (Eds.) (LIPIcs, Vol. 198). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 19:1\u201319:13."},{"key":"e_1_3_2_1_3_1","volume-title":"2nd Symposium on Simplicity in Algorithms, SOSA 2019","volume":"20","author":"Assadi Sepehr","year":"2019","unstructured":"Sepehr Assadi and Aaron Bernstein . 2019 . Towards a Unified Theory of Sparsification for Matching Problems . In 2nd Symposium on Simplicity in Algorithms, SOSA 2019 , January 8-9, 2019, San Diego, CA, USA, Jeremy T. Fineman and Michael Mitzenmacher (Eds.) (OASIcs , Vol. 69). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 11:1\u201311: 20 . Sepehr Assadi and Aaron Bernstein. 2019. Towards a Unified Theory of Sparsification for Matching Problems. In 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8-9, 2019, San Diego, CA, USA, Jeremy T. Fineman and Michael Mitzenmacher (Eds.) (OASIcs, Vol. 69). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 11:1\u201311:20."},{"key":"e_1_3_2_1_4_1","volume-title":"Improved Analysis of EDCS via Gallai-Edmonds Decomposition. CoRR, abs\/2110.05746","author":"Behnezhad Soheil","year":"2021","unstructured":"Soheil Behnezhad . 2021. Improved Analysis of EDCS via Gallai-Edmonds Decomposition. CoRR, abs\/2110.05746 ( 2021 ), arXiv:2110.05746. Soheil Behnezhad. 2021. Improved Analysis of EDCS via Gallai-Edmonds Decomposition. CoRR, abs\/2110.05746 (2021), arXiv:2110.05746."},{"key":"e_1_3_2_1_5_1","volume-title":"Time-Optimal Sublinear Algorithms for Matching and Vertex Cover. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021","author":"Behnezhad Soheil","year":"2021","unstructured":"Soheil Behnezhad . 2021 . Time-Optimal Sublinear Algorithms for Matching and Vertex Cover. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 , Denver, CO, USA , February 7-10, 2022. IEEE, 873\u2013884. Soheil Behnezhad. 2021. Time-Optimal Sublinear Algorithms for Matching and Vertex Cover. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022. IEEE, 873\u2013884."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch6"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Soheil Behnezhad and Sanjeev Khanna. [n. d.]. New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS. 3529\u20133566. arxiv:https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/1.9781611977073.140. \t\t\t\t  Soheil Behnezhad and Sanjeev Khanna. [n. d.]. New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS. 3529\u20133566. arxiv:https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/1.9781611977073.140.","DOI":"10.1137\/1.9781611977073.140"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch151"},{"key":"e_1_3_2_1_9_1","first-page":"1868","volume-title":"47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Artur Czumaj, Anuj Dawar, and Emanuela Merelli (Eds.) (Leibniz International Proceedings in Informatics (LIPIcs)","volume":"13","author":"Bernstein Aaron","year":"2020","unstructured":"Aaron Bernstein . 2020 . Improved Bounds for Matching in Random-Order Streams. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Artur Czumaj, Anuj Dawar, and Emanuela Merelli (Eds.) (Leibniz International Proceedings in Informatics (LIPIcs) , Vol. 168). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany. 12:1\u201312: 13 . isbn:978-3-95977-138-2 issn: 1868 - 8969 Aaron Bernstein. 2020. Improved Bounds for Matching in Random-Order Streams. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Artur Czumaj, Anuj Dawar, and Emanuela Merelli (Eds.) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 168). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany. 12:1\u201312:13. isbn:978-3-95977-138-2 issn:1868-8969"},{"key":"e_1_3_2_1_10_1","volume-title":"Fully Dynamic Matching in Bipartite Graphs","author":"Bernstein Aaron","unstructured":"Aaron Bernstein and Cliff Stein . 2015. Fully Dynamic Matching in Bipartite Graphs . In Automata, Languages, and Programming, Magn\u00fas M. Halld\u00f3rsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg . 167\u2013179. isbn:978-3-662-47672-7 Aaron Bernstein and Cliff Stein. 2015. Fully Dynamic Matching in Bipartite Graphs. In Automata, Languages, and Programming, Magn\u00fas M. Halld\u00f3rsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 167\u2013179. isbn:978-3-662-47672-7"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884485"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Sayan Bhattacharya Peter Kiss and Thatchaphol Saranurak. 2022. Sublinear Algorithms for (1.5 + \u220a )-Approximate Matching. \t\t\t\t  Sayan Bhattacharya Peter Kiss and Thatchaphol Saranurak. 2022. Sublinear Algorithms for (1.5 + \u220a )-Approximate Matching.","DOI":"10.1145\/3564246.3585252"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Sayan Bhattacharya Peter Kiss Thatchaphol Saranurak and David Wajc. 2023. Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time. \t\t\t\t  Sayan Bhattacharya Peter Kiss Thatchaphol Saranurak and David Wajc. 2023. Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time.","DOI":"10.1137\/1.9781611977554.ch5"},{"key":"e_1_3_2_1_14_1","volume-title":"47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference). 30:1\u201330:19","author":"Chen Yu","year":"2020","unstructured":"Yu Chen , Sampath Kannan , and Sanjeev Khanna . 2020 . Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference). 30:1\u201330:19 . Yu Chen, Sampath Kannan, and Sanjeev Khanna. 2020. Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference). 30:1\u201330:19."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.41"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.107"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755615"},{"key":"e_1_3_2_1_20_1","volume-title":"49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008","author":"Huy","year":"2008","unstructured":"Huy N. Nguyen and Krzysztof Onak. 2008. Constant-Time Approximation Algorithms via Local Improvements . In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 , October 25-28, 2008 , Philadelphia, PA, USA. 327\u2013336. Huy N. Nguyen and Krzysztof Onak. 2008. Constant-Time Approximation Algorithms via Local Improvements. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA. 327\u2013336."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.88"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1280283.1280327"},{"key":"e_1_3_2_1_23_1","volume-title":"Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract). In 18th Annual Symposium on Foundations of Computer Science","author":"Chi-Chih Yao Andrew","year":"1977","unstructured":"Andrew Chi-Chih Yao . 1977 . Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract). In 18th Annual Symposium on Foundations of Computer Science , Providence, Rhode Island , USA, 31 October - 1 November 1977. IEEE Computer Society, 222\u2013227. Andrew Chi-Chih Yao. 1977. Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract). In 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1 November 1977. IEEE Computer Society, 222\u2013227."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536447"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585231","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585231","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:02Z","timestamp":1750178822000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585231"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":24,"alternative-id":["10.1145\/3564246.3585231","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585231","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}