[1]   Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams: Tight hardness results for LCS and other sequence similarity measures. In Proc. 56th FOCS, pp. 59–78. IEEE Comp. Soc., 2015. [doi:10.1109/FOCS.2015.14]

[2]   Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof: More consequences of falsifying SETH and the orthogonal vectors conjecture. In Proc. 50th STOC, pp. 253–266. ACM Press, 2018. [doi:10.1145/3188745.3188938]

[3]   Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemysław Uznański, and Daniel Wolleb-Graf: Faster algorithms for all-pairs bounded min-cuts. In Proc. 46th Internat. Colloq. on Automata, Languages, and Programming (ICALP’19), volume 132, pp. 7:1–7:15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.ICALP.2019.7]

[4]   Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi: New algorithms and lower bounds for all-pairs max-flow in undirected graphs. In Proc. 31st Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’20), pp. 48–61. SIAM, 2020. [doi:10.1137/1.9781611975994.4, arXiv:1901.01412]

[5]   Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi: APMF ¡ APSP? Gomory–Hu tree for unweighted graphs in almost-quadratic time, 2021. Accepted to FOCS 2021. [arXiv:2106.02981]

[6]   Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi: Subcubic algorithms for Gomory–Hu tree in unweighted graphs. In Proc. 53rd STOC, pp. 1725–1737. ACM Press, 2021. [doi:10.1145/3406325.3451073]

[7]   Amir Abboud and Virginia Vassilevska Williams: Popular conjectures imply strong lower bounds for dynamic problems. In Proc. 55th FOCS, pp. 434–443. IEEE Comp. Soc., 2014. [doi:10.1109/FOCS.2014.53]

[8]   Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu: Matching triangles and basing hardness on an extremely popular conjecture. SIAM J. Comput., 47(3):1098–1122, 2018. Preliminary version in STOC’15. [doi:doi:10.1137/15M1050987]

[9]   Eyad Alkassar, Sascha Böhme, Kurt Mehlhorn, and Christine Rizkallah: A framework for the verification of certifying computations. J. Autom. Reason., 52(3):241–273, 2014. Preliminary version in CAV’11. [doi:10.1007/s10817-013-9289-2]

[10]   Nima Anari and Vijay V. Vazirani: Planar graph perfect matching is in NC. J. ACM, 67(4):21:1–21:34, 2020. Preliminary version in FOCS’18. [doi:10.1145/3397504]

[11]   Srinivasa Rao Arikati, Shiva Chaudhuri, and Christos D. Zaroliagis: All-pairs min-cut in sparse networks. J. Algorithms, 29(1):82–110, 1998. [doi:10.1006/jagm.1998.0961]

[12]   Jørgen Bang-Jensen, András Frank, and Bill Jackson: Preserving and increasing local edge-connectivity in mixed graphs. SIAM J. Discr. Math., 8(2):155–178, 1995. [doi:10.1137/S0036142993226983]

[13]   Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi: An (mn) Gomory–Hu tree construction algorithm for unweighted graphs. In Proc. 39th STOC, pp. 605–614. ACM Press, 2007. [doi:10.1145/1250790.1250879]

[14]   Glencora Borradaile, David Eppstein, Amir Nayyeri, and Christian Wulff-Nilsen: All-pairs minimum cuts in near-linear time for surface-embedded graphs. In Proc. 32nd Internat. Symp. Comput. Geom. (SoCG’16), pp. 22:1–22:16. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.SoCG.2016.22, arXiv:1411.7055]

[15]   Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang: Minimum cost flows, MDPs, and ℓ₁-regression in nearly linear time for dense instances. In Proc. 53rd STOC, pp. 859–869. ACM Press, 2021. [doi:10.1145/3406325.3451108]

[16]   Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider: Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proc. 7th Innovations in Theoret. Comp. Sci. Conf. (ITCS’16), pp. 261–270. ACM Press, 2016. [doi:10.1145/2840728.2840746]

[17]   Ho Yee Cheung, Lap Chi Lau, and Kai Man Leung: Graph connectivities, network coding, and expander graphs. SIAM J. Comput., 42(3):733–751, 2013. [doi:10.1137/110844970]

[18]   Robert T. Chien: Synthesis of a communication net. IBM J. Res. Dev., 4(3):311–320, 1960. [doi:10.1147/rd.43.0311]

[19]   Richard Cole and Ramesh Hariharan: A fast algorithm for computing Steiner edge connectivity. In Proc. 35th STOC, pp. 167–176. ACM Press, 2003. [doi:10.1145/780542.780568]

[20]   Jack Edmonds: Submodular functions, matroids, and certain polyhedra. In Combinatorial Structures and Their Appl., Proc. Conf. Calgary 1969, pp. 69–87. Gordon and Breach, 1970. [doi:10.1007/3-540-36478-1_2]

[21]   Lester R. Ford and Delbert R. Fulkerson: Maximal flow through a network. Canad. J. Math., 8(3):399–404, 1956. [doi:10.4153/CJM-1956-045-5]

[22]   Harold N. Gabow: A matroid approach to finding edge connectivity and packing arborescences. J. Comput. System Sci., 50(2):259–273, 1995. Preliminary version in STOC’91. [doi:10.1006/jcss.1995.1022]

[23]   Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and R. Ryan Williams: Completeness for first-order properties on sparse structures with algorithmic applications. ACM Trans. Algorithms, 15(2):1–35, 2019. Preliminary version in SODA’17. [doi:10.1145/3196275]

