Monotone Projection Lower Bounds from Extended Formulation Lower Bounds
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]