Strongly exponential lower bounds for monotone computation

DOI10.1145/3055399.3055478MaRDI QIDQ4978063zbMATH OpenOpenAlexFDO

Authors Toniann Pitassi, Robert Robere

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

zbMATH Keywords

circuit complexitycomparator circuitsformulasmonotone complexityrank methodspan programsswitching networks

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Higher lower bounds on monotone size
• An exponential lower bound for the size of monotone real circuits
• Superpolynomial lower bounds for monotone span programs
• Lower bounds for monotone span programs
• Combinatorics of monotone computations

Cited in

(32)

• An exponential lower bound for the size of monotone real circuits
• Better lower bounds for monotone threshold formulas
• Nullstellensatz size-degree trade-offs from reversible pebbling
• Upslices, downslices, and secret-sharing with complexity of 1.5ⁿ
• Quadratic secret sharing and conditional disclosure of secrets
• On \(\epsilon\)-sensitive monotone computations
• 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
• Higher lower bounds on monotone size
• Communication lower bounds via critical block sensitivity
• A lower bound for monotone perceptrons
• A \(\mathrm{ZPP}^{\mathrm{NP}[1]}\) lifting theorem
• Adventures in monotone complexity and TFNP
• Lower Bounds for DeMorgan Circuits of Bounded Negation Width
• Nullstellensatz size-degree trade-offs from reversible pebbling
• Tight bounds for monotone switching networks via Fourier analysis
• Query-to-communication lifting using low-discrepancy gadgets
• Strongly Exponential Separation between Monotone VP and Monotone VNP
• Monotone circuit lower bounds from robust sunflowers
• Monotone circuit lower bounds from robust sunflowers
• The strongest model of computation obeying 0-1 Principles
• Succinct computational secret sharing
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
• Fully anonymous secret sharing
• On protocols for monotone feasible interpolation
• Strength and limitations of Sherali-Adams and nullstellensatz proof systems
• Shrinkage under random projections, and cubic formula lower bounds for AC^0 (extended abstract)
• Simplified PIR and CDS protocols and improved linear secret-sharing schemes
• Some recent advancements in monotone circuit complexity (invited talk)

This page was built for publication: Strongly exponential lower bounds for monotone computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978063)