On the public citation graph
Exponential lower bounds for the pigeonhole principle
0 signed · 196 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-16486-3_102openalex-snapshot
A depth-size tradeoff for boolean circuits with unbounded fan-in
inferredcites →https://doi.org/10.1007/978-3-642-81955-1_28openalex-snapshot
On the Complexity of Derivation in Propositional Calculus
inferredcites →https://doi.org/10.1007/bf01744431openalex-snapshot
Parity, circuits, and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0166-218x(90)90079-ropenalex-snapshot
Lower bounds for recognizing small cliques on CRCW PRAM's
inferredcites →https://doi.org/10.1016/0168-0072(83)90038-6openalex-snapshot
∑11-Formulae on finite structures
inferredcites →https://doi.org/10.1016/0304-3975(85)90144-6openalex-snapshot
The intractability of resolution
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.1985.49openalex-snapshot
Separating the polynomial-time hierarchy by oracles
inferredcites →https://doi.org/10.1109/sfcs.1988.21951openalex-snapshot
The complexity of the pigeonhole principle
inferredcites →https://doi.org/10.1137/0221068openalex-snapshot
Approximation and Small-Depth Frege Proofs
inferredcites →https://doi.org/10.1145/129712.129733openalex-snapshot
Exponential lower bounds for the pigeonhole principle
inferredcites →https://doi.org/10.1145/65950.65958openalex-snapshot
Optimal bounds for decision problems on the CRCW PRAM
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
inferredcites →https://doi.org/10.2307/2275228openalex-snapshot
The deduction rule and linear and near-linear proof simulations
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1002/1521-3870(200111)47:4<461::aid-malq461>3.0.co;2-bopenalex-snapshot
Monotone Proofs of the Pigeon Hole Principle
inferred← citeshttps://doi.org/10.1002/1521-3870(200204)48:3<375::aid-malq375>3.0.co;2-lopenalex-snapshot
A Note on Conservativity Relations among Bounded Arithmetic Theories
inferred← citeshttps://doi.org/10.1002/malq.19970430313openalex-snapshot
Forcing in Finite Structures
inferred← citeshttps://doi.org/10.1002/malq.200410019openalex-snapshot
An unexpected separation result in Linearly Bounded Arithmetic
inferred← citeshttps://doi.org/10.1002/malq.200710069openalex-snapshot
On the correspondence between arithmetic theories and propositional proof systems – a survey
inferred← citeshttps://doi.org/10.1002/rsa.3240070103openalex-snapshot
An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
inferred← citeshttps://doi.org/10.1006/jcss.2002.1830openalex-snapshot
A New Proof of the Weak Pigeonhole Principle
inferred← citeshttps://doi.org/10.1007/3-540-44683-4_14openalex-snapshot
Improved Bounds on the Weak Pigeonhole Principle and Infinitely Many Primes from Weaker Axioms
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-61440-0_116openalex-snapshot
Lower bounds for prepositional proofs and independence results in bounded arithmetic
inferred← citeshttps://doi.org/10.1007/978-1-4612-2566-9_1openalex-snapshot
On the Existence of modulo p Cardinality Functions
inferred← citeshttps://doi.org/10.1007/978-1-4612-2566-9_10openalex-snapshot
On Frege and Extended Frege Proof Systems
inferred← citeshttps://doi.org/10.1007/978-1-4612-2566-9_3openalex-snapshot
Are there Hard Examples for Frege Systems?
inferred← citeshttps://doi.org/10.1007/978-3-030-24258-9_5openalex-snapshot
DRAT Proofs, Propagation Redundancy, and Extended Resolution
inferred← citeshttps://doi.org/10.1007/978-3-030-71430-7_18openalex-snapshot
Reflections on Proof Complexity and Counting Principles
inferred← citeshttps://doi.org/10.1007/978-3-0348-9110-3_9openalex-snapshot
The Power of Exponentiation in Arithmetic
inferred← citeshttps://doi.org/10.1007/978-3-319-09284-3_11openalex-snapshot
Proof Complexity and the Kneser-Lovász Theorem
inferred← citeshttps://doi.org/10.1007/978-3-319-40970-2_2openalex-snapshot
Satisfiability via Smooth Pictures
inferred← citeshttps://doi.org/10.1007/978-3-540-79709-8_4openalex-snapshot
Twelve Problems in Proof Complexity
inferred← citeshttps://doi.org/10.1007/978-3-642-13562-0_3openalex-snapshot
Proof Complexity of Non-classical Logics
inferred← citeshttps://doi.org/10.1007/978-3-642-13562-0_7openalex-snapshot
Algebraic Proofs over Noncommutative Formulas
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-30870-3_15openalex-snapshot
Complexity of Deep Inference via Atomic Flows
inferred← citeshttps://doi.org/10.1007/978-3-642-31485-8openalex-snapshot
Lectures on Logic and Computation
inferred← citeshttps://doi.org/10.1007/978-3-642-31485-8_1openalex-snapshot
Proof Complexity of Non-classical Logics
inferred← citeshttps://doi.org/10.1007/978-3-642-58622-4_5openalex-snapshot
Propositional Proof Complexity an Introduction
inferred← citeshttps://doi.org/10.1007/978-3-662-21963-8_6openalex-snapshot
A bottom-up approach to foundations of mathematics
inferred← citeshttps://doi.org/10.1007/978-3-7091-9461-4_4openalex-snapshot
A Fundamental Problem of Mathematical Logic
inferred← citeshttps://doi.org/10.1007/978-3-7091-9461-4_5openalex-snapshot
On the lengths of proofs of consistency
inferred← citeshttps://doi.org/10.1007/978-94-017-0487-8_4openalex-snapshot
On Methods for Proving Lower Bounds in Propositional Logic
inferred← citeshttps://doi.org/10.1007/bf01294258openalex-snapshot
Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
inferred← citeshttps://doi.org/10.1007/bf02391554openalex-snapshot
Some remarks on lengths of propositional proofs
inferred← citeshttps://doi.org/10.1007/bfb0028012openalex-snapshot
Resolution and the weak pigeonhole principle
inferred← citeshttps://doi.org/10.1007/bfb0029951openalex-snapshot
Lower bounds for a proof system with an exponential speed-up over constant-depth Frege systems and over polynomial calculus
inferred← citeshttps://doi.org/10.1007/s00037-002-0172-5openalex-snapshot
Hard examples for the bounded depth Frege proof system
inferred← citeshttps://doi.org/10.1007/s00037-008-0246-0openalex-snapshot
The Strength of Multilinear Proofs
inferred← citeshttps://doi.org/10.1007/s00037-013-0064-xopenalex-snapshot
Lifting lower bounds for tree-like proofs
inferred← citeshttps://doi.org/10.1007/s00037-020-00202-xopenalex-snapshot
Resolution with Counting: Dag-Like Lower Bounds and Different Moduli
inferred← citeshttps://doi.org/10.1007/s00153-003-0205-zopenalex-snapshot
Matrix identities and the pigeonhole principle
inferred← citeshttps://doi.org/10.1007/s00153-005-0325-8openalex-snapshot
Upper bounds on complexity of Frege proofs with limited use of certain schemata
inferred← citeshttps://doi.org/10.1007/s00153-008-0068-4openalex-snapshot
On meta complexity of propositional formulas and propositional proofs
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.1007/s00153-011-0240-0openalex-snapshot
Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
inferred← citeshttps://doi.org/10.1007/s00153-014-0398-3openalex-snapshot
Partially definable forcing and bounded arithmetic
inferred← citeshttps://doi.org/10.1007/s00153-024-00938-1openalex-snapshot
On some $$\Sigma ^{B}_{0}$$-formulae generalizing counting principles over $$V^{0}$$
inferred← citeshttps://doi.org/10.1007/s001530050060openalex-snapshot
Count( $q$ ) versus the pigeon-hole principle
inferred← citeshttps://doi.org/10.1016/0168-0072(96)83747-xopenalex-snapshot
An exponential separation between the parity principle and the pigeonhole principle
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.2011.09.009openalex-snapshot
Towards NP – P via proof complexity and search
inferred← citeshttps://doi.org/10.1016/j.apal.2019.05.002openalex-snapshot
On transformations of constant depth propositional proofs
inferred← citeshttps://doi.org/10.1016/j.apal.2022.103166openalex-snapshot
Bounded-depth Frege complexity of Tseitin formulas for all graphs
inferred← citeshttps://doi.org/10.1016/j.apal.2024.103538openalex-snapshot
Strength and limitations of Sherali-Adams and Nullstellensatz proof systems
inferred← citeshttps://doi.org/10.1016/j.ic.2011.07.004openalex-snapshot
Algebraic proofs over noncommutative formulas
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.09.021openalex-snapshot
LA, permutations, and the Hajós Calculus
inferred← citeshttps://doi.org/10.1016/j.tcs.2006.03.011openalex-snapshot
Polynomial-size Frege and resolution proofs of st-connectivity and Hex tautologies
inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00394-8openalex-snapshot
Improved bounds on the Weak Pigeonhole Principle and infinitely many primes from weaker axioms
inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00446-2openalex-snapshot
Algebraic proof systems over formulas
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/9781316716939.007openalex-snapshot
A bottom-up approach to foundations of mathematics
inferred← citeshttps://doi.org/10.1017/9781316716939.008openalex-snapshot
K-graph Machines: generalizing Turing's machines and arguments
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/dimacs/039/01openalex-snapshot
Plausibly hard combinatorial tautologies
inferred← citeshttps://doi.org/10.1090/dimacs/039/02openalex-snapshot
More on the relative strength of counting principles
inferred← citeshttps://doi.org/10.1090/proc/16709openalex-snapshot
Extended Nullstellensatz proof systems
inferred← citeshttps://doi.org/10.1090/s0002-9939-2015-12610-xopenalex-snapshot
A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
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.1090/s0273-0979-97-00715-5openalex-snapshot
Making proofs without Modus Ponens: An introduction to the combinatorics and complexity of cut elimination
inferred← citeshttps://doi.org/10.1090/tran/8494openalex-snapshot
Where pigeonhole principles meet König lemmas
inferred← citeshttps://doi.org/10.1093/ietfec/e91-a.9.2301openalex-snapshot
New Graph Calculi for Planar Non-3-Colorable Graphs
inferred← citeshttps://doi.org/10.1109/ccc.2002.1004321openalex-snapshot
Hard examples for bounded depth frege
inferred← citeshttps://doi.org/10.1109/ccc.2004.1313795openalex-snapshot
Relativized NP search problems and propositional proof systems
inferred← citeshttps://doi.org/10.1109/ccc.2004.30openalex-snapshot
Relativized NP search problems and propositional proof systems
inferred← citeshttps://doi.org/10.1109/ccc.2011.34openalex-snapshot
Relativized Separations of Worst-Case and Average-Case Complexities for NP
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/focs.2014.20openalex-snapshot
Circuit Complexity, Proof Complexity, and Polynomial Identity Testing
inferred← citeshttps://doi.org/10.1109/focs.2015.67openalex-snapshot
An Average-Case Depth Hierarchy Theorem for Boolean Circuits
inferred← citeshttps://doi.org/10.1109/focs.2017.18openalex-snapshot
On Small-Depth Frege Proofs for Tseitin for Grids
inferred← citeshttps://doi.org/10.1109/focs.2019.00080openalex-snapshot
Why are Proof Complexity Lower Bounds Hard?
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00052openalex-snapshot
Tradeoffs for small-depth Frege proofs
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00110openalex-snapshot
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited
inferred← citeshttps://doi.org/10.1109/focs57990.2023.00010openalex-snapshot
On small-depth Frege proofs for PHP
inferred← citeshttps://doi.org/10.1109/lics.1993.287577openalex-snapshot
An exponential separation between the matching principle and the pigeonhole 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.1109/sct.1995.514725openalex-snapshot
Intractability of read-once resolution
inferred← citeshttps://doi.org/10.1109/sfcs.1994.365714openalex-snapshot
Lower bounds on Hilbert's Nullstellensatz and propositional proofs
inferred← citeshttps://doi.org/10.1109/sfcs.2001.959894openalex-snapshot
Counting axioms do not polynomially simulate counting gates
inferred← citeshttps://doi.org/10.1109/sfcs.2002.1181982openalex-snapshot
Bounded-depth Frege lower bounds for weaker pigeonhole principles
inferred← citeshttps://doi.org/10.1112/plms/pdq044openalex-snapshot
The provably total search problems of bounded arithmetic
inferred← citeshttps://doi.org/10.1112/plms/s3-69.1.1openalex-snapshot
An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
inferred← citeshttps://doi.org/10.1137/16m1107632openalex-snapshot
Characterizing Propositional Proofs as Noncommutative Formulas
inferred← citeshttps://doi.org/10.1137/21m1447519openalex-snapshot
Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity
inferred← citeshttps://doi.org/10.1137/22m153851xopenalex-snapshot
On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited
inferred← citeshttps://doi.org/10.1137/s0097539703433146openalex-snapshot
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles
inferred← citeshttps://doi.org/10.1142/s021906132250012xopenalex-snapshot
Approximate counting and NP search problems
inferred← citeshttps://doi.org/10.1145/1131313.1131314openalex-snapshot
Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations
inferred← citeshttps://doi.org/10.1145/129712.129733openalex-snapshot
Exponential lower bounds for the pigeonhole principle
inferred← citeshttps://doi.org/10.1145/1740582.1740587openalex-snapshot
Lower bounds for bounded depth Frege proofs via Pudlák-Buss games
inferred← citeshttps://doi.org/10.1145/2603088.2603164openalex-snapshot
On the pigeonhole and related principles in deep inference and monotone systems
inferred← citeshttps://doi.org/10.1145/2656209openalex-snapshot
Exponential Lower Bounds for AC 0 -Frege Imply Superpolynomial Frege Lower Bounds
inferred← citeshttps://doi.org/10.1145/2897518.2897637openalex-snapshot
Poly-logarithmic Frege depth lower bounds via an expander switching lemma
inferred← citeshttps://doi.org/10.1145/2933575.2933597openalex-snapshot
Understanding Gentzen and Frege Systems for QBF
inferred← citeshttps://doi.org/10.1145/2951860.2951874openalex-snapshot
SIGACT News Complexity Theory Column 91
inferred← citeshttps://doi.org/10.1145/3095799openalex-snapshot
An Average-Case Depth Hierarchy Theorem for Boolean Circuits
inferred← citeshttps://doi.org/10.1145/335305.335348openalex-snapshot
A new proof of the weak pigeonhole principle
inferred← citeshttps://doi.org/10.1145/3378665openalex-snapshot
Reasons for Hardness in QBF Proof Systems
inferred← citeshttps://doi.org/10.1145/3381881openalex-snapshot
Frege Systems for Quantified Boolean Logic
inferred← citeshttps://doi.org/10.1145/3406325.3451010openalex-snapshot
Iterated lower bound formulas: a diagonalization-based approach to proof complexity
inferred← citeshttps://doi.org/10.1145/3425606openalex-snapshot
On Small-depth Frege Proofs for Tseitin for Grids
inferred← citeshttps://doi.org/10.1145/3471469.3471478openalex-snapshot
SIGACT News Complexity Theory Column 109
inferred← citeshttps://doi.org/10.1145/3506702openalex-snapshot
On Proof Complexity of Resolution over Polynomial Calculus
inferred← citeshttps://doi.org/10.1145/3531130.3533344openalex-snapshot
On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
inferred← citeshttps://doi.org/10.1145/3579997openalex-snapshot
Circular (Yet Sound) Proofs in Propositional Logic
inferred← citeshttps://doi.org/10.1145/3618260.3649616openalex-snapshot
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
inferred← citeshttps://doi.org/10.1145/3798129.3800735openalex-snapshot
The Weak Rank Principle: Lower Bounds and Applications
inferred← citeshttps://doi.org/10.1145/3798129.3800809openalex-snapshot
Lower Bounds for Near-Quadratic-Depth Resolution over Parities
inferred← citeshttps://doi.org/10.1145/3801091openalex-snapshot
Towards P≠NP from Extended Frege lower bounds
inferred← citeshttps://doi.org/10.1145/509907.509988openalex-snapshot
Hard examples for bounded depth frege
inferred← citeshttps://doi.org/10.1305/ndjfl/1040046140openalex-snapshot
Simplified Lower Bounds for Propositional Proofs
inferred← citeshttps://doi.org/10.2168/lmcs-11(1:4)2015openalex-snapshot
On the relative proof complexity of deep inference via atomic flows
inferred← citeshttps://doi.org/10.2178/bsl/1203350879openalex-snapshot
The Complexity of Propositional Proofs
inferred← citeshttps://doi.org/10.2178/jsl/1080938837openalex-snapshot
Approximate Euler characteristic, dimension, and weak pigeonhole principles
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/1268917504openalex-snapshot
A form of feasible interpolation for constant depth Frege systems
inferred← citeshttps://doi.org/10.2307/2275228openalex-snapshot
The deduction rule and linear and near-linear proof simulations
inferred← citeshttps://doi.org/10.2307/2586729openalex-snapshot
Witnessing functions in bounded arithmetic and search problems
inferred← citeshttps://doi.org/10.2307/421058openalex-snapshot
Combinatorics with Definable Sets: Euler Characteristics and Grothendieck Rings
inferred← citeshttps://doi.org/10.2307/421131openalex-snapshot
The Complexity of Propositional Proofs
inferred← citeshttps://doi.org/10.23638/lmcs-16(1:1)2020openalex-snapshot
On the logical complexity of cyclic arithmetic
inferred← citeshttps://doi.org/10.23638/lmcs-17(2:12)2021openalex-snapshot
DRAT and Propagation Redundancy Proofs Without New Variables
inferred← citeshttps://doi.org/10.29007/2b78openalex-snapshot
Beyond DRAT: Challenges in Certifying UNSAT
inferred← citeshttps://doi.org/10.36253/979-12-215-0778-2.12openalex-snapshot
Sequent calculus and complexity theory
inferred← citeshttps://doi.org/10.4171/owr/2006/52openalex-snapshot
Mini-workshop: Logic, Combinatorics and Independence Results
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2024.33openalex-snapshot
Failure of Feasible Disjunction Property for $k$-DNF Resolution and NP-hardness of Automating It
inferred← citeshttps://doi.org/10.4230/lipics.mfcs.2018.70openalex-snapshot
Tree Tribes and Lower Bounds for Switching Lemmas
inferred← citeshttps://doi.org/10.48550/arxiv.1311.2501openalex-snapshot
A reduction of proof complexity to computational complexity for $AC^0[p]$ Frege systems
inferred← citeshttps://doi.org/10.48550/arxiv.1609.04218openalex-snapshot
The complexity of propositional proofs
inferred← citeshttps://doi.org/10.48550/arxiv.1811.01421openalex-snapshot
Why Extension-Based Proofs Fail
inferred← citeshttps://doi.org/10.48550/arxiv.1909.03691openalex-snapshot
The Cook-Reckhow definition
inferred← citeshttps://doi.org/10.5821/dissertation-2117-94931openalex-snapshot
On the complexity of resolution-based proof systems
inferred← citeshttps://doi.org/10.7146/brics.v1i21.21646openalex-snapshot
Count(q) does not imply Count(p)
inferred← citeshttps://doi.org/10.7146/brics.v1i26.21640openalex-snapshot
Count(q) versus the Pigeon-Hole Principle
inferred← citeshttps://doi.org/10.7146/brics.v6i29.20098openalex-snapshot
A Complexity Gap for Tree-Resolution
inferred← citeshttps://doi.org/10.7282/t32b8wngopenalex-snapshot
Some applications of randomness in computational complexity
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.