Monotone circuit lower bounds from resolution
From MaRDI portal
(Redirected from Publication:5140848)
Monotone circuit lower bounds from resolution (scientific article; zbMATH DE number 7286923)
Monotone circuit lower bounds from resolution (scientific article; zbMATH DE number 7286923)
Recommendations
- Monotone circuit lower bounds from resolution
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes
- Combinatorics of monotone computations
- An exponential lower bound for the size of monotone real circuits
Cites work
- A characterization of span program size and improved lower bounds for monotone span programs
- A combinatorial characterization of resolution width
- A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
- A new kind of tradeoffs in propositional proof complexity
- A note on monotone real circuits
- An exponential lower bound for the size of monotone real circuits
- Boolean function complexity. Advances and frontiers.
- Communication Complexity
- Communication Complexity
- Communication lower bounds via critical block sensitivity
- Dag-like communication and its applications
- Deterministic communication vs. partition number
- Discretely ordered modules as a first-order extension of the cutting planes proof system
- Hard examples for resolution
- scientific article; zbMATH DE number 4008289 (Why is no real title available?)
- scientific article; zbMATH DE number 1261805 (Why is no real title available?)
- scientific article; zbMATH DE number 524142 (Why is no real title available?)
- scientific article; zbMATH DE number 3999837 (Why is no real title available?)
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Lower bounds for cutting planes proofs with small coefficients
- Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Monotone circuit lower bounds from resolution
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- On the bottleneck counting argument
- On the complexity of cutting-plane proofs
- On the virtue of succinct proofs
- Proofs as Games
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- Query-to-communication lifting for BPP
- Rectangles are nonnegative juntas
- Resolution over linear equations and multilinear proofs
- Search Problems in the Decision Tree Model
- Separation of the monotone NC hierarchy
- Short proofs are narrow—resolution made simple
- Simulation theorems via pseudo-random properties
- Symmetric approximation arguments for monotone lower bounds without sunflowers
- The gap between monotone and non-monotone circuit complexity is exponential
- The monotone circuit complexity of Boolean functions
- The monotone complexity of \(k\)-clique on random graphs
- The Potential of the Approximation Method
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
Cited in
(19)- Lower bounds for monotone counting circuits
- Monotone circuits for matching require linear depth
- Communication lower bounds via critical block sensitivity
- A conditional superpolynomial lower bound for extended resolution
- Monotone circuit lower bounds from resolution
- Monotone circuit lower bounds from robust sunflowers
- Randomized versus deterministic decision tree size
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Cutting planes width and the complexity of graph isomorphism refutations
- Exponential separation between powers of regular and general resolution over parities
- Lifting dichotomies
- Lifting dichotomies
- Proving unsatisfiability with hitting formulas
- Catalytic branching programs from groups and general protocols
- On protocols for monotone feasible interpolation
- Some recent advancements in monotone circuit complexity (invited talk)
- On the power and limitations of branch and cut
- Secret sharing, slice formulas, and monotone real circuits
- Searching for falsified clause in random ( n)-CNFs is hard for randomized communication
This page was built for publication: Monotone circuit lower bounds from resolution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5140848)
