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):

Displayed 30 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)
• Partially definable forcing and bounded arithmetic (Q2257103) ‎ (← 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)
• A form of feasible interpolation for constant depth Frege systems (Q3570172) ‎ (← links)
• On the correspondence between arithmetic theories and propositional proof systems – a survey (Q3619867) ‎ (← links)
• Witnessing functions in bounded arithmetic and search problems (Q4227882) ‎ (← links)
• Forcing in Finite Structures (Q4351930) ‎ (← links)
• Combinatorics with Definable Sets: Euler Characteristics and Grothendieck Rings (Q4527935) ‎ (← links)
• An unexpected separation result in Linearly Bounded Arithmetic (Q4666949) ‎ (← 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)
• A new proof of the weak pigeonhole principle (Q5894824) ‎ (← links)
• Proof Complexity of Non-classical Logics (Q5894972) ‎ (← links)