The following pages link to On the weak pigeonhole principle (Q2773242):
Displaying 47 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)
- Resolution over linear equations and multilinear proofs (Q952492) (← links)
- A note about \(k\)-DNF resolution (Q1641156) (← 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)
- 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)
- (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 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)
- (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)
- The Complexity of Propositional Proofs (Q5444711) (← links)
- LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE (Q5501765) (← links)
- Space characterizations of complexity measures and size-space trade-offs in propositional proof systems (Q6168323) (← links)
- ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS (Q6204144) (← links)
- Proof complexity and the binary encoding of combinatorial principles (Q6562831) (← links)
- First-order reasoning and efficient semi-algebraic proofs (Q6614038) (← links)
