Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits

DOI10.1051/ita:2001120zbMath1052.68053OpenAlexW2163595083MaRDI QIDQ2773024

Jan Johannsen

Publication date: 2001

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2001__35_3_277_0

zbMATH Keywords

Boolean functionscommunication complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Deterministic Communication vs. Partition Number ⋮ Unnamed Item ⋮ Simulation theorems via pseudo-random properties

Cites Work

• Properties that characterize LOGCFL
• Separation of the monotone NC hierarchy
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Two Applications of Inductive Counting for Complementation Problems
• Communication Complexity
• Unnamed Item

This page was built for publication: Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits