Monotone separation of logarithmic space from logarithmic depth

DOI10.1006/JCSS.1995.1033MaRDI QIDQ1894451zbMATH OpenOpenAlexFDO

Authors Michelangelo Grigni, Michael Sipser

Publication date 24 July 1995

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/a1b9e8d5758fe9f933d535238221717e2f0a58d6

zbMATH Keywords

monotone bounded fanin circuits

Mathematics Subject Classification ID

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

Recommendations

• Monotone Circuits for Connectivity Have Depth (log n)^2-o(1)
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• scientific article; zbMATH DE number 1263233
• scientific article; zbMATH DE number 176869

Cited in

(9)

• Positive versions of polynomial time
• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
• On derandomized composition of Boolean functions
• Prediction from partial information and hindsight, with application to circuit lower bounds
• Bounds in ontology-based data access via circuit complexity
• scientific article; zbMATH DE number 176869 (Why is no real title available?)
• A super-quadratic lower bound for depth four arithmetic circuits
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• Regular expression length via arithmetic formula complexity

This page was built for publication: Monotone separation of logarithmic space from logarithmic depth

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