%% Theory of Computing
%% File: v017a005.bib
%% Publication date: September 20, 2021
%% Authors: Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi

@INPROCEEDINGS{Kunnemann18,
  author    = {Marvin K{\"{u}}nnemann},
  title     = {On Nondeterministic Derandomization of {F}reivalds' Algorithm: Consequences, Avenues and Algorithmic Progress},
  crossref  = {pesa18},
  pages     = {56:1--56:16},
  doi       = {10.4230/LIPIcs.ESA.2018.56}
}
%
@article{alkassar2011verification,
  title={A framework for the verification of certifying computations},
  author={Alkassar, Eyad and B{\"o}hme, Sascha and Mehlhorn, Kurt and Rizkallah, Christine},
  journal = {J. Autom. Reason.},
  year = {2014},
  volume = {52},
  number = {3},
  pages={241--273},
  doi = {10.1007/s10817-013-9289-2},
  note = {\prelim \href{https://doi.org/10.1007/978-3-642-22110-1\_7}{CAV'11}},
}
%
@INPROCEEDINGS{alkassar2011verification-conf,
  title={Verification of certifying computations},
  author={Alkassar, Eyad and B{\"o}hme, Sascha and Mehlhorn, Kurt and Rizkallah, Christine},
  crossref= {pcav11},
  pages = {67--82},
  doi   = {10.1007/978-3-642-22110-1\_7},
}
%
@ARTICLE{certify_survey11,
  title={Certifying algorithms},
  author={McConnell, Ross M. and Mehlhorn, Kurt and N{\"a}her, Stefan and Schweitzer, Pascal},
  journal= cosrev,
  volume={5},
  number={2},
  pages={119--161},
  year={2011},
  publisher={Elsevier},
  doi = {10.1016/j.cosrev.2010.09.009},
}
%
@INPROCEEDINGS{Wil16_MASETH,
  author    = {R. Ryan Williams},
  title     = {Strong {ETH} Breaks With {M}erlin and {A}rthur: Short Non-Interactive Proofs of Batch Evaluation},
  crossref = {pccc16},
  pages     = {2:1--2:17},
  doi  = {10.4230/LIPIcs.CCC.2016.2},
eprint  =  {1601.04743},
}
%
@InCollection{Panigrahi16,
author="Panigrahi, Debmalya",
editor="Kao, Ming-Yang",
title="{G}omory--{H}u Trees",
bookTitle="Encyclopedia of Algorithms",
year="2016",
publisher= springer,
pages="858--861",
doi = {10.1007/978-1-4939-2864-4\_168},
}

@INPROCEEDINGS{carmosino2016nondeterministic,
 author = {Carmosino, Marco L. and Gao, Jiawei and Impagliazzo, Russell and Mihajlin, Ivan and Paturi, Ramamohan and Schneider, Stefan},
 title = {Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility},
 crossref = {pitcs16},
 pages = {261--270},
 doi = {10.1145/2840728.2840746},
} 

@INPROCEEDINGS{lee2014path,
 author = {Lee, Yin Tat and Sidford, Aaron},
 title = {Path Finding Methods for Linear Programming: Solving Linear Programs in {${\widetilde O}(\sqrt{\mathit{rank}})$} Iterations and Faster Algorithms for Maximum Flow},
 crossref = {pfocs14},
 pages = {424--433},
 doi = {10.1109/FOCS.2014.52},
}

@ARTICLE{ImpaSETH,
 author = {Impagliazzo, Russell and Paturi, Ramamohan},
 title = {On the Complexity of $k$-{SAT}},
 journal = jcss,
 issue_date = {March 2001},
 volume = {62},
 number = {2},
 year = {2001},
 pages = {367--375},
 doi = {10.1006/jcss.2000.1727},
}

@ARTICLE{KT18,
  author    = {Robert Krauthgamer and Ohad Trabelsi},
  title     = {Conditional Lower Bounds for All-Pairs Max-Flow},
  journal   = talg,
  volume    = {14},
  number    = {4},
  pages     = {42:1--42:15},
  year      = {2018},
  doi       = {10.1145/3212510},
}
%
%
@Article{GH61,
        author = {Ralph E. Gomory and Te Chiang Hu},
        title = {Multi-Terminal Network Flows},
        journal = SIAMjournal,
        year = 1961,
        volume = {9},
        number = {4},
        pages = {551-570},
        doi = {10.1137/0109047},
        url = {http://www.jstor.org/stable/2098881},
}


@INPROCEEDINGS{BHKP07,
 author = {Bhalgat, Anand and Hariharan, Ramesh and Kavitha, Telikepalli and Panigrahi, Debmalya},
 title = {An {${\widetilde O}(mn)$} {G}omory--{H}u Tree Construction Algorithm for Unweighted Graphs},
 crossref = {pstoc07},
 pages = {605--614},
 doi = {10.1145/1250790.1250879},
}
%
@ARTICLE{FF56,
  title={Maximal flow through a network},
  author={Ford, Lester R. and Fulkerson, Delbert R.},
  journal= CanadJMath,
  volume={8},
  number={3},
  pages={399--404},
  year={1956},
  doi = {10.4153/CJM-1956-045-5}
}
%
@INPROCEEDINGS{A+18,
  author =	{Amir Abboud and Loukas Georgiadis and Giuseppe F. Italiano and Robert Krauthgamer and Nikos Parotsidis and Ohad Trabelsi and
 Przemys{\l}aw Uzna{\'n}ski and Daniel Wolleb{-}Graf}, 
  title =	{Faster Algorithms for All-Pairs Bounded Min-Cuts},
  crossref =	{picalp19},
  pages =	{7:1--7:15},
  volume =	{132},
  doi =		{10.4230/LIPIcs.ICALP.2019.7},
}
%
@INPROCEEDINGS{G+17,
  author =	{Loukas Georgiadis and Daniel Graf and Giuseppe F. Italiano and Nikos Parotsidis and Przemys{\l}aw Uzna{\'n}ski},
  title =	{All-Pairs 2-Reachability in ${O}(n^\omega\log n)$ Time},
 crossref =     {picalp17},
  pages =	{74:1--74:14},
  volume =	{80},
  doi =		{10.4230/LIPIcs.ICALP.2017.74},
}


@ARTICLE{GH86,
  title={Multi-terminal maximum flows in node-capacitated networks.},
  author={Granot, Frieda and Hassin, Refael},
  journal= discrappmath,
  volume={13},
  number={2-3},
  pages={157--163},
  year={1986},
  doi = {10.1016/0166-218X(86)90079-X},
}

@ARTICLE{HL07, 
 author = {Hassin, Refael and Levin, Asaf},
 title = {Flow Trees for Vertex-capacitated Networks},
 journal =  discrappmath,
 volume = {155},
 number = {4},
 year = {2007},
 pages = {572--578},
 numpages = {7},
 doi = {10.1016/j.dam.2006.08.012},
 publisher = {Elsevier},
} 
%
@ARTICLE{Mayeda60,
  title={Terminal and branch capacity matrices of a communication net},
  author={Mayeda, Wataru},
  journal= IREtct,
  volume={7},
  number={3},
  pages={261--269},
  year={1960},
  publisher={IEEE},
  doi={10.1109/TCT.1960.1086673}, 
}
%
@ARTICLE{Chien60,
  title={Synthesis of a communication net},
  author={Chien, Robert T.},
  journal= IBMjournal,
  volume={4},
  number={3},
  pages={311--320},
  year={1960},
  publisher={IBM},
  doi = {10.1147/rd.43.0311},
}
%
@ARTICLE{GT01,
  title={Cut tree algorithms: an experimental study},
  author={Goldberg, Andrew V. and Tsioutsiouliklis, Kostas},
  journal= JAlgorithms,
  volume={38},
  number={1},
  pages={51--83},
  year={2001},
  doi = {10.1006/jagm.2000.1136},
}
%
@ARTICLE{Gusfield90,
  title={Very simple methods for all pairs network flow analysis},
  author={Gusfield, Dan},
  journal= sicomp,
  volume={19},
  number={1},
  pages={143--155},
  year={1990},
  doi = {10.1137/0219009},
}

@INPROCEEDINGS{HKP07,
  title={Efficient algorithms for computing all low $s-t$ edge connectivities and related problems},
  author={Hariharan, Ramesh and Kavitha, Telikepalli and Panigrahi, Debmalya},
  crossref = {psoda07},
  pages={127--136},
  year={2007},
  note = {\href{http://dl.acm.org/citation.cfm?id=1283383.1283398}{ACM DL}},
}
%
@inproceedings{Edmonds70,
  title={Submodular functions, matroids, and certain polyhedra},
  author={Edmonds, Jack},
booktitle={Combinatorial Structures and Their Appl., Proc. Conf. Calgary 1969},
  publisher = {Gordon and Breach},
  pages={69--87},
  year={1970},
  doi = {10.1007/3-540-36478-1\_2},
}
%
@ARTICLE{Gabow95,
  title={A matroid approach to finding edge connectivity and packing arborescences},
  author={Gabow, Harold N.},
  journal= jcss,
  volume={50},
  number={2},
  pages={259--273},
  year={1995},
  doi = {10.1006/jcss.1995.1022},
  note = {\prelim \href{https:/doi.org/10.1145/103418.103436}{STOC'91}},
}
%
@ARTICLE{WL93,
  title={An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation},
  author={Wu, Zhenyu and Leahy, Richard},
  journal= ACMpattern,
  volume={15},
  number={11},
  pages={1101--1113},
  year={1993},
  doi = {10.1109/34.244673},
}
%
@INPROCEEDINGS{BENW16,
  author    = {Glencora Borradaile and David Eppstein and Amir Nayyeri and
               Christian Wulff{-}Nilsen},
  title     = {All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs},
 crossref  = {pcompgeom16},
  pages     = {22:1--22:16},
  doi  =  {10.4230/LIPIcs.SoCG.2016.22},
  eprint    = {1411.7055},
}
%
@article{AVY15,
  author    = {Amir Abboud and Vassilevska Williams, Virginia and Huacheng Yu},
  title     = {Matching Triangles and Basing Hardness on an Extremely Popular Conjecture},
  journal = sicomp,
  year   =  {2018},
  volume = {47},
  number = {3},
  pages  = {1098--1122},
  doi    = {doi:10.1137/15M1050987},
note = {\prelim \href{https://doi.org/10.1145/2746539.2746594}{STOC'15}},
}
%
@INPROCEEDINGS{AVY15-conf,
  author    = {Amir Abboud and Vassilevska Williams, Virginia and Huacheng Yu},
  title     = {Matching Triangles and Basing Hardness on an Extremely Popular Conjecture},
 crossref   = {pstoc15},
  pages     = {41--50},
  doi  = {10.1145/2746539.2746594},
}



@ARTICLE{CLL13,
  title={Graph connectivities, network coding, and expander graphs},
  author={Cheung, Ho Yee and Lau, Lap Chi and Leung, Kai Man},
  journal= sicomp,
  volume={42},
  number={3},
  pages={733--751},
  year={2013},
  doi={10.1137/110844970},
}
%
@ARTICLE{ACZ98,
author ={Srinivasa Rao Arikati and Shiva Chaudhuri and Christos D. Zaroliagis},
  title     = {All-Pairs Min-Cut in Sparse Networks},
  journal   = JAlgorithms,
  year      = {1998},
  volume    = {29},
  number    = {1},
  pages     = {82--110},
  doi  = {10.1006/jagm.1998.0961},
}
%
@INPROCEEDINGS{LNSW12,
  author    = {Jakub Lacki and Yahav Nussbaum and Piotr Sankowski and
               Wulff-Nilsen, Christian},
  title     = {Single Source -- All Sinks Max Flows in Planar Digraphs},
  crossref = {pfocs12},
  pages     = {599--608},
  doi  = {10.1109/FOCS.2012.66},
}



@ARTICLE{Wil05,
  author    = {R. Ryan Williams},
  title     = {A new algorithm for optimal 2-constraint satisfaction and its implications},
  journal   = tcs,
  volume    = {348},
  number    = {2--3},
  pages     = {357--365},
  year      = {2005},
  doi       = {10.1016/j.tcs.2005.09.023},
}


@INPROCEEDINGS{ABV15,
author = {Amir Abboud and Arturs Backurs and Vassilevska Williams, Virginia},
title={Tight Hardness Results for {LCS} and Other Sequence Similarity Measures},
crossref = {pfocs15},
  pages     = {59--78},
  doi       = {10.1109/FOCS.2015.14},
}

@INPROCEEDINGS{ABDN18,
author  = {Amir Abboud and Karl Bringmann and Holger Dell and Jesper Nederlof},
title={More consequences of falsifying {SETH} and the orthogonal vectors conjecture},
crossref= {pstoc18},
  pages     = {253--266},
  doi       = {10.1145/3188745.3188938},
}
%
@article{GIKW17,
  author    = {Jiawei Gao and Russell Impagliazzo and Antonina Kolokolova and
               R. Ryan Williams},
  title   = {Completeness for First-Order Properties on Sparse Structures with
               Algorithmic Applications},
  journal   = talg,
  volume    = {15},
  year      = {2019},                  
  number    = {2},
  pages     = {1--35},
  doi       = {10.1145/3196275},
note = {\prelim \href{https://doi.org/10.1137/1.9781611974782.141}{SODA'17}},
}

@INPROCEEDINGS{GIKW17-conf,
  author    = {Jiawei Gao and Russell Impagliazzo and Antonina Kolokolova and
               R. Ryan Williams},
  title   = {Completeness for First-Order Properties on Sparse Structures with
               Algorithmic Applications},
 crossref = {psoda17},
  pages     = {2162--2181},
  year      = {2017},
  doi       = {10.1137/1.9781611974782.141},
}

@INPROCEEDINGS{Madry16,
  author    = {Aleksander Madry},
  title     = {Computing Maximum Flow with Augmenting Electrical Flows},
 crossref   = {pfocs16},
  pages     = {593--602},
  doi       = {10.1109/FOCS.2016.70},
}

@ARTICLE{Mayeda62,
author={Wataru Mayeda},
journal= IREtct,
title={On Oriented Communication Nets},
year={1962},
volume={9},
number={3},
pages={261--267},
doi={10.1109/TCT.1962.1086912},
}

@ARTICLE{Jelinek63, 
author={Frederick Jelinek},
journal= IEEEtct,
title={On the Maximum Number of Different Entries in the Terminal Capacity Matrix of Oriented Communication Nets},
year={1963},
volume={10},
number={2},
pages={307-308},
doi={10.1109/TCT.1963.1082149},
}
%
@ARTICLE{Bang-Jensen95,
 author = {{Bang-Jensen}, J{\o}rgen and Frank, Andr{\'a}s and Jackson, Bill},
 title = {Preserving and Increasing Local Edge-Connectivity in Mixed Graphs},
 journal = sidma,
 volume = {8},
 number = {2},
 year = {1995},
 pages = {155--178},
 doi = {10.1137/S0036142993226983},
} 

@INPROCEEDINGS{Cole03,
 author = {Cole, Richard and Hariharan, Ramesh},
 title = {A Fast Algorithm for Computing {S}teiner Edge Connectivity},
crossref = {pstoc03},
 pages = {167--176},
 doi = {10.1145/780542.780568},
} 
%
@INPROCEEDINGS{SidfordT18,
  author    = {Aaron Sidford and Kevin Tian},
  title     = {Coordinate Methods for Accelerating $\ell_{\infty}$ Regression 
  and Faster Approximate Maximum Flow},
crossref  = {pfocs18},
  pages     = {922--933},
  doi = {10.1109/FOCS.2018.00091},
}
%
@article{AnariV18,
  author    = {Nima Anari and Vijay V. Vazirani},
  title     = {Planar Graph Perfect Matching Is in {NC}},
  journal   = jacm,
  year      = {2020},
  volume    = {67},
  number    = {4},
  pages     = {21:1--21:34},
  doi       = {10.1145/3397504},
  note  = {\prelim \href{https://doi.org/10.1109/FOCS.2018.00068}{FOCS'18}}, 
}

@INPROCEEDINGS{AnariV18-conf,
  author    = {Nima Anari and Vijay V. Vazirani},
  title     = {Planar Graph Perfect Matching Is in {NC}},
crossref = {pfocs18},
  pages     = {650--661},
  doi = {10.1109/FOCS.2018.00068}, 
}

@INPROCEEDINGS{LS19,
  author    = {Yang P. Liu and Aaron Sidford},
  title     = {Faster energy maximization for faster maximum flow},
 crossref   = {pstoc20},
  pages     = {803--814},
  doi       = {10.1145/3357713.3384247}
}


@INPROCEEDINGS{AW14,
  author    = {Amir Abboud and Vassilevska Williams, Virginia},
title  = {Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems},
crossref = {pfocs14},
  pages     = {434--443},
  doi       = {10.1109/FOCS.2014.53}
}



@INPROCEEDINGS{conf-version,
  author =	{Amir Abboud and Robert Krauthgamer and Ohad Trabelsi},
  title =	{New Algorithms and Lower Bounds for All-Pairs Max-Flow
                  in Undirected Graphs},
  crossref =	{psoda20},
  pages =	{48--61},
  doi    =      {10.1137/1.9781611975994.4},
  eprint =      {1901.01412},
}
%
@inproceedings{linearflow21,
author = {Brand, Jan van den and Lee, Yin Tat and Liu, Yang P. and Saranurak, Thatchaphol and Sidford, Aaron and Song, Zhao and Wang, Di},
title = {Minimum Cost Flows, {MDPs}, and $\ell_1$-Regression in Nearly Linear Time for Dense Instances},
crossref = {pstoc21},
pages = {859--869},
doi = {10.1145/3406325.3451108},
}

@misc{AKT21_arxiv,
  title={{APMF} < {APSP}? {G}omory--{H}u Tree for Unweighted Graphs in Almost-Quadratic Time},
  author={Abboud, Amir and Krauthgamer, Robert and Trabelsi, Ohad},
  eprint = {2106.02981},
  year={2021},
  note={Accepted to FOCS 2021},
}

@inproceedings{AKT21_stoc,
  author={Abboud, Amir and Krauthgamer, Robert and Trabelsi, Ohad},
  title={Subcubic algorithms for {G}omory--{H}u tree in unweighted graphs},
  crossref = {pstoc21},  
  pages={1725--1737},
  doi = {10.1145/3406325.3451073},
}

@misc{Zhang21,
  title={Faster Cut-Equivalent Trees in Simple Graphs},
  author={Zhang, Tianyi},
  eprint={2106.03305},
  year={2021}
}

@misc{LPS21,
  title={A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs},
  author={Li, Jason and Panigrahi, Debmalya and Saranurak, Thatchaphol},
  eprint={2106.02233},
  year={2021},
  note={Accepted to FOCS 2021},
}
