Monotone Projection Lower Bounds from Extended Formulation Lower Bounds

by Joshua A. Grochow

Theory of Computing, Volume 13(18), pp. 1-15, 2017

Bibliography with links to cited articles

[1]   Scott Aaronson: A linear-optical proof that the permanent is #P-hard. Proc. Royal Soc. London A, 467(2136):3393–3405, 2011. [doi:10.1098/rspa.2011.0232, arXiv:1109.1674]

[2]   Scott Aaronson and Alex Arkhipov: The computational complexity of linear optics. Theory of Computing, 9(4):143–252, 2013. Preliminary version in STOC’11. [doi:10.4086/toc.2013.v009a004, arXiv:1011.3245]

[3]   Amir Ben-Dor and Shai Halevi: Zero-one permanent is #P-complete, a simpler proof. In Proc. 2nd Israeli Symp. on Theory and Computing Systems. IEEE Comp. Soc. Press, 1993. [doi:10.1109/ISTCS.1993.253457]

[4]   Peter Bürgisser: On the structure of Valiant’s complexity classes. Discr. Math. & Theoret. Comput. Sci., 3(3):73–94, 1999. HAL. Preliminary version in STACS’98.

[5]   Peter Bürgisser: Completeness and Reduction in Algebraic Complexity Theory. Volume 7 of Algorithms and Computation in Mathematics. Springer, 2000. [doi:10.1007/978-3-662-04179-6]

[6]   Jack Edmonds: Paths, trees, and flowers. Canad. J. Math., 17:449–467, 1965. [doi:10.4153/CJM-1965-045-4]

[7]   Stephen A. Fenner, Rohit Gurjar, and Thomas Thierauf: Bipartite perfect matching is in quasi-NC. In Proc. 48th STOC, pp. 754–763. ACM Press, 2016. [doi:10.1145/2897518.2897564, arXiv:1601.06319]

[8]   Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf: Exponential lower bounds for polytopes in combinatorial optimization. J. ACM, 62(2):17:1–23, 2015. Preliminary version in STOC’12. [doi:10.1145/2716307, arXiv:1111.0837]

[9]   Joshua A. Grochow: Monotone projection lower bounds from extended formulation lower bounds, 2015. ECCC TR15-171. [arXiv:1510.08417]

[10]   Joshua A. Grochow, Ketan D. Mulmuley, and Youming Qiao: Boundaries of VP and VNP. In Proc. 43rd Internat. Colloq. on Automata, Languages and Programming (ICALP’16), pp. 34:1–34:14. Springer, 2016. [doi:10.4230/LIPIcs.ICALP.2016.34, arXiv:1605.02815]

[11]   Mark Jerrum and Marc Snir: Some exact complexity results for straight-line computations over semirings. J. ACM, 29(3):874–897, 1982. [doi:10.1145/322326.322341]

[12]   Stasys Jukna: Why is Hamilton cycle so different from permanent? StackExchange, 2014.

[13]   Stasys Jukna: Lower bounds for monotone counting circuits. Discr. Appl. Math., 213:139–152, 2016. Preliminary version in ECCC TR14-169. [doi:10.1016/j.dam.2016.04.024, arXiv:1502.01865]

[14]   Jacobus H. van Lint and Richard M. Wilson: A Course in Combinatorics. Cambridge Univ. Press, 2001.

[15]   Meena Mahajan and Nitin Saurabh: Some complete and intermediate polynomials in algebraic complexity theory. In Proc. 11th Comput. Sci. Symp. in Russia (CSR’16), pp. 251–265. Springer, 2016. Full version available at ECCC TR16-038. [doi:10.1007/978-3-319-34171-2_18, arXiv:1603.04606]

[16]   Silvio Micali and Vijay V. Vazirani: An O(sqrt(| V| ) | E| ) algorithm for finding maximum matching in general graphs. In Proc. 12th STOC, pp. 17–27. ACM Press, 1980. [doi:10.1109/SFCS.1980.12]

[17]   Henryk Minc: Permanents. Cambridge Univ. Press, 1984.

[18]   Thomas Muir and William H. Metzler: A Treatise on the Theory of Determinants. Dover, 1960.

[19]   Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani: Matching is as easy as matrix inversion. Combinatorica, 7(1):105–113, 1987. Preliminary version in STOC’87. [doi:10.1007/BF02579206]

[20]   Alexander A. Razborov: Lower bounds on monotone complexity of the logical permanent function. Math. Notes, 37(6):485–493, 1985. [doi:10.1007/BF01157687]

[21]   Alexander A. Razborov: Lower bounds for deterministic and nondeterministic branching programs. In Fundamentals of Computation Theory (FCT’91), volume 529 of LNCS, pp. 47–60. Springer, 1991. [doi:10.1007/3-540-54458-5_49]

[22]   Thomas Rothvoß: The matching polytope has exponential extension complexity. J. ACM, 64(6):41:1–19, 2017. Preliminary version in STOC’14. [doi:10.1145/3127497, arXiv:1311.2369]

[23]   Nicolas de Rugy-Altherre: A dichotomy theorem for homomorphism polynomials. In Proc. 37th Internat. Symp. Math. Found. Comput. Sci. (MFCS’12), pp. 308–322. Springer, 2012. [doi:10.1007/978-3-642-32589-2_29, arXiv:1210.7641]

[24]   Claus-Peter Schnorr: A lower bound on the number of additions in monotone computations. Theoret. Comput. Sci., 2(3):305–315, 1976. [doi:10.1016/0304-3975(76)90083-9]

[25]   Alexander Schrijver: Combinatorial optimization. Polyhedra and efficiency. Vol. A. Volume 24 of Algorithms and Combinatorics. Springer, 2003. Chapters 1–38.

[26]   Volker Strassen: Vermeidung von Divisionen. J. Reine Angew. Math., 1973(264):184–202, 1973. [doi:10.1515/crll.1973.264.184]

[27]   Ola Svensson and Jakub Tarnawski: The matching problem in general graphs is in quasi-NC. In Proc. 58th FOCS, pp. 696–707. IEEE Comp. Soc. Press, 2017. [doi:10.1109/FOCS.2017.70, arXiv:1704.01929]

[28]   Leslie G. Valiant: Completeness classes in algebra. In Proc. 11th STOC, pp. 249–261. ACM Press, 1979. [doi:10.1145/800135.804419]

[29]    Leslie G. Valiant: The complexity of computing the permanent. Theoret. Comput. Sci., 8(2):189–201, 1979. [doi:10.1016/0304-3975(79)90044-6]

[30]   Leslie G. Valiant: Negation can be exponentially powerful. Theoret. Comput. Sci., 12(3):303–314, 1980. Preliminary version in STOC’79. [doi:10.1016/0304-3975(80)90060-2]

[31]   Leslie G. Valiant, Sven Skyum, Stuart Berkowitz, and Charles Rackoff: Fast parallel computation of polynomials using few processors. SIAM J. Comput., 12(4):641–644, 1983. Preliminary version in MFCS’81. [doi:10.1137/0212043]

[32]   Vijay V. Vazirani: A simplification of the MV matching algorithm and its proof, 2013. [arXiv:1210.4594]

[33]   Tzu-Chieh Wei and Simone Severini: Matrix permanent and quantum entanglement of permutation invariant states. J. Math. Phys., 51(9), 2010. [doi:10.1063/1.3464263, arXiv:0905.0012]

[34]   Mihalis Yannakakis: Expressing combinatorial optimization problems by linear programs. J. Comput. System Sci., 43(3):441–466, 1991. Preliminary version in STOC’88. [doi:10.1016/0022-0000(91)90024-Y]