On the Width of Semialgebraic Proofs and Algorithms

References

• Alekhnovich M, Razborov A (2003) Lower bounds for the polynomial calculus: Non-binomial case. Proc. Steklov Institute Math. 242:18–35.Google Scholar
• Alekhnovich M, Arora S, Tourlakis I (2011) Toward strong nonapproximability results in the Lovász-Schrijver hierarchy. Computational Complexity 20(4):615–648.Crossref, Google Scholar
• Alekhnovich M, Ben-Sasson E, Razborov A, Wigderson A (2004) Pseudorandom generators in propositional proof complexity. SIAM J. Comput. 34(1):67–88.Crossref, Google Scholar
• Ash R (1990) Information Theory (Dover Publications, Mineola, NY).Google Scholar
• Barak B, Steurer D (2014) Sum-of-squares proofs and the quest toward optimal algorithms. Jang SY, Kim YR, Lee D-W, Yie I, eds. Proc. Internat. Congress Math. ICM, Vol. IV (Kyung Moon SA, Seoul, Korea), 509–533.Google Scholar
• Bassalygo LA (1981) Asymptotically optimal switching circuits. Problems Inform. Transmission 17(3):206–211.Google Scholar
• Ben-Sasson E, Wigderson A (2001) Short proofs are narrow—Resolution made simple. J. ACM 48(2):149–169.Crossref, Google Scholar
• Bollobás B (1980) A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Eur. J. Combinatorics 1(4):311–316.Crossref, Google Scholar
• Bollobás B (1985) Random Graphs (Academic Press, London).Google Scholar
• Bollobás B (1988) The isoperimetric number of random regular graphs. Eur. J. Combinatorics 9(3):241–244.Crossref, Google Scholar
• Buss S, Grigoriev D, Impagliazzo R, Pitassi T (2001) Linear gaps between degrees for the Polynomial Calculus modulo distinct primes. J. Comput. System Sci. 62(2):267–289.Crossref, Google Scholar
• Chvátal V (1973) Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. 4(4):305–337.Crossref, Google Scholar
• Chvátal V, Szemerédi E (1988) Many hard examples for resolution. J. ACM 35(4):759–768.Crossref, Google Scholar
• Cook W, Coullard CR, Turán G (1987) On the complexity of cutting plane proofs. Discrete Appl. Math. 18(1):25–38.Crossref, Google Scholar
• Dash S (2005) Exponential lower bounds on the lengths of some classes of branch-and-cut proofs. Math. Oper. Res. 30(3):678–700.Link, Google Scholar
• Dey SS, Molinaro M, Wang Q (2015) Approximating polyhedra with sparse inequalities. Math. Programming, Ser. B 154(1):329–352.Crossref, Google Scholar
• Edmonds J (1965) Maximum matching and a polyhedron with 0,1-vertices. J. Res. National Bureau of Standards 69(1–2):125–130.Crossref, Google Scholar
• Eisenbrand F, Schulz A (2003) Bounds on the Chvátal rank of polytopes in the 0-1 cube. Combinatorica 23(2):245–261.Crossref, Google Scholar
• Goemans M, Tuncel L (2001) When does the positive semidefiniteness constraint help in lifting procedures. Math. Oper. Res. 26(4):796–815.Link, Google Scholar
• Gomory RE (1963) An algorithm for integer solutions of linear programs. Recent Advances in Mathematical Programming (McGraw-Hill, New York), 269–302.Google Scholar
• Grigoriev DY, Hirsch EA, Pasechnik DV (2002) Complexity of semi-algebraic proofs. Moscow Math. J. 2(4):647–679.Crossref, Google Scholar
• Hoeffding W (1963) Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58(301):13–30.Crossref, Google Scholar
• Impagliazzo R, Pitassi T, Urquhart A (1994) Upper and lower bounds for tree-like cutting planes proofs. Proc. 9th Ann. IEEE Symp. Logic Comput. Sci., LICS ’94 (IEEE Computer Society, Washington, DC), 220–228.Crossref, Google Scholar
• Jukna S (2012) Boolean Function Complexity: Advances and Frontiers (Springer, Berlin).Crossref, Google Scholar
• Lasserre J (2001) Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3):796–817.Crossref, Google Scholar
• Lee JR, Raghavendra P, Steurer D (2015) Lower bounds on the size of semidefinite programming relaxations. Servedio RA, Rubinfeld R, eds. Proc. 47th Annual ACM Sympos. Theory Comput., STOC ’15 (ACM, New York), 567–576.Crossref, Google Scholar
• Lovász L, Plummer MD (2009) Matching Theory (AMS Chelsea Publishing, Providence, RI).Crossref, Google Scholar
• Lovász L, Schrijver A (1991) Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1(2):166–190.Crossref, Google Scholar
• Mathieu C, Sinclair A (2009) Sherali-Adams relaxations of the matching polytope. Mitzenmacher M, ed. Proc. 41st ACM Sympos. Theory Comput., STOC ’09 (ACM, New York), 293–302.Crossref, Google Scholar
• Nordström J (2013) Pebble games, proof complexity and time-space trade-offs. Logical Methods Comput. Sci. 9(3):15:1–15:63.Crossref, Google Scholar
• Pinsker M (1973) On the complexity of a concentrator. 7th Internat. Teletraffic Conf., Stockholm, 318/1–318/4.Google Scholar
• Pudlák P (1997) Lower bounds for resolution and cutting planes proofs and monotone computations. J. Symbolic Logic 62(3):981–998.Crossref, Google Scholar
• Pudlák P (1999) On the complexity of propositional calculus. Cooper SB, Truss JK, eds. Sets and Proofs. London Mathematical Society Lecture Note Series, Vol. 258 (Cambridge University Press, Cambridge, UK), 197–218.Crossref, Google Scholar
• Razborov A (2016) A new kind of tradeoffs in propositional proof complexity. J. ACM 63(2):Article 16.Crossref, Google Scholar
• Schoenebeck G (2008) Linear level Lasserre lower bounds for certain k-CSPs. Proc. 49th IEEE Sympos. Foundations Comput. Sci., FOCS ’08 (IEEE Computer Society, Washington, DC), 593–602.Crossref, Google Scholar
• Schoenebeck G, Trevisan L, Tulsiani M (2007) A linear round lower bound for lovász-schrijver LP relaxations of Vertex Cover and Max Cut. Johnson DS, Feige U, eds. Proc. 39th ACM Sympos. Theory Comput., STOC ’07 (ACM, New York), 302–310.Crossref, Google Scholar
• Schrijver A (1980) On cutting planes. Ann. Discrete Math. 9:291–296.Crossref, Google Scholar
• Tulsiani M (2009) CSP gaps and reductions in the Lasserre hierarchy. Mitzenmacher M, ed. Proc. 41st ACM Sympos. Theory of Comput., STOC ’09 (ACM, New York), 303–312.Crossref, Google Scholar
• Wormald NC (1999) Models of random regular graphs. Lamb JD, Preece DA, eds. Surveys in Combinatorics. London Mathematical Society Lecture Note Series, Vol. 267 (Cambridge University Press, Cambridge, UK), 239–298.Crossref, Google Scholar