Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR13-128 | 16th September 2013 21:11

A note on semantic cutting planes

RSS-Feed




TR13-128
Authors: Pavel Hrubes
Publication: 16th September 2013 21:15
Downloads: 3905
Keywords: 


Abstract:

We show that the semantic cutting planes proof system has feasible interpolation via monotone real circuits. This gives an exponential lower bound on proof length in the system.

We also pose the following problem: can every multivariate non-decreasing function be expressed as a composition of non-decreasing functions in two variables?



ISSN 1433-8092 | Imprint