Separation of the monotone NC hierarchy

DOI10.1007/s004930050062zbMath0977.68037OpenAlexW3022335368WikidataQ30054697 ScholiaQ30054697MaRDI QIDQ1977414

Ran Raz, Pierre McKenzie

Publication date: 14 May 2000

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s004930050062

zbMATH Keywords

monotone circuitscommunication complexitymonotone-NC

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Discrete mathematics in relation to computer science (68R99)

Related Items (38)

Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes ⋮ The Range of Topological Effects on Communication ⋮ Cumulative Space in Black-White Pebbling and Resolution ⋮ Communication Lower Bounds via Critical Block Sensitivity ⋮ Communication complexity of approximate Nash equilibria ⋮ Deterministic Communication vs. Partition Number ⋮ Reversible Pebble Game on Trees ⋮ Dag-like communication and its applications ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On differential privacy and adaptive data analysis with bounded space ⋮ Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) ⋮ Structure of Protocols for XOR Functions ⋮ Query-to-Communication Lifting for BPP ⋮ The depth of resolution proofs ⋮ Incremental branching programs ⋮ From Expanders to Hitting Distributions and Simulation Theorems ⋮ The direct sum of universal relations ⋮ Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Simulation theorems via pseudo-random properties ⋮ On derandomized composition of Boolean functions ⋮ Reversible pebble games and the relation between tree-like and general resolution space ⋮ Rectangles Are Nonnegative Juntas ⋮ Nondeterministic and randomized Boolean hierarchies in communication complexity ⋮ Unnamed Item ⋮ Adventures in monotone complexity and TFNP ⋮ Lifting Theorems for Equality ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Query-To-Communication Lifting for BPP Using Inner Product ⋮ Non-cancellative Boolean circuits: A generalization of monotone boolean circuits ⋮ Unnamed Item ⋮ Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets ⋮ A Lifting Theorem with Applications to Symmetric Functions ⋮ The expressiveness of DAC ⋮ Large clique is hard on average for resolution

This page was built for publication: Separation of the monotone NC hierarchy