{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,18]],"date-time":"2026-02-18T04:09:05Z","timestamp":1771387745216,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council","award":["617951"],"award-info":[{"award-number":["617951"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384264","type":"proceedings-article","created":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T21:48:11Z","timestamp":1624916891000},"page":"40-53","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Bipartite TSP in o(1.9999\u207f) time, assuming quadratic time matrix multiplication"],"prefix":"10.1145","author":[{"given":"Jesper","family":"Nederlof","sequence":"first","affiliation":[{"name":"Utrecht University, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.107"},{"key":"e_1_3_2_1_2_1","volume-title":"34th Computational Complexity Conference, CCC 2019","author":"Alman Josh","year":"2019","unstructured":"Josh Alman . Limits on the universal method for matrix multiplication . In 34th Computational Complexity Conference, CCC 2019 , July 18-20, 2019 , New Brunswick, NJ, USA., pages 12:1\u201312:24 , 2019. Josh Alman. Limits on the universal method for matrix multiplication. In 34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA., pages 12:1\u201312:24, 2019."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.008"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321111"},{"key":"e_1_3_2_1_5_1","first-page":"586","volume-title":"17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings","author":"Bj\u00f6rklund Andreas","year":"2009","unstructured":"Andreas Bj\u00f6rklund , Thore Husfeldt , Petteri Kaski , and Mikko Koivisto . Counting paths and packings in halves. In Algorithms - ESA 2009 , 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings , pages 578\u2013 586 , 2009 . Andreas Bj\u00f6rklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Counting paths and packings in halves. In Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, pages 578\u2013586, 2009."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2151171.2151181"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.03.003"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839229"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933101"},{"key":"e_1_3_2_1_10_1","volume-title":"44th International Colloquium on Automata, Languages, and Programming, ICALP 2017","author":"Bj\u00f6rklund Andreas","year":"2017","unstructured":"Andreas Bj\u00f6rklund , Petteri Kaski , and Ioannis Koutis . Directed hamiltonicity and out-branchings via generalized laplacians. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 , July 10-14, 2017 , Warsaw, Poland, pages 91:1\u201391:14 , 2017. Andreas Bj\u00f6rklund, Petteri Kaski, and Ioannis Koutis. Directed hamiltonicity and out-branchings via generalized laplacians. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 91:1\u201391:14, 2017."},{"key":"e_1_3_2_1_11_1","first-page":"231","volume-title":"WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings","author":"Chan Timothy M.","year":"2013","unstructured":"Timothy M. Chan . The art of shaving logs. In Algorithms and Data Structures - 13th International Symposium , WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings , page 231 , 2013 . Timothy M. Chan. The art of shaving logs. In Algorithms and Data Structures - 13th International Symposium, WADS 2013, London, ON, Canada, August 12-14, 2013. Proceedings, page 231, 2013."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3148227"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.39"},{"key":"e_1_3_2_1_15_1","first-page":"1099","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018","author":"Curticapean Radu","year":"2018","unstructured":"Radu Curticapean , Nathan Lindzey , and Jesper Nederlof . A tight lower bound for counting hamiltonian cycles via matrix rank . In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 , New Orleans, LA, USA , January 7-10, 2018 , pages 1080\u2013 1099 , 2018. Radu Curticapean, Nathan Lindzey, and Jesper Nederlof. A tight lower bound for counting hamiltonian cycles via matrix rank. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1080\u20131099, 2018."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400841103"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.007"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087604.3087609"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00137"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2886094"},{"key":"e_1_3_2_1_23_1","first-page":"842","volume-title":"Proceedings of the 7th IFIP Congress 1977","author":"Freivalds Rusins","year":"1977","unstructured":"Rusins Freivalds . Probabilistic machines can use less running time. In Information Processing , Proceedings of the 7th IFIP Congress 1977 , Toronto, Canada , August 8-12, 1977 ., pages 839\u2013 842 , 1977. Rusins Freivalds. Probabilistic machines can use less running time. In Information Processing, Proceedings of the 7th IFIP Congress 1977, Toronto, Canada, August 8-12, 1977., pages 839\u2013842, 1977."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972986.8"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216034"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0110015"},{"key":"e_1_3_2_1_28_1","first-page":"117","volume-title":"13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007","author":"Iwama Kazuo","year":"2007","unstructured":"Kazuo Iwama and Takuya Nakashima . An improved exact algorithm for cubic graph TSP. In Computing and Combinatorics , 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007 , Proceedings , pages 108\u2013 117 , 2007 . Kazuo Iwama and Takuya Nakashima. An improved exact algorithm for cubic graph TSP. In Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings, pages 108\u2013117, 2007."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(82)90044-X"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975055.16"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/800179.810218"},{"key":"e_1_3_2_1_33_1","first-page":"586","volume-title":"35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games","author":"Koutis Ioannis","year":"2008","unstructured":"Ioannis Koutis . Faster algebraic algorithms for path and packing problems. In Automata, Languages and Programming , 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games , pages 575\u2013 586 , 2008 . Ioannis Koutis. Faster algebraic algorithms for path and packing problems. In Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, pages 575\u2013586, 2008."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2742544"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2885499"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806735"},{"key":"e_1_3_2_1_37_1","first-page":"727","volume-title":"MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings","author":"Nederlof Jesper","year":"2012","unstructured":"Jesper Nederlof , Erik Jan van Leeuwen , and Ruben van der Zwaan. Reducing a target interval to a few exact queries. In Mathematical Foundations of Computer Science 2012 - 37th International Symposium , MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings , pages 718\u2013 727 , 2012 . Jesper Nederlof, Erik Jan van Leeuwen, and Ruben van der Zwaan. Reducing a target interval to a few exact queries. In Mathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings, pages 718\u2013727, 2012."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01192528"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Alexander\n      Schrijver\n    .\n  On the history of combinatorial optimization (till\n  1960\n  ). In K. Aardal G.L.\n   Nemhauser and R. Weismantel editors Discrete Optimization volume \n  12\n   of \n  Handbooks in Operations Research and Management Science pages \n  1\n   \u2013 68. \n  Elsevier 2005.  Alexander Schrijver. On the history of combinatorial optimization (till 1960). In K. Aardal G.L. Nemhauser and R. Weismantel editors Discrete Optimization volume 12 of Handbooks in Operations Research and Management Science pages 1 \u2013 68. Elsevier 2005.","DOI":"10.1016\/S0927-0507(05)12001-5"},{"key":"e_1_3_2_1_41_1","first-page":"76","article-title":"On some extremal tours in graphs (in russian)","volume":"17","author":"Serdyukov Anatoliy I.","year":"1978","unstructured":"Anatoliy I. Serdyukov . On some extremal tours in graphs (in russian) . Upravlyaemye systemy , 17 : 76 \u2013 79 , 1978 . Anatoliy I. Serdyukov. On some extremal tours in graphs (in russian). Upravlyaemye systemy, 17:76\u201379, 1978.","journal-title":"Upravlyaemye systemy"},{"key":"e_1_3_2_1_42_1","first-page":"446","volume-title":"First European Congress of Mathematics Paris, July 6\u201310","author":"Strassen Volker","year":"1992","unstructured":"Volker Strassen . Algebra and complexity . In First European Congress of Mathematics Paris, July 6\u201310 , 1992 , pages 429\u2013 446 . Springer, 1994. Volker Strassen. Algebra and complexity. In First European Congress of Mathematics Paris, July 6\u201310, 1992, pages 429\u2013446. Springer, 1994."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188824"},{"key":"e_1_3_2_1_44_1","volume-title":"The factorization of linear graphs. Journal of the London Mathematical Society, s1-22(2):107\u2013111","author":"Tutte William T.","year":"1947","unstructured":"William T. Tutte . The factorization of linear graphs. Journal of the London Mathematical Society, s1-22(2):107\u2013111 , 1947 . William T. Tutte. The factorization of linear graphs. Journal of the London Mathematical Society, s1-22(2):107\u2013111, 1947."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Vera Traub and Jens Vygen. Approaching 3\/2 for the s-t-path TSP. J. ACM 66(2):14:1\u201314:17 2019.  Vera Traub and Jens Vygen. Approaching 3\/2 for the s-t-path TSP. J. ACM 66(2):14:1\u201314:17 2019.","DOI":"10.1145\/3309715"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.11.004"},{"key":"e_1_3_2_1_47_1","first-page":"17","volume-title":"31st Conference on Computational Complexity, CCC 2016","author":"Williams Ryan","year":"2016","unstructured":"Ryan Williams . Strong ETH breaks with merlin and arthur: Short non-interactive proofs of batch evaluation . In 31st Conference on Computational Complexity, CCC 2016 , May 29 to June 1, 2016 , Tokyo, Japan, pages 2:1\u20132: 17 , 2016. Ryan Williams. Strong ETH breaks with merlin and arthur: Short non-interactive proofs of batch evaluation. In 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, pages 2:1\u20132:17, 2016."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1024524"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0489-3"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186893"},{"key":"e_1_3_2_1_51_1","volume-title":"The Design and Analysis of Factorial Experiments","author":"Yates Franck","year":"1937","unstructured":"Franck Yates . The Design and Analysis of Factorial Experiments . Imperial Bureau of Soil Science. Technical Communication. Imperial Bureau of Soil Science , 1937 . Franck Yates. The Design and Analysis of Factorial Experiments. Imperial Bureau of Soil Science. Technical Communication. Imperial Bureau of Soil Science, 1937."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.93"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384264","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384264","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384264"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":51,"alternative-id":["10.1145\/3357713.3384264","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384264","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}