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

DOI10.1137/S0097539795285631zbMATH Open0907.68084DBLPjournals/siamcomp/GoldmannH98WikidataQ56959071 ScholiaQ56959071MaRDI QIDQ4210096FDOQ4210096

Authors: Mikael Goldmann, Johan Hastad 

Publication date: 20 September 1998

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

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

zbMATH Keywords

lower boundsconnectivitycircuit complexitymonotone circuits

Mathematics Subject Classification ID

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

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)