The following pages link to On the weak pigeonhole principle (Q2773242):
Displaying 50 items.
- The limits of tractability in resolution-based propositional proof systems (Q408157) (← links)
- Towards NP-P via proof complexity and search (Q408544) (← links)
- Lower bounds for \(k\)-DNF resolution on random 3-CNFs (Q430840) (← links)
- A lower bound on the size of resolution proofs of the Ramsey theorem (Q436623) (← links)
- A note on propositional proof complexity of some Ramsey-type statements (Q627444) (← links)
- On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography (Q693058) (← links)
- Short propositional refutations for dense random 3CNF formulas (Q741088) (← links)
- Spines of random constraint satisfaction problems: definition and connection with computational complexity (Q812393) (← links)
- Substitutions into propositional tautologies (Q845921) (← links)
- Short proofs of the pigeonhole formulas based on the connection method (Q915494) (← links)
- Resolution over linear equations and multilinear proofs (Q952492) (← links)
- The complexity of the pigeonhole principle (Q1343166) (← links)
- Count\((q)\) versus the pigeon-hole principle (Q1360313) (← links)
- A note about \(k\)-DNF resolution (Q1641156) (← links)
- Reductions in \textbf{PPP} (Q1730025) (← links)
- A model-theoretic characterization of the weak pigeonhole principle (Q1849868) (← links)
- Lower bounds for the weak pigeonhole principle and random formulas beyond resolution (Q1854546) (← links)
- On the automatizability of resolution and related propositional proof systems (Q1881219) (← links)
- On the complexity of resolution with bounded conjunctions (Q1885907) (← links)
- Dual weak pigeonhole principle, Boolean complexity, and derandomization (Q1887654) (← links)
- Feasibly constructive proofs of succinct weak circuit lower bounds (Q2007873) (← links)
- The treewidth of proofs (Q2013559) (← links)
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution (Q2255289) (← links)
- Random resolution refutations (Q2311546) (← links)
- Circuit principles and weak pigeonhole variants (Q2383589) (← links)
- Hardness assumptions in the foundations of theoretical computer science (Q2388429) (← links)
- Upper and lower Ramsey bounds in bounded arithmetic (Q2488271) (← links)
- Separation results for the size of constant-depth propositional proofs (Q2566064) (← links)
- Typical forcings, NP search problems and an extension of a theorem of Riis (Q2659102) (← links)
- A tradeoff between length and width in resolution (Q2816413) (← links)
- Fragments of approximate counting (Q2921008) (← links)
- On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution (Q3012839) (← links)
- ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD <font>NP</font> ∩ <font>coNP</font> FUNCTION (Q3094358) (← links)
- Nisan-Wigderson generators in proof systems with forms of interpolation (Q3170558) (← links)
- The weak pigeonhole principle for function classes inS12 (Q3418087) (← links)
- The polynomial and linear hierarchies in models where the weak pigeonhole principle fails (Q3503756) (← links)
- On the correspondence between arithmetic theories and propositional proof systems – a survey (Q3619867) (← links)
- Randomized feasible interpolation and monotone circuits with a local oracle (Q4562441) (← links)
- Proof Complexity Meets Algebra (Q4617977) (← links)
- 2003 Annual Meeting of the Association for Symbolic Logic (Q4678936) (← links)
- Hardness magnification near state-of-the-art lower bounds (Q5028364) (← links)
- Approximate counting and NP search problems (Q5055313) (← links)
- Hardness magnification near state-of-the-art lower bounds (Q5091779) (← links)
- Parity Games and Propositional Proofs (Q5169973) (← links)
- From Small Space to Small Width in Resolution (Q5277893) (← links)
- On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies (Q5278196) (← links)
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds (Q5311724) (← links)
- An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams (Q5387310) (← links)
- On Independence of Variants of the Weak Pigeonhole Principle (Q5431613) (← links)
- The Complexity of Propositional Proofs (Q5444711) (← links)
