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)

Full work available at URL https://doi.org/10.1137/S0097539795285631

zbMATH Keywords

circuit complexityconnectivitylower boundsmonotone 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

(8)

• A simple lower bound for monotone clique using a communication game
• Improved depth lower bounds for small distance connectivity
• Monotone separation of logarithmic space from logarithmic depth
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• scientific article; zbMATH DE number 1263233 (Why is no real title available?)
• Lower bounds for tropical circuits and dynamic programs
• Formulas vs. circuits for small distance connectivity
• 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)