On the public citation graph

Resolution and the weak pigeonhole principle

https://doi.org/10.1007/bfb0028012
0 signed · 69 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1002/rsa.3240070103openalex-snapshot
An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
inferredcites →https://doi.org/10.1007/bf01200117openalex-snapshot
Exponential lower bounds for the pigeonhole principle
inferredcites →https://doi.org/10.1016/0304-3975(85)90144-6openalex-snapshot
The intractability of resolution
inferredcites →https://doi.org/10.1016/0304-3975(88)90072-2openalex-snapshot
Resolution proofs of generalized pigeonhole principles
inferredcites →https://doi.org/10.1017/s0022481200028061openalex-snapshot
Provability of the pigeonhole principle and the existence of infinitely many primes
inferredcites →https://doi.org/10.1109/sfcs.1988.21951openalex-snapshot
The complexity of the pigeonhole principle
inferredcites →https://doi.org/10.1145/129712.129733openalex-snapshot
Exponential lower bounds for the pigeonhole principle
inferredcites →https://doi.org/10.1145/258533.258673openalex-snapshot
Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus
inferredcites →https://doi.org/10.2307/2273702openalex-snapshot
The relative efficiency of propositional proof systems
inferredcites →https://doi.org/10.2307/2273826openalex-snapshot
Polynomial size proofs of the propositional pigeonhole principle

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1006/inco.2001.2921openalex-snapshot
Space Bounds for Resolution
inferred← citeshttps://doi.org/10.1006/inco.2002.3114openalex-snapshot
Lower Bounds for the Weak Pigeonhole Principle and Random Formulas beyond Resolution
inferred← citeshttps://doi.org/10.1006/jcss.2002.1830openalex-snapshot
A New Proof of the Weak Pigeonhole Principle
inferred← citeshttps://doi.org/10.1007/11750321_6openalex-snapshot
Width Versus Size in Resolution Proofs
inferred← citeshttps://doi.org/10.1007/3-540-45022-x_13openalex-snapshot
Monotone Proofs of the Pigeon Hole Principle
inferred← citeshttps://doi.org/10.1007/3-540-46011-x_8openalex-snapshot
Proof Complexity of Pigeonhole Principles
inferred← citeshttps://doi.org/10.1007/3-540-46632-0_14openalex-snapshot
Tree-Like Resolution Is Superpolynomially Slower Than DAG-Like Resolution for the Pigeonhole Principle
inferred← citeshttps://doi.org/10.1007/3-540-48168-0_26openalex-snapshot
Lower Bounds for Space in Resolution
inferred← citeshttps://doi.org/10.1007/3-540-48224-5_81openalex-snapshot
Lower Bounds for the Weak Pigeonhole Principle Beyond Resolution
inferred← citeshttps://doi.org/10.1007/3-540-49116-3_52openalex-snapshot
Space Bounds for Resolution
inferred← citeshttps://doi.org/10.1007/978-3-030-51825-7_15openalex-snapshot
Mycielski Graphs and PR Proofs
inferred← citeshttps://doi.org/10.1007/978-3-030-61792-9_27openalex-snapshot
Sherali-Adams and the Binary Encoding of Combinatorial Principles
inferred← citeshttps://doi.org/10.1007/978-3-319-05446-9_9openalex-snapshot
A Tutorial on Time and Space Bounds in Tree-Like Resolution
inferred← citeshttps://doi.org/10.1007/978-3-319-20297-6_15openalex-snapshot
Resolution Complexity of Perfect Matching Principles for Sparse Graphs
inferred← citeshttps://doi.org/10.1007/978-3-540-24628-2_4openalex-snapshot
RCA-Based Detection Methods for Resolution Refutation
inferred← citeshttps://doi.org/10.1007/978-3-642-22006-7_53openalex-snapshot
Parameterized Bounded-Depth Frege Is Not Optimal
inferred← citeshttps://doi.org/10.1007/978-3-642-24508-4openalex-snapshot
Boolean Function Complexity: Advances and Frontiers
inferred← citeshttps://doi.org/10.1007/s00037-001-8194-yopenalex-snapshot
A complexity gap for tree resolution
inferred← citeshttps://doi.org/10.1007/s00037-010-0001-1openalex-snapshot
Parameterized Proof Complexity
inferred← citeshttps://doi.org/10.1007/s00165-011-0186-3openalex-snapshot
Improved algorithms for optimal length resolution refutation in difference constraint systems
inferred← citeshttps://doi.org/10.1007/s00224-023-10134-yopenalex-snapshot
Unit Read-once Refutations for Systems of Difference Constraints
inferred← citeshttps://doi.org/10.1007/s00493-002-0007-7openalex-snapshot
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus
inferred← citeshttps://doi.org/10.1007/s00493-004-0030-yopenalex-snapshot
Regular Resolution Lower Bounds For The Weak Pigeonhole Principle
inferred← citeshttps://doi.org/10.1007/s10472-004-9433-0openalex-snapshot
Toward Leaner Binary-Clause Reasoning in a Satisfiability Solver
inferred← citeshttps://doi.org/10.1007/s10817-009-9139-4openalex-snapshot
Optimal Length Resolution Refutations of Difference Constraint Systems
inferred← citeshttps://doi.org/10.1016/j.apal.2008.04.001openalex-snapshot
Resolution over linear equations and multilinear proofs
inferred← citeshttps://doi.org/10.1016/j.jcss.2004.01.004openalex-snapshot
Resolution lower bounds for perfect matching principles
inferred← citeshttps://doi.org/10.1016/j.tcs.2018.02.002openalex-snapshot
Finding read-once resolution refutations in systems of 2CNF clauses
inferred← citeshttps://doi.org/10.1017/s096012952000016xopenalex-snapshot
NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability
inferred← citeshttps://doi.org/10.1023/a:1021231610627openalex-snapshot
Resolution Proofs of Matching Principles
inferred← citeshttps://doi.org/10.1109/ccc.2001.933873openalex-snapshot
Tree resolution proofs of the weak pigeon-hole principle
inferred← citeshttps://doi.org/10.1109/ccc.2002.1004320openalex-snapshot
Resolution lower bounds for the weak pigeon hole principle
inferred← citeshttps://doi.org/10.1109/ccc.2002.1004336openalex-snapshot
Resolution lower bounds for perfect matching principles
inferred← citeshttps://doi.org/10.1109/ccc.2002.1004337openalex-snapshot
Resolution width-size trade-offs for the Pigeon-Hole Principle
inferred← citeshttps://doi.org/10.1109/ccc.2012.27openalex-snapshot
Space Complexity in Polynomial Calculus
inferred← citeshttps://doi.org/10.1109/focs.2007.52openalex-snapshot
Minimizing Average Flow-time : Upper and Lower Bounds
inferred← citeshttps://doi.org/10.1109/focs.2007.53openalex-snapshot
Parameterized Proof Complexity
inferred← citeshttps://doi.org/10.1109/sfcs.1996.548486openalex-snapshot
Simplified and improved resolution lower bounds
inferred← citeshttps://doi.org/10.1109/sffcs.1999.814614openalex-snapshot
A study of proof search algorithms for resolution and polynomial calculus
inferred← citeshttps://doi.org/10.1137/20m134784xopenalex-snapshot
Proof Complexity and the Binary Encoding of Combinatorial Principles
inferred← citeshttps://doi.org/10.1137/s0097539700369156openalex-snapshot
The Efficiency of Resolution and Davis--Putnam Procedures
inferred← citeshttps://doi.org/10.1145/2499937.2499941openalex-snapshot
Parameterized Complexity of DPLL Search Procedures
inferred← citeshttps://doi.org/10.1145/258533.258673openalex-snapshot
Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus
inferred← citeshttps://doi.org/10.1145/301250.301392openalex-snapshot
Short proofs are narrow—resolution made simple
inferred← citeshttps://doi.org/10.1145/335305.335348openalex-snapshot
A new proof of the weak pigeonhole principle
inferred← citeshttps://doi.org/10.1145/375827.375835openalex-snapshot
Short proofs are narrow—resolution made simple
inferred← citeshttps://doi.org/10.1145/380752.380821openalex-snapshot
Regular resolution lower bounds for the weak pigeonhole principle
inferred← citeshttps://doi.org/10.1145/509907.509975openalex-snapshot
Size space tradeoffs for resolution
inferred← citeshttps://doi.org/10.21015/vtcs.v11i1.1407openalex-snapshot
Statistical Methods in Computer Science: A Comparative Review of Inductive and Deductive Approaches
inferred← citeshttps://doi.org/10.2168/lmcs-3(1:6)2007openalex-snapshot
Structure and Problem Hardness: Goal Asymmetry and DPLL Proofs in SAT-Based Planning
inferred← citeshttps://doi.org/10.2168/lmcs-4(4:13)2008openalex-snapshot
Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning
inferred← citeshttps://doi.org/10.2178/bsl/1203350879openalex-snapshot
The Complexity of Propositional Proofs
inferred← citeshttps://doi.org/10.3233/fi-2016-1358openalex-snapshot
Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles
inferred← citeshttps://doi.org/10.33915/etd.3843openalex-snapshot
Analyzing Satisfiability and Refutability in Selected Constraint Systems
inferred← citeshttps://doi.org/10.4036/iis.2015.l.02openalex-snapshot
An Introduction to Lower Bounds on Resolution Proof Systems
inferred← citeshttps://doi.org/10.4064/fm170-1-8openalex-snapshot
On the weak pigeonhole principle
inferred← citeshttps://doi.org/10.46298/theoretics.25.9openalex-snapshot
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
inferred← citeshttps://doi.org/10.48550/arxiv.1809.02843openalex-snapshot
Resolution and the binary encoding of combinatorial principles
inferred← citeshttps://doi.org/10.7146/brics.v6i29.20098openalex-snapshot
A Complexity Gap for Tree-Resolution
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.