Showing cs.CCShow all
2 papers · 1 filter
cs.CC2024
Supercritical Tradeoffs for Monotone Circuits
Mika Göös, Gilbert Maystre, Kilian Risse +1
We exhibit a monotone function computable by a monotone circuit of quasipolynomial size such that any monotone circuit of polynomial depth requires exponential size. This is the fi…
cs.CC2014
Tree-like resolution complexity of two planar problems
Dmitry Itsykson, Anna Malova, Vsevolod Oparin +1
We consider two CSP problems: the first CSP encodes 2D Sperner's lemma for the standard triangulation of the right triangle on small triangles; the second CSP encodes the fac…