Strongly exponential lower bounds for monotone computation
From MaRDI portal
Publication:4978063
DOI10.1145/3055399.3055478zbMath1370.68111MaRDI 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 complexity; switching networks; monotone complexity; span programs; formulas; comparator circuits; rank method
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Communication Lower Bounds via Critical Block Sensitivity, 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, Query-to-Communication Lifting Using Low-Discrepancy Gadgets, Monotone circuit lower bounds from robust sunflowers, Nullstellensatz size-degree trade-offs from reversible pebbling, Upslices, downslices, and secret-sharing with complexity of \(1.5^n\), Quadratic secret sharing and conditional disclosure of secrets, Dag-like communication and its applications, Local bounds for the optimal information ratio of secret sharing schemes, Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\), Lower bounds for Boolean circuits of bounded negation width
