On the public citation graph
Counting problems in bounded arithmetic
0 signed · 162 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.1016/0168-0072(83)90038-6openalex-snapshot
∑11-Formulae on finite structures
inferredcites →https://doi.org/10.1090/s0002-9947-1963-0158822-2openalex-snapshot
Classes of predictably computable functions
inferredcites →https://doi.org/10.1109/sfcs.1981.35openalex-snapshot
Parity, circuits, and the polynomial-time hierarchy
inferredcites →https://doi.org/10.2307/1993719openalex-snapshot
Classes of Predictably Computable Functions
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(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/inco.1995.1067openalex-snapshot
Regular Languages Defined with Generalized Quantifiers
inferred← citeshttps://doi.org/10.1006/inco.1997.2674openalex-snapshot
Some Consequences of Cryptographical Conjectures forS12and EF
inferred← citeshttps://doi.org/10.1006/inco.2001.3084openalex-snapshot
Nonerasing, Counting, and Majority over the Linear Time Hierarchy
inferred← citeshttps://doi.org/10.1007/11494645_32openalex-snapshot
The Small Grzegorczyk Classes and the Typed λ-Calculus
inferred← citeshttps://doi.org/10.1007/11750321_23openalex-snapshot
Disjoint NP-Pairs from Propositional Proof Systems
inferred← citeshttps://doi.org/10.1007/3-540-19488-6_142openalex-snapshot
Regular languages defined with generalized quantifiers
inferred← citeshttps://doi.org/10.1007/3-540-45793-3_40openalex-snapshot
Resolution Refutations and Propositional Proofs with Height-Restrictions
inferred← citeshttps://doi.org/10.1007/3-540-60178-3_81openalex-snapshot
Computation models and function algebras
inferred← citeshttps://doi.org/10.1007/3-540-60178-3_86openalex-snapshot
Some consequences of cryptographical conjectures for S 2 1 and EF
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-1-4612-3466-1_1openalex-snapshot
Parity and the Pigeonhole Principle
inferred← citeshttps://doi.org/10.1007/978-3-0348-9078-6_22openalex-snapshot
Logic and Complexity: Independence results and the complexity of propositional calculus
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-0348-9328-2_9openalex-snapshot
The Power of Exponentiation in Arithmetic
inferred← citeshttps://doi.org/10.1007/978-3-540-27836-8_4openalex-snapshot
Feasible Proofs and Computations: Partnership and Fusion
inferred← citeshttps://doi.org/10.1007/978-3-642-02261-6_1openalex-snapshot
A Characterisation of Definable NP Search Problems in Peano Arithmetic
inferred← citeshttps://doi.org/10.1007/978-3-642-40313-2_12openalex-snapshot
Parity Games and Propositional Proofs
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/978-3-662-21963-8_6openalex-snapshot
A bottom-up approach to foundations of mathematics
inferred← citeshttps://doi.org/10.1007/978-3-662-21963-8_8openalex-snapshot
Forcing on Bounded Arithmetic
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/bf01302964openalex-snapshot
The complexity of the Pigeonhole Principle
inferred← citeshttps://doi.org/10.1007/bf01845704openalex-snapshot
Cutting planes, connectivity, and threshold logic
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-019-00702-wopenalex-snapshot
Induction rules in bounded arithmetic
inferred← citeshttps://doi.org/10.1007/s001530050060openalex-snapshot
Count( $q$ ) versus the pigeon-hole principle
inferred← citeshttps://doi.org/10.1007/s00224-007-9021-xopenalex-snapshot
Complexity-Theoretic Hierarchies Induced by Fragments of Gödel’s T
inferred← citeshttps://doi.org/10.1016/0168-0072(91)90096-5openalex-snapshot
Combinatorial principles in elementary number theory
inferred← citeshttps://doi.org/10.1016/0168-0072(94)00055-8openalex-snapshot
Δ0-complexity of the relation y = Πi ⩽ nF(i)
inferred← citeshttps://doi.org/10.1016/0168-0072(95)00029-gopenalex-snapshot
Transfinite induction within Peano arithmetic
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/0304-3975(88)90072-2openalex-snapshot
Resolution proofs of generalized pigeonhole principles
inferred← citeshttps://doi.org/10.1016/0304-3975(91)90317-uopenalex-snapshot
On the complexity of counting in the polynomial hierarchy
inferred← citeshttps://doi.org/10.1016/0890-5401(87)90044-7openalex-snapshot
A generalized Grzegorczyk hierarchy and low complexity classes
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.2009.06.004openalex-snapshot
On the computational complexity of cut-reduction
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.2020.102892openalex-snapshot
The canonical pairs of bounded depth Frege systems
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.apal.2024.103496openalex-snapshot
First-order reasoning and efficient semi-algebraic proofs
inferred← citeshttps://doi.org/10.1016/j.ipl.2012.03.009openalex-snapshot
A note on SAT algorithms and proof complexity
inferred← citeshttps://doi.org/10.1016/j.tcs.2007.04.017openalex-snapshot
Circuit principles and weak pigeonhole variants
inferred← citeshttps://doi.org/10.1016/s0049-237x(99)80033-0openalex-snapshot
Computation Models and Function Algebras
inferred← citeshttps://doi.org/10.1016/s0168-0072(97)00029-8openalex-snapshot
Count(ifq) does not imply Count(ifp)
inferred← citeshttps://doi.org/10.1016/s0168-0072(98)00030-xopenalex-snapshot
Bounded arithmetic, proof complexity and two papers of Parikh
inferred← citeshttps://doi.org/10.1016/s0304-3975(95)00245-6openalex-snapshot
Deterministic summation modulo Bn, the semigroup of binary relations on {0, 1,…, n − 1}
inferred← citeshttps://doi.org/10.1016/s0304-3975(96)00051-5openalex-snapshot
Nondeterministic stack register machines
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/9781316716939.010openalex-snapshot
Uniform Interpolation and Layered Bisimulation
inferred← citeshttps://doi.org/10.1017/9781316755723.004openalex-snapshot
Generalised dynamic ordinals — universal measures for implicit computational complexity
inferred← citeshttps://doi.org/10.1017/9781316755785.014openalex-snapshot
Consistency and games— in search of new combinatorial principles
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.1017/s0022481200028061openalex-snapshot
Provability of the pigeonhole principle and the existence of infinitely many primes
inferred← citeshttps://doi.org/10.1017/s0022481200029078openalex-snapshot
Finite automata, real time processes and counting problems in bounded arithmetics
inferred← citeshttps://doi.org/10.1017/s0960129510000198openalex-snapshot
Bounded minimalisation and bounded counting in argument-bounded idc's
inferred← citeshttps://doi.org/10.1090/dimacs/039/02openalex-snapshot
More on the relative strength of counting principles
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/jigpal/8.6.787openalex-snapshot
Generating hard tautologies using predicate logic and the symmetric group
inferred← citeshttps://doi.org/10.1093/logcom/exq009openalex-snapshot
Higher Types, Finite Domains and Resource-bounded Turing Machines
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.2013.20openalex-snapshot
Lower Bounds for DNF-refutations of a Relativized Weak Pigeonhole Principle
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00100openalex-snapshot
Indistinguishability Obfuscation via Mathematical Proofs of Equivalence
inferred← citeshttps://doi.org/10.1109/focs61266.2024.00044openalex-snapshot
Jump Operators, Interactive Proofs and Proof Complexity Generators
inferred← citeshttps://doi.org/10.1109/lics.2001.932490openalex-snapshot
Eliminating definitions and Skolem functions in first-order logic
inferred← citeshttps://doi.org/10.1109/lics.2001.932495openalex-snapshot
A second-order system for polytime reasoning using Gradel's theorem
inferred← citeshttps://doi.org/10.1109/lics.2004.1319607openalex-snapshot
Feasible proofs and computations: partnership and fusion
inferred← citeshttps://doi.org/10.1109/lics.2004.17openalex-snapshot
Feasible proofs and computations: partnership and fusion
inferred← citeshttps://doi.org/10.1109/lics.2008.30openalex-snapshot
On the Asymptotic Nullstellensatz and Polynomial Calculus Proof Complexity
inferred← citeshttps://doi.org/10.1109/lics.2008.9openalex-snapshot
On the Computational Complexity of Cut-Reduction
inferred← citeshttps://doi.org/10.1109/lics52264.2021.9470546openalex-snapshot
First-Order Reasoning and Efficient Semi-Algebraic Proofs
inferred← citeshttps://doi.org/10.1109/sct.1990.113967openalex-snapshot
Bounded arithmetic and computational complexity
inferred← citeshttps://doi.org/10.1109/sct.1991.160281openalex-snapshot
Approximation and small depth Frege proofs
inferred← citeshttps://doi.org/10.1109/sfcs.1988.21951openalex-snapshot
The complexity of the pigeonhole principle
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.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.1137/0221068openalex-snapshot
Approximation and Small-Depth Frege Proofs
inferred← citeshttps://doi.org/10.1142/s0219061309000847openalex-snapshot
POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
inferred← citeshttps://doi.org/10.1142/s021906132250012xopenalex-snapshot
Approximate counting and NP search problems
inferred← citeshttps://doi.org/10.1145/1007352.1007426openalex-snapshot
A conjecture about polynomial time computable lattice-lattice functions
inferred← citeshttps://doi.org/10.1145/129712.129733openalex-snapshot
Exponential lower bounds for the pigeonhole principle
inferred← citeshttps://doi.org/10.1145/2579822openalex-snapshot
Parity Games and Propositional Proofs
inferred← citeshttps://doi.org/10.1145/3060145openalex-snapshot
The NP Search Problems of Frege and Extended Frege Proofs
inferred← citeshttps://doi.org/10.1145/335305.335348openalex-snapshot
A new proof of the weak pigeonhole principle
inferred← citeshttps://doi.org/10.1145/3431922openalex-snapshot
Uniform, Integral, and Feasible Proofs for the Determinant Identities
inferred← citeshttps://doi.org/10.1145/3717823.3718276openalex-snapshot
Feasibly Constructive Proof of Schwartz–Zippel Lemma and the Complexity of Finding Hitting Sets
inferred← citeshttps://doi.org/10.1145/772062.772068openalex-snapshot
Eliminating definitions and Skolem functions in first-order logic
inferred← citeshttps://doi.org/10.1515/9783110324907.65openalex-snapshot
Characterising Definable Search Problems in Bounded Arithmetic via Proof Notations
inferred← citeshttps://doi.org/10.2168/lmcs-12(3:8)2016openalex-snapshot
Build your own clarithmetic I: Setup and completeness
inferred← citeshttps://doi.org/10.2168/lmcs-2(1:3)2006openalex-snapshot
Theories for TC0 and Other Small Complexity Classes
inferred← citeshttps://doi.org/10.2178/bsl/1203350879openalex-snapshot
The Complexity of Propositional Proofs
inferred← citeshttps://doi.org/10.2178/jsl/1080938841openalex-snapshot
Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
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/1208359061openalex-snapshot
The polynomial and linear hierarchies in models where the weak pigeonhole principle fails
inferred← citeshttps://doi.org/10.2178/jsl/1243948322openalex-snapshot
On bounded arithmetic augmented by the ability to count certain sets of primes
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/2273826openalex-snapshot
Polynomial size proofs of the propositional pigeonhole principle
inferred← citeshttps://doi.org/10.2307/2274765openalex-snapshot
Propositional proof systems, the consistency of first order theories and the complexity of computations
inferred← citeshttps://doi.org/10.2307/2275173openalex-snapshot
Local behaviour of the Chebyshev theorem in models of I⊿0
inferred← citeshttps://doi.org/10.2307/2275250openalex-snapshot
Lower bounds to the size of constant-depth propositional proofs
inferred← citeshttps://doi.org/10.2307/2275541openalex-snapshot
Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
inferred← citeshttps://doi.org/10.2307/2586729openalex-snapshot
Witnessing functions in bounded arithmetic and search problems
inferred← citeshttps://doi.org/10.2307/2687774openalex-snapshot
Tautologies from Pseudo-Random Generators
inferred← citeshttps://doi.org/10.2307/421131openalex-snapshot
The Complexity of Propositional Proofs
inferred← citeshttps://doi.org/10.4171/owr/2006/52openalex-snapshot
Mini-workshop: Logic, Combinatorics and Independence Results
inferred← citeshttps://doi.org/10.4230/lipics.csl.2020.12openalex-snapshot
Proof Complexity of Systems of (Non-Deterministic) Decision Trees and Branching Programs
inferred← citeshttps://doi.org/10.48550/arxiv.0712.1499openalex-snapshot
On the computational complexity of cut-reduction
inferred← citeshttps://doi.org/10.48550/arxiv.0801.4105openalex-snapshot
Quantified Propositional Logspace Reasoning
inferred← citeshttps://doi.org/10.48550/arxiv.1505.00118openalex-snapshot
Expansions of pseudofinite structures and circuit and proof complexity
inferred← citeshttps://doi.org/10.7146/brics.v1i21.21646openalex-snapshot
Count(q) does not imply Count(p)
inferred← citeshttps://doi.org/10.7146/brics.v1i23.21644openalex-snapshot
Finitisation in Bounded Arithmetic
inferred← citeshttps://doi.org/10.7146/brics.v1i36.21607openalex-snapshot
On provably disjoint NP-pairs
inferred← citeshttps://doi.org/10.7146/brics.v5i19.19425openalex-snapshot
Generating Hard Tautologies Using Predicate Logic and the Symmetric Group
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.