Monotone separation of logarithmic space from logarithmic depth

DOI10.1006/jcss.1995.1033zbMath0837.68030OpenAlexW2077946919MaRDI QIDQ1894451

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)

Related Items (8)

Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity ⋮ Bounds in ontology-based data access via circuit complexity ⋮ On derandomized composition of Boolean functions ⋮ Optimal Lower Bounds on Regular Expression Size Using Communication Complexity ⋮ Regular expression length via arithmetic formula complexity ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Prediction from partial information and hindsight, with application to circuit lower bounds ⋮ Positive versions of polynomial time

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