On the public citation graph
Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
0 signed · 141 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/978-1-4612-3466-1_1openalex-snapshot
Parity and the Pigeonhole Principle
inferredcites →https://doi.org/10.1007/978-3-7091-9461-4_4openalex-snapshot
A Fundamental Problem of Mathematical Logic
inferredcites →https://doi.org/10.1007/978-94-017-0487-8_4openalex-snapshot
On Methods for Proving Lower Bounds in Propositional Logic
inferredcites →https://doi.org/10.1007/bf01200117openalex-snapshot
Exponential lower bounds for the pigeonhole principle
inferredcites →https://doi.org/10.1007/bf02391554openalex-snapshot
Some remarks on lengths of propositional proofs
inferredcites →https://doi.org/10.1007/s000370050013openalex-snapshot
Lower bounds for the polynomial calculus
inferredcites →https://doi.org/10.1016/0168-0072(96)83747-xopenalex-snapshot
An exponential separation between the parity principle and the pigeonhole principle
inferredcites →https://doi.org/10.1016/0304-3975(85)90144-6openalex-snapshot
The intractability of resolution
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.1090/dimacs/031/07openalex-snapshot
Algebraic propositional proof systems
inferredcites →https://doi.org/10.1090/dimacs/039/02openalex-snapshot
More on the relative strength of counting principles
inferredcites →https://doi.org/10.1109/lics.1993.287577openalex-snapshot
An exponential separation between the matching principle and the pigeonhole principle
inferredcites →https://doi.org/10.1109/sfcs.1988.21951openalex-snapshot
The complexity of the pigeonhole principle
inferredcites →https://doi.org/10.1109/sfcs.1994.365714openalex-snapshot
Lower bounds on Hilbert's Nullstellensatz and propositional proofs
inferredcites →https://doi.org/10.1112/plms/s3-73.1.1openalex-snapshot
Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
inferredcites →https://doi.org/10.1137/0221068openalex-snapshot
Approximation and Small-Depth Frege Proofs
inferredcites →https://doi.org/10.1145/12130.12132openalex-snapshot
Almost optimal lower bounds for small depth circuits
inferredcites →https://doi.org/10.1145/195058.195207openalex-snapshot
The independence of the modulo p counting principles
inferredcites →https://doi.org/10.1145/225058.225147openalex-snapshot
The relative complexity of NP search problems
inferredcites →https://doi.org/10.1145/225058.225275openalex-snapshot
Lower bounds for cutting planes proofs with small coefficients
inferredcites →https://doi.org/10.1145/237814.237860openalex-snapshot
Using the Groebner basis algorithm to find proofs of unsatisfiability
inferredcites →https://doi.org/10.1145/28395.28404openalex-snapshot
Algebraic methods in the theory of lower bounds for Boolean circuit complexity
inferredcites →https://doi.org/10.1145/48014.48016openalex-snapshot
Many hard examples for resolution
inferredcites →https://doi.org/10.2178/bsl/1203350879openalex-snapshot
The Complexity of Propositional Proofs
inferredcites →https://doi.org/10.2307/2007638openalex-snapshot
Encyclopedia of Mathematics and its Applications.
inferredcites →https://doi.org/10.2307/2273702openalex-snapshot
The relative efficiency of propositional proof systems
inferredcites →https://doi.org/10.2307/2275250openalex-snapshot
Lower bounds to the size of constant-depth propositional proofs
inferredcites →https://doi.org/10.2307/2275541openalex-snapshot
Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
inferredcites →https://doi.org/10.2307/421131openalex-snapshot
The Complexity of Propositional Proofs
inferredcites →https://doi.org/10.7146/brics.v1i21.21646openalex-snapshot
Count(q) does not imply Count(p)
inferredcites →https://doi.org/10.7146/brics.v1i23.21644openalex-snapshot
Finitisation in Bounded Arithmetic
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1006/jcss.1998.1585openalex-snapshot
Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle
inferred← citeshttps://doi.org/10.1006/jcss.2000.1726openalex-snapshot
Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes
inferred← citeshttps://doi.org/10.1007/3-540-45022-x_78openalex-snapshot
Homogenization and the Polynomial Calculus
inferred← citeshttps://doi.org/10.1007/3-540-45465-9_19openalex-snapshot
Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations
inferred← citeshttps://doi.org/10.1007/3-540-45465-9_23openalex-snapshot
Exponential Lower Bound for Static Semi-algebraic Proofs
inferred← citeshttps://doi.org/10.1007/3-540-45841-7_34openalex-snapshot
Complexity of Semi-algebraic Proofs
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-3-319-66902-1_22openalex-snapshot
Parameterized Provability in Equational Logic
inferred← citeshttps://doi.org/10.1007/978-3-540-72504-6_58openalex-snapshot
Phase Transition of Multivariate Polynomial Systems
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_7openalex-snapshot
Algebraic Proofs over Noncommutative Formulas
inferred← citeshttps://doi.org/10.1007/978-3-642-13824-9_1openalex-snapshot
Entailment Multipliers: An Algebraic Characterization of Validity for Classical and Modal Logics
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-001-8192-0openalex-snapshot
Complexity of Positivstellensatz proofs for the knapsack
inferred← citeshttps://doi.org/10.1007/s00037-002-0171-6openalex-snapshot
Homogenization and the 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-019-00182-7openalex-snapshot
Random resolution refutations
inferred← citeshttps://doi.org/10.1007/s00037-020-00201-yopenalex-snapshot
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
inferred← citeshttps://doi.org/10.1007/s00037-024-00250-7openalex-snapshot
KRW Composition Theorems via Lifting
inferred← citeshttps://doi.org/10.1007/s000370050024openalex-snapshot
Lower bounds for the polynomial calculus and the Gröbner basis algorithm
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.2011.09.009openalex-snapshot
Towards NP – P via proof complexity and search
inferred← citeshttps://doi.org/10.1016/j.apal.2012.01.015openalex-snapshot
Propositional proofs and reductions between NP search problems
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.ic.2011.07.004openalex-snapshot
Algebraic proofs over noncommutative formulas
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/s0022-4049(00)00069-4openalex-snapshot
Uniformly generated submodules of permutation modules
inferred← citeshttps://doi.org/10.1016/s0168-0072(01)00055-0openalex-snapshot
Complexity of Null- and Positivstellensatz proofs
inferred← citeshttps://doi.org/10.1016/s0304-3975(00)00157-2openalex-snapshot
Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
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/s0960129508007251openalex-snapshot
Phase transition of multivariate polynomial systems
inferred← citeshttps://doi.org/10.1090/dimacs/039/02openalex-snapshot
More on the relative strength of counting principles
inferred← citeshttps://doi.org/10.1090/dimacs/039/04openalex-snapshot
Lower bounds on Nullstellensatz proofs via designs
inferred← citeshttps://doi.org/10.1090/proc/16709openalex-snapshot
Extended Nullstellensatz proof systems
inferred← citeshttps://doi.org/10.1090/pspum/111/02040openalex-snapshot
The nonlinear algebra view of discrete mathematics
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.1109/ccc.1996.507685openalex-snapshot
Good degree bounds on Nullstellensatz refutations of the induction principle
inferred← citeshttps://doi.org/10.1109/ccc.2009.9openalex-snapshot
The Proof Complexity of Polynomial Identities
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00011openalex-snapshot
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00025openalex-snapshot
Simple Hard Instances for Low-Depth Algebraic Proofs
inferred← citeshttps://doi.org/10.1109/sfcs.1998.743444openalex-snapshot
Unsatisfiable systems of equations, over a finite field
inferred← citeshttps://doi.org/10.1109/sfcs.1998.743515openalex-snapshot
Tseitin's tautologies and lower bounds for Nullstellensatz proofs
inferred← citeshttps://doi.org/10.1109/sfcs.2001.959893openalex-snapshot
Lower bounds for polynomial calculus: non-binomial case
inferred← citeshttps://doi.org/10.1109/sfcs.2001.959894openalex-snapshot
Counting axioms do not polynomially simulate counting gates
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/1.9781611974782.21openalex-snapshot
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
inferred← citeshttps://doi.org/10.1137/16m1107632openalex-snapshot
Characterizing Propositional Proofs as Noncommutative Formulas
inferred← citeshttps://doi.org/10.1137/20m1374523openalex-snapshot
Semialgebraic Proofs, IPS Lower Bounds, and the \(\boldsymbol{\tau}\)-Conjecture: Can a Natural Number be Negative?
inferred← citeshttps://doi.org/10.1137/21m1447519openalex-snapshot
Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity
inferred← citeshttps://doi.org/10.1142/s0219061318500125openalex-snapshot
Randomized feasible interpolation and monotone circuits with a local oracle
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/1740582.1740587openalex-snapshot
Lower bounds for bounded depth Frege proofs via Pudlák-Buss games
inferred← citeshttps://doi.org/10.1145/2422436.2422486openalex-snapshot
Pseudo-partitions, transversality and locality
inferred← citeshttps://doi.org/10.1145/2699438openalex-snapshot
A Framework for Space Complexity in Algebraic Proof Systems
inferred← citeshttps://doi.org/10.1145/301250.301399openalex-snapshot
Linear gaps between degrees for the polynomial calculus modulo distinct primes
inferred← citeshttps://doi.org/10.1145/3243126openalex-snapshot
Some Subsystems of Constant-Depth Frege with Parity
inferred← citeshttps://doi.org/10.1145/3357713.3384245openalex-snapshot
Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative?
inferred← citeshttps://doi.org/10.1145/3357713.3384288openalex-snapshot
(Semi)Algebraic proofs over {±1} variables
inferred← citeshttps://doi.org/10.1145/3373718.3394754openalex-snapshot
The Surprising Power of Constant Depth Algebraic Proofs
inferred← citeshttps://doi.org/10.1145/3519935.3520025openalex-snapshot
Ideals, determinants, and straightening: proving and using lower bounds for polynomial ideals
inferred← citeshttps://doi.org/10.1145/3618260.3649616openalex-snapshot
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
inferred← citeshttps://doi.org/10.1215/ijm/1258138254openalex-snapshot
On the degree of ideal membership proofs from uniform families of polynomials over a finite field
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.2307/2586668openalex-snapshot
Discretely ordered modules as a first-order extension of the cutting planes proof system
inferred← citeshttps://doi.org/10.26456/mfcsics-21-9openalex-snapshot
Несколько слов о сложности доказательств
inferred← citeshttps://doi.org/10.3233/faia200990openalex-snapshot
Chapter 7. Proof Complexity and SAT Solving
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2016.32openalex-snapshot
Proof Complexity Lower Bounds from Algebraic Circuit Complexity
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2021.21openalex-snapshot
A Lower Bound for Polynomial Calculus with Extension Rule
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.1607.00443openalex-snapshot
Algebraic Proof Complexity: Progress, Frontiers and Challenges
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.