Monotone Circuits for Connectivity Have Depth (log n)2-o(1)

DOI10.1137/S0097539795285631MaRDI QIDQ4210096zbMATH OpenDBLPWikidataFDO

Authors Mikael Goldmann, Johan Hastad

Publication date 20 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

lower boundsconnectivitycircuit complexitymonotone circuits

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1263233
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Monotone circuits for matching require linear depth
• Formulas vs. circuits for small distance connectivity
• Improved depth lower bounds for small distance connectivity

Cited in

(6)

• Formulas vs. circuits for small distance connectivity
• Lower bounds for tropical circuits and dynamic programs
• Monotone separation of logarithmic space from logarithmic depth
• A simple lower bound for monotone clique using a communication game
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Near-optimal small-depth lower bounds for small distance connectivity

This page was built for publication: Monotone Circuits for Connectivity Have Depth (log n)^2-o(1)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210096)