Randomized feasible interpolation and monotone circuits with a local oracle
From MaRDI portal
Publication:4562441
DOI10.1142/S0219061318500125OpenAlexW3098043201WikidataQ129592975 ScholiaQ129592975MaRDI QIDQ4562441
Publication date: 20 December 2018
Published in: Journal of Mathematical Logic (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1611.08680
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Resolution over linear equations and multilinear proofs
- The monotone circuit complexity of Boolean functions
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Lower bounds for the polynomial calculus
- Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- Several notes on the power of Gomory-Chvátal cuts
- On the weak pigeonhole principle
- FRAGMENTS OF APPROXIMATE COUNTING
- Lower Bounds for Splittings by Linear Combinations
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- Improved Lower Bounds for Tree-Like Resolution over Linear Inequalities
- Interpolation by a Game
- Discretely ordered modules as a first-order extension of the cutting planes proof system
- Monotone circuits for matching require linear depth
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Lower bounds for resolution and cutting plane proofs and monotone computations
- On monotone circuits with local oracles and clique lower bounds
- Pseudorandom Generators in Propositional Proof Complexity
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
This page was built for publication: Randomized feasible interpolation and monotone circuits with a local oracle
