Strongly exponential lower bounds for monotone computation
From MaRDI portal
Publication:4978063
DOI10.1145/3055399.3055478zbMath1370.68111OpenAlexW2624730843MaRDI QIDQ4978063
Robert Robere, Toniann Pitassi
Publication date: 17 August 2017
Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3055399.3055478
circuit complexityswitching networksmonotone complexityspan programsformulascomparator circuitsrank method
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (14)
Upslices, downslices, and secret-sharing with complexity of \(1.5^n\) ⋮ Quadratic secret sharing and conditional disclosure of secrets ⋮ Communication Lower Bounds via Critical Block Sensitivity ⋮ Dag-like communication and its applications ⋮ Lower bounds for Boolean circuits of bounded negation width ⋮ Local bounds for the optimal information ratio of secret sharing schemes ⋮ Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) ⋮ Unnamed Item ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Adventures in monotone complexity and TFNP ⋮ Lower Bounds for DeMorgan Circuits of Bounded Negation Width ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets ⋮ Monotone circuit lower bounds from robust sunflowers
This page was built for publication: Strongly exponential lower bounds for monotone computation