[24]   Loukas Georgiadis, Daniel Graf, Giuseppe F. Italiano, Nikos Parotsidis, and Przemysław Uznański: All-pairs 2-reachability in O(n^ω log n) time. In Proc. 44th Internat. Colloq. on Automata, Languages, and Programming (ICALP’17), volume 80, pp. 74:1–74:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.ICALP.2017.74]

[25]   Andrew V. Goldberg and Kostas Tsioutsiouliklis: Cut tree algorithms: an experimental study. J. Algorithms, 38(1):51–83, 2001. [doi:10.1006/jagm.2000.1136]

[26]   Ralph E. Gomory and Te Chiang Hu: Multi-terminal network flows. J. SIAM, 9(4):551–570, 1961. [doi:10.1137/0109047]

[27]   Frieda Granot and Refael Hassin: Multi-terminal maximum flows in node-capacitated networks. Discr. Appl. Math., 13(2-3):157–163, 1986. [doi:10.1016/0166-218X(86)90079-X]

[28]   Dan Gusfield: Very simple methods for all pairs network flow analysis. SIAM J. Comput., 19(1):143–155, 1990. [doi:10.1137/0219009]

[29]   Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi: Efficient algorithms for computing all low s - t edge connectivities and related problems. In Proc. 18th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’07), pp. 127–136. SIAM, 2007. ACM DL.

[30]   Refael Hassin and Asaf Levin: Flow trees for vertex-capacitated networks. Discr. Appl. Math., 155(4):572–578, 2007. [doi:10.1016/j.dam.2006.08.012]

[31]   Russell Impagliazzo and Ramamohan Paturi: On the complexity of k-SAT. J. Comput. System Sci., 62(2):367–375, 2001. [doi:10.1006/jcss.2000.1727]

[32]   Frederick Jelinek: On the maximum number of different entries in the terminal capacity matrix of oriented communication nets. IRE Trans. Circuit Theory, 10(2):307–308, 1963. [doi:10.1109/TCT.1963.1082149]

[33]   Robert Krauthgamer and Ohad Trabelsi: Conditional lower bounds for all-pairs max-flow. ACM Trans. Algorithms, 14(4):42:1–42:15, 2018. [doi:10.1145/3212510]

[34]   Marvin Künnemann: On nondeterministic derandomization of Freivalds’ algorithm: Consequences, avenues and algorithmic progress. In Proc. 26th Eur. Symp. Algorithms (ESA’18), pp. 56:1–56:16. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ESA.2018.56]

[35]   Jakub Lacki, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen: Single source – all sinks max flows in planar digraphs. In Proc. 53rd FOCS, pp. 599–608. IEEE Comp. Soc., 2012. [doi:10.1109/FOCS.2012.66]

[36]   Yin Tat Lee and Aaron Sidford: Path finding methods for linear programming: Solving linear programs in () iterations and faster algorithms for maximum flow. In Proc. 55th FOCS, pp. 424–433. IEEE Comp. Soc., 2014. [doi:10.1109/FOCS.2014.52]

[37]   Jason Li, Debmalya Panigrahi, and Thatchaphol Saranurak: A nearly optimal all-pairs min-cuts algorithm in simple graphs, 2021. Accepted to FOCS 2021. [arXiv:2106.02233]

[38]   Yang P. Liu and Aaron Sidford: Faster energy maximization for faster maximum flow. In Proc. 52nd STOC, pp. 803–814. ACM Press, 2020. [doi:10.1145/3357713.3384247]

[39]   Aleksander Madry: Computing maximum flow with augmenting electrical flows. In Proc. 57th FOCS, pp. 593–602. IEEE Comp. Soc., 2016. [doi:10.1109/FOCS.2016.70]

[40]   Wataru Mayeda: Terminal and branch capacity matrices of a communication net. IRE Trans. Circuit Theory, 7(3):261–269, 1960. [doi:10.1109/TCT.1960.1086673]

[41]   Wataru Mayeda: On oriented communication nets. IRE Trans. Circuit Theory, 9(3):261–267, 1962. [doi:10.1109/TCT.1962.1086912]

[42]   Ross M. McConnell, Kurt Mehlhorn, Stefan Näher, and Pascal Schweitzer: Certifying algorithms. Computer Sci. Review, 5(2):119–161, 2011. [doi:10.1016/j.cosrev.2010.09.009]

[43]   Debmalya Panigrahi: Gomory–Hu trees. In Ming-Yang Kao, editor, Encyclopedia of Algorithms, pp. 858–861. Springer, 2016. [doi:10.1007/978-1-4939-2864-4_168]

[44]   Aaron Sidford and Kevin Tian: Coordinate methods for accelerating ℓ_∞ regression and faster approximate maximum flow. In Proc. 59th FOCS, pp. 922–933. IEEE Comp. Soc., 2018. [doi:10.1109/FOCS.2018.00091]

[45]   R. Ryan Williams: A new algorithm for optimal 2-constraint satisfaction and its implications. Theoret. Comput. Sci., 348(2–3):357–365, 2005. [doi:10.1016/j.tcs.2005.09.023]

[46]   R. Ryan Williams: Strong ETH breaks with Merlin and Arthur: Short non-interactive proofs of batch evaluation. In Proc. 31st Comput. Complexity Conf. (CCC’16), pp. 2:1–2:17. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.2, arXiv:1601.04743]

[47]   Zhenyu Wu and Richard Leahy: An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation. ACM Trans. Pattern Anal. Machine Intell., 15(11):1101–1113, 1993. [doi:10.1109/34.244673]

[48]   Tianyi Zhang: Faster cut-equivalent trees in simple graphs, 2021. [arXiv:2106.03305]