Pages that link to "Item:Q687506"

The following pages link to Exponential lower bounds for the pigeonhole principle (Q687506):

Displaying 47 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)
• Exponential lower bounds for the pigeonhole principle (Q687506) (← 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)
• 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)
• Upper bounds on complexity of Frege proofs with limited use of certain schemata (Q2491079) (← 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)
• LA, permutations, and the Hajós calculus (Q2581274) (← links)
• Satisfiability via Smooth Pictures (Q2817998) (← links)
• A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems (Q2944868) (← links)
• Collapsing modular counting in bounded arithmetic and constant depth propositional proofs (Q2944908) (← 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)
• Combinatorics with Definable Sets: Euler Characteristics and Grothendieck Rings (Q4527935) (← links)
• Characterizing Propositional Proofs as Noncommutative Formulas (Q4577770) (← links)
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle (Q4847394) (← links)
• (Q4989407) (← links)
• Reflections on Proof Complexity and Counting Principles (Q5027248) (← links)
• Approximate counting and NP search problems (Q5055313) (← 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)
• (Q5208872) (← 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)
• A new proof of the weak pigeonhole principle (Q5894824) (← links)
• Proof Complexity of Non-classical Logics (Q5894972) (← links)
• Propositional proof complexity (Q6064569) (← links)
• Why Extension-Based Proofs Fail (Q6115415) (← links)