Monotone circuit lower bounds from resolution
From MaRDI portal
(Redirected from Publication:5230347)
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
- On the relative complexity of resolution refinements and cutting planes proof systems
- Lower bounds for cutting planes proofs with small coefficients
Cited in
(20)- Large clique is hard on average for resolution
- Hardness amplification in proof complexity
- Proofs with monotone cuts
- Lower bounds for monotone counting circuits
- Monotone circuits for matching require linear depth
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Randomized feasible interpolation and monotone circuits with a local oracle
- A conditional superpolynomial lower bound for extended resolution
- Reflections on Proof Complexity and Counting Principles
- Adventures in monotone complexity and TFNP
- Lifting Theorems for Equality
- Query-to-communication lifting for BPP using inner product
- Short Proofs Are Hard to Find
- Resolution lower bounds for refutation statements
- Monotone circuit lower bounds from resolution
- Query-to-communication lifting using low-discrepancy gadgets
- Monotone circuit lower bounds from robust sunflowers
- From proof complexity to circuit complexity via interactive protocols
- Pseudo-deterministic query complexity of search problems
- Lifting to randomized parity decision trees
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 Q5230347)
