Document Open Access Logo

Semantic Versus Syntactic Cutting Planes

Authors Yuval Filmus, Pavel Hrubeš, Massimo Lauria

PDF
Thumbnail PDF

File

LIPIcs.STACS.2016.35.pdf
  • Filesize: 0.63 MB
  • 13 pages

Document Identifiers

Author Details

Yuval Filmus
Pavel Hrubeš
Massimo Lauria

Cite As Get BibTex

Yuval Filmus, Pavel Hrubeš, and Massimo Lauria. Semantic Versus Syntactic Cutting Planes. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 35:1-35:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.STACS.2016.35

Abstract

In this paper, we compare the strength of the semantic and syntactic version of the cutting planes proof system.

First, we show that the lower bound technique of Pudlák applies also to semantic cutting planes: the proof system has feasible interpolation via monotone real circuits, which gives an exponential lower bound on lengths of semantic cutting planes refutations.

Second, we show that semantic refutations are stronger than syntactic ones. In particular, we give a formula for which any refutation in syntactic cutting planes requires exponential length, while there is a polynomial length refutation in semantic cutting planes. In other words, syntactic cutting planes does not p-simulate semantic cutting planes. We also give two incompatible integer inequalities which require exponential length refutation in syntactic cutting planes.

Finally, we pose the following problem, which arises in connection with semantic inference of arity larger than two: can every multivariate non-decreasing real function be expressed as a composition of non-decreasing real functions in two variables?

Subject Classification

Keywords
  • proof complexity
  • cutting planes
  • lower bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Shigeo Akashi and Satoshi Kodama. A version of Hilbert’s 13th problem for infinitely differentiable functions. Fixed point theory and applications, 2010. Google Scholar
  2. Vladimir N. Arnold. On functions of three variables. Doklady Akad. Nauk SSSR, 114:679-681, 1957. Google Scholar
  3. Paul Beame, Toniann Pitassi, and Nathan Segerlind. Lower bounds for Lovász-Schrijver systems and beyond follow from multiparty communication complexity. SIAM J. Comput., 37(3):845-869, June 2007. Google Scholar
  4. Maria Luisa Bonet, Toniann Pitassi, and Ran Raz. Lower bounds for cutting planes proofs with small coefficients. The Journal of Symbolic Logic, 62(3):708-728, 1997. URL: http://www.jstor.org/stable/2275569.
  5. Samuel R. Buss and Peter Clote. Cutting planes, connectivity, and threshold logic. Archive for Mathematical Logic, 35(1):33-62, 1996. Google Scholar
  6. Arkadev Chattopadhyay and Anil Ada. Multiparty communication complexity of disjointness. Electronic Colloquium on Computational Complexity (ECCC), 15:2, 208. Google Scholar
  7. Vašek Chvátal. Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Mathematics, 4(4):305-337, 1973. Google Scholar
  8. Vašek Chvátal, William Cook, and Mark Hartmann. On cutting-plane proofs in combinatorial optimization. Linear Algebra and its Applications, 114:455-499, 1989. Google Scholar
  9. Stephen A. Cook and Robert A. Reckhow. The relative efficiency of propositional proof systems. Journal of Symbolic Logic, 44:36-50, 1979. Google Scholar
  10. William Cook, Collette R. Coullard, and György Turán. On the complexity of cutting-plane proofs. Discrete Applied Mathematics, 18(1):25-38, 1987. Google Scholar
  11. Friederich Eisenbrand and Andreas S. Schulz. Bounds on the Chvátal rank of polytopes in the 0/1-cube. Integer Programming and Combinatorial Optimization, pages 137-150, 1999. Google Scholar
  12. Yuval Filmus and Massimo Lauria. A separation between semantic and syntactic cutting planes. Manuscript, 2013. Google Scholar
  13. Ralph E. Gomory. Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5):275-278, 1958. Google Scholar
  14. Pavel Hrubeš. A note on semantic cutting planes. Electronic Colloquium on Computational Complexity (ECCC), 20:128, 2013. URL: http://eccc.hpi-web.de/report/2013/128.
  15. Russell Impagliazzo, Toniann Pitassi, and Alasdair Urquhart. Upper and lower bounds for tree-like cutting planes proofs. In Logic in Computer Science, 1994. LICS'94. Proceedings., Symposium on, pages 220-228. IEEE, 1994. Google Scholar
  16. Stasys Jukna. Boolean Function Complexity: Advances and Frontiers. Springer-Verlag, 2012. Google Scholar
  17. Andrey N. Kolmogorov. On the representations of continuous functions of several variables by superpositions of continuous functions of fewer variables. Doklady Akad. Nauk SSSR, 108:179-182, 1956. Google Scholar
  18. Jan Krajíček. Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic. Journal of Symbolic Logic, 62(2):457-486, 1997. Google Scholar
  19. Jan Krajíček. Interpolation and approximate semantic derivations. Mathematical Logic Quarterly, 48(4):602-606, 2002. Google Scholar
  20. Troy Lee and Adi Shraibman. Disjointness is hard in the multi-party number-on-the-forehead model. 2012 IEEE 27th Conference on Computational Complexity, 0:81-91, 2008. URL: http://dx.doi.org/http://doi.ieeecomputersociety.org/10.1109/CCC.2008.29.
  21. G. G. Lorentz. Approximations of functions. Holt, Rinehart and Winston, New York, 1966. Google Scholar
  22. Saburo Muroga, Iwao Toda, and Satoru Takasu. Theory of majority decision elements. Journal of the Franklin Institute, 271(5):376-418, 1961. Google Scholar
  23. Pavel Pudlák. Lower bounds for Resolution and Cutting Plane proofs and monotone computations. Journal of Symbolic Logic, 62(3):981-998, 1997. Google Scholar
  24. Alexander A. Razborov. Lower bounds on the monotone complexity of some Boolean functions. Doklady Akad. Nauk SSSR, 282:1033-1037, 1985. Google Scholar
  25. Martin Rhodes. On the Chvátal rank of the pigeonhole principle. Theoretical Computer Science, 410(27-29):2774-2778, 2009. Google Scholar
  26. Alexander A. Sherstov. The multiparty communication complexity of set disjointness. In STOC, pages 525-548, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact