Pages that link to "Item:Q4847394"

The following pages link to An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle (Q4847394):

Displaying 33 items.

• Towards NP-P via proof complexity and search (Q408544) (← links)
• Lifting lower bounds for tree-like proofs (Q475337) (← links)
• A note on propositional proof complexity of some Ramsey-type statements (Q627444) (← links)
• Algebraic proofs over noncommutative formulas (Q642520) (← links)
• Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem (Q647334) (← links)
• On meta complexity of propositional formulas and propositional proofs (Q937212) (← links)
• Simplified lower bounds for propositional proofs (Q1374208) (← links)
• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting (Q1377580) (← links)
• \(\text{Count}(q)\) does not imply \(\text{Count}(p)\) (Q1377601) (← links)
• Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms (Q1401230) (← links)
• Algebraic proof systems over formulas. (Q1401356) (← links)
• Some remarks on lengths of propositional proofs (Q1908815) (← links)
• An exponential separation between the parity principle and the pigeonhole principle (Q1923563) (← links)
• Resolution with counting: dag-like lower bounds and different moduli (Q2029775) (← links)
• Bounded-depth Frege complexity of Tseitin formulas for all graphs (Q2084956) (← links)
• Partially definable forcing and bounded arithmetic (Q2257103) (← links)
• On transformations of constant depth propositional proofs (Q2311211) (← links)
• Random resolution refutations (Q2311546) (← links)
• Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies (Q2500481) (← links)
• Separation results for the size of constant-depth propositional proofs (Q2566064) (← links)
• Satisfiability via Smooth Pictures (Q2817998) (← links)
• A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems (Q2944868) (← links)
• Parameterized Bounded-Depth Frege Is Not Optimal (Q3012838) (← links)
• An unexpected separation result in Linearly Bounded Arithmetic (Q4666949) (← links)
• (Q5077146) (← links)
• Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs (Q5092411) (← links)
• (Q5136303) (← links)
• Where pigeonhole principles meet Koenig lemmas (Q5158115) (← links)
• Approximate Euler characteristic, dimension, and weak pigeonhole principles (Q5311719) (← links)
• The Complexity of Propositional Proofs (Q5444711) (← links)
• LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE (Q5501765) (← links)
• (Q5875501) (← links)
• Propositional proof complexity (Q6064569) (← links)