Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR97-032 | 11th July 1997 00:00

Lower Bounds for Monotone Real Circuit Depth and Formula Size and Tree-like Cutting Planes

RSS-Feed




TR97-032
Authors: Jan Johannsen
Publication: 10th September 1997 21:07
Downloads: 972
Keywords: 


Abstract:

Using a notion of real communication complexity recently
introduced by J. Krajicek, we prove a lower bound on the depth of
monotone real circuits and the size of monotone real formulas for
st-connectivity. This implies a super-polynomial speed-up of dag-like
over tree-like Cutting Planes proofs.



ISSN 1433-8092 | Imprint