On the public citation graph
A New Proof of the Weak Pigeonhole Principle
0 signed · 80 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.
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.
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/3-540-44683-4_14openalex-snapshot
Improved Bounds on the Weak Pigeonhole Principle and Infinitely Many Primes from Weaker Axioms
inferredcites →https://doi.org/10.1007/978-3-662-22156-3openalex-snapshot
Metamathematics of First-Order Arithmetic
inferredcites →https://doi.org/10.1007/bf01200117openalex-snapshot
Exponential lower bounds for the pigeonhole principle
inferredcites →https://doi.org/10.1007/bfb0028012openalex-snapshot
Resolution and the weak pigeonhole principle
inferredcites →https://doi.org/10.1016/0168-0072(91)90096-5openalex-snapshot
Combinatorial principles in elementary number theory
inferredcites →https://doi.org/10.1016/0304-3975(88)90072-2openalex-snapshot
Resolution proofs of generalized pigeonhole principles
inferredcites →https://doi.org/10.1017/cbo9780511529948openalex-snapshot
Bounded Arithmetic, Propositional Logic and Complexity Theory
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.1070/im1995v059n01abeh000009openalex-snapshot
Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
inferredcites →https://doi.org/10.1090/dimacs/039openalex-snapshot
Proof Complexity and Feasible Arithmetics
inferredcites →https://doi.org/10.2307/2273826openalex-snapshot
Polynomial size proofs of the propositional pigeonhole principle
inferredcites →https://doi.org/10.2307/2275250openalex-snapshot
Lower bounds to the size of constant-depth propositional proofs
inferredcites →https://doi.org/10.7146/brics.v6i29.20098openalex-snapshot
A Complexity Gap for Tree-Resolution
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/malq.200610015openalex-snapshot
The weak pigeonhole principle for function classes in S12
inferred← citeshttps://doi.org/10.1002/malq.200910009openalex-snapshot
Abelian groups and quadratic residues in weak arithmetic
inferred← citeshttps://doi.org/10.1007/978-3-642-40313-2_62openalex-snapshot
Revisiting Space in Proof Complexity: Treewidth and Pathwidth
inferred← citeshttps://doi.org/10.1007/s00153-010-0212-9openalex-snapshot
A note on propositional proof complexity of some Ramsey-type statements
inferred← citeshttps://doi.org/10.1016/j.apal.2003.12.003openalex-snapshot
Dual weak pigeonhole principle, Boolean complexity, and derandomization
inferred← citeshttps://doi.org/10.1016/j.apal.2005.01.001openalex-snapshot
Upper and lower Ramsey bounds in bounded arithmetic
inferred← citeshttps://doi.org/10.1016/j.apal.2005.05.002openalex-snapshot
Separation results for the size of constant-depth propositional proofs
inferred← citeshttps://doi.org/10.1016/j.apal.2019.102735openalex-snapshot
Feasibly constructive proofs of succinct weak circuit lower bounds
inferred← citeshttps://doi.org/10.1016/j.apal.2020.102796openalex-snapshot
Expander construction in VNC1
inferred← citeshttps://doi.org/10.1016/j.apal.2020.102930openalex-snapshot
Typical forcings, NP search problems and an extension of a theorem of Riis
inferred← citeshttps://doi.org/10.1016/j.ic.2003.10.004openalex-snapshot
On the automatizability of resolution and related propositional proof systems
inferred← citeshttps://doi.org/10.1016/j.tcs.2007.04.017openalex-snapshot
Circuit principles and weak pigeonhole variants
inferred← citeshttps://doi.org/10.1016/j.tcs.2015.02.005openalex-snapshot
Quasipolynomial size proofs of the propositional pigeonhole principle
inferred← citeshttps://doi.org/10.1017/9781108242066.006openalex-snapshot
Quantified Propositional Calculus
inferred← citeshttps://doi.org/10.1017/9781108242066.008openalex-snapshot
Algebraic and Geometric Proof Systems
inferred← citeshttps://doi.org/10.1017/9781108242066.010openalex-snapshot
Basic Example of the Correspondence between Theories and Proof Systems
inferred← citeshttps://doi.org/10.1017/9781108242066.011openalex-snapshot
The Two Worlds of Bounded Arithmetic
inferred← citeshttps://doi.org/10.1017/9781108242066.012openalex-snapshot
Up to EF via the 〈. . .〉 Translation
inferred← citeshttps://doi.org/10.1017/9781108242066.013openalex-snapshot
Examples of Upper Bounds and p-Simulations
inferred← citeshttps://doi.org/10.1017/9781108242066.014openalex-snapshot
Beyond EF via the || . . . || Translation
inferred← citeshttps://doi.org/10.1017/9781108242066.016openalex-snapshot
LKd+1/2 and Combinatorial Restrictions
inferred← citeshttps://doi.org/10.1017/9781108242066.017openalex-snapshot
Fd and Logical Restrictions
inferred← citeshttps://doi.org/10.1017/9781108242066.018openalex-snapshot
Algebraic and Geometric Proof Systems
inferred← citeshttps://doi.org/10.1017/9781108242066.019openalex-snapshot
Feasible Interpolation: A Framework
inferred← citeshttps://doi.org/10.1017/9781108242066.020openalex-snapshot
Feasible Interpolation: Applications
inferred← citeshttps://doi.org/10.1017/9781108242066.022openalex-snapshot
Model Theory and Lower Bounds
inferred← citeshttps://doi.org/10.1017/9781108242066.024openalex-snapshot
The Nature of Proof Complexity
inferred← citeshttps://doi.org/10.1017/jsl.2014.56openalex-snapshot
LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE
inferred← citeshttps://doi.org/10.1090/s0002-9947-2015-06233-3openalex-snapshot
Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
inferred← citeshttps://doi.org/10.1093/logcom/exm017openalex-snapshot
On Independence of Variants of the Weak Pigeonhole Principle
inferred← citeshttps://doi.org/10.1109/ccc.2008.34openalex-snapshot
On the Relative Efficiency of Resolution-Like Proofs and Ordered Binary Decision Diagram Proofs
inferred← citeshttps://doi.org/10.1109/ccc.2013.20openalex-snapshot
Lower Bounds for DNF-refutations of a Relativized Weak Pigeonhole Principle
inferred← citeshttps://doi.org/10.1109/focs61266.2024.00044openalex-snapshot
Jump Operators, Interactive Proofs and Proof Complexity Generators
inferred← citeshttps://doi.org/10.1109/focs61266.2024.00089openalex-snapshot
Strong vs. Weak Range Avoidance and the Linear Ordering Principle
inferred← citeshttps://doi.org/10.1109/lics.2006.19openalex-snapshot
Conditional Lower Bound for a System of Constant-Depth Proofs with Modular Connectives
inferred← citeshttps://doi.org/10.1137/20m134784xopenalex-snapshot
Proof Complexity and the Binary Encoding of Combinatorial Principles
inferred← citeshttps://doi.org/10.1137/s0097539703428555openalex-snapshot
A Switching Lemma for Small Restrictions and Lower Bounds for k -DNF Resolution
inferred← citeshttps://doi.org/10.1142/s021906132250012xopenalex-snapshot
Approximate counting and NP search problems
inferred← citeshttps://doi.org/10.1145/2946801openalex-snapshot
On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies
inferred← citeshttps://doi.org/10.1145/3243126openalex-snapshot
Some Subsystems of Constant-Depth Frege with Parity
inferred← citeshttps://doi.org/10.1145/3798129.3800735openalex-snapshot
The Weak Rank Principle: Lower Bounds and Applications
inferred← citeshttps://doi.org/10.2178/bsl/1203350879openalex-snapshot
The Complexity of Propositional Proofs
inferred← citeshttps://doi.org/10.2178/jsl/1120224731openalex-snapshot
Structured pigeonhole principle, search problems and hard tautologies
inferred← citeshttps://doi.org/10.2178/jsl/1185803628openalex-snapshot
NP search problems in low fragments of bounded arithmetic
inferred← citeshttps://doi.org/10.2178/jsl/1191333850openalex-snapshot
Approximate counting in bounded arithmetic
inferred← citeshttps://doi.org/10.2178/jsl/1208359061openalex-snapshot
The polynomial and linear hierarchies in models where the weak pigeonhole principle fails
inferred← citeshttps://doi.org/10.2178/jsl/1245158087openalex-snapshot
Approximate counting by hashing in bounded arithmetic
inferred← citeshttps://doi.org/10.4288/jafpos.20.0_3openalex-snapshot
The Mathematical Infinite as a Matter of Method( Infinity in Philosophy and Mathematics)
inferred← citeshttps://doi.org/10.5821/dissertation-2117-94931openalex-snapshot
On the complexity of resolution-based proof systems
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.