On the public citation graph

Narrow Proofs May Be Maximally Long

0 signed · 110 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.10089openalex-snapshot
Space complexity of random formulae in resolution
inferredcites →https://doi.org/10.1006/inco.2001.2921openalex-snapshot
Space Bounds for Resolution
inferredcites →https://doi.org/10.1007/3-540-45535-3_23openalex-snapshot
An Explicit Exact SDP Relaxation for Nonlinear 0-1 Programs
inferredcites →https://doi.org/10.1007/3-540-45841-7_34openalex-snapshot
Complexity of Semi-algebraic Proofs
inferredcites →https://doi.org/10.1007/978-1-4614-0769-0_6openalex-snapshot
Convex Relaxations and Integrality Gaps
inferredcites →https://doi.org/10.1007/978-3-642-22006-7_53openalex-snapshot
Parameterized Bounded-Depth Frege Is Not Optimal
inferredcites →https://doi.org/10.1007/978-3-642-39206-1_37openalex-snapshot
Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds
inferredcites →https://doi.org/10.1007/bf01744431openalex-snapshot
Parity, circuits, and the polynomial-time hierarchy
inferredcites →https://doi.org/10.1007/s000370050013openalex-snapshot
Lower bounds for the polynomial calculus
inferredcites →https://doi.org/10.1007/s000370050024openalex-snapshot
Lower bounds for the polynomial calculus and the Gröbner basis algorithm
inferredcites →https://doi.org/10.1007/s000370100000openalex-snapshot
Optimality of size-width tradeoffs for resolution
inferredcites →https://doi.org/10.1016/0012-365x(73)90167-2openalex-snapshot
Edmonds polytopes and a hierarchy of combinatorial problems
inferredcites →https://doi.org/10.1016/0166-218x(87)90039-4openalex-snapshot
On the complexity of cutting-plane proofs
inferredcites →https://doi.org/10.1016/0304-3975(85)90144-6openalex-snapshot
The intractability of resolution
inferredcites →https://doi.org/10.1016/j.apal.2013.10.009openalex-snapshot
Relativization makes contradictions harder for Resolution
inferredcites →https://doi.org/10.1016/j.jcss.2007.06.025openalex-snapshot
A combinatorial characterization of resolution width
inferredcites →https://doi.org/10.1016/j.jpaa.2008.11.043openalex-snapshot
New developments in the theory of Gröbner bases and applications to formal verification
inferredcites →https://doi.org/10.1016/j.jsc.2008.02.017openalex-snapshot
PolyBoRi: A framework for Gröbner-basis computations with Boolean polynomials
inferredcites →https://doi.org/10.1016/j.tcs.2009.01.002openalex-snapshot
Tight rank lower bounds for the Sherali–Adams proof system
inferredcites →https://doi.org/10.1016/s0168-0072(01)00055-0openalex-snapshot
Complexity of Null- and Positivstellensatz proofs
inferredcites →https://doi.org/10.1016/s0304-3975(00)00157-2openalex-snapshot
Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
inferredcites →https://doi.org/10.1016/s0304-3975(03)00395-5openalex-snapshot
Mutilated chessboard problem is exponentially hard for resolution
inferredcites →https://doi.org/10.1017/cbo9781107325944.010openalex-snapshot
On the Complexity of the Propositional Calculus
inferredcites →https://doi.org/10.1080/00029890.2000.12005233openalex-snapshot
Proofs as Games
inferredcites →https://doi.org/10.1109/12.769433openalex-snapshot
GRASP: a search algorithm for propositional satisfiability
inferredcites →https://doi.org/10.1109/ccc.2013.20openalex-snapshot
Lower Bounds for DNF-refutations of a Relativized Weak Pigeonhole Principle
inferredcites →https://doi.org/10.1109/ccc.2014.36openalex-snapshot
Narrow Proofs May Be Maximally Long
inferredcites →https://doi.org/10.1109/focs.2008.42openalex-snapshot
Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution
inferredcites →https://doi.org/10.1109/focs.2008.74openalex-snapshot
Linear Level Lasserre Lower Bounds for Certain k-CSPs
inferredcites →https://doi.org/10.1109/focs.2012.48openalex-snapshot
On the Complexity of Finding Narrow Proofs
inferredcites →https://doi.org/10.1109/focs.2014.74openalex-snapshot
Total Space in Resolution
inferredcites →https://doi.org/10.1109/sfcs.2001.959893openalex-snapshot
Lower bounds for polynomial calculus: non-binomial case
inferredcites →https://doi.org/10.1109/sfcs.2001.959896openalex-snapshot
"Planar" tautologies hard for resolution
inferredcites →https://doi.org/10.1137/0206031openalex-snapshot
On Resolution with Clauses of Bounded Size
inferredcites →https://doi.org/10.1137/0403036openalex-snapshot
A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
inferredcites →https://doi.org/10.1137/060654645openalex-snapshot
Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
inferredcites →https://doi.org/10.1137/0801013openalex-snapshot
Cones of Matrices and Set-Functions and 0–1 Optimization
inferredcites →https://doi.org/10.1137/080723880openalex-snapshot
Size-Space Tradeoffs for Resolution
inferredcites →https://doi.org/10.1137/120895950openalex-snapshot
Space Complexity in Polynomial Calculus
inferredcites →https://doi.org/10.1137/s0097539700366735openalex-snapshot
Space Complexity in Propositional Calculus
inferredcites →https://doi.org/10.1145/2213977.2213999openalex-snapshot
Time-space tradeoffs in resolution
inferredcites →https://doi.org/10.1145/2213977.2214006openalex-snapshot
Hypercontractivity, sum-of-squares proofs, and their applications
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/2488608.2488711openalex-snapshot
Some trade-off results for polynomial calculus
inferredcites →https://doi.org/10.1145/2499937.2499941openalex-snapshot
Parameterized Complexity of DPLL Search Procedures
inferredcites →https://doi.org/10.1145/2591796.2591838openalex-snapshot
Communication lower bounds via critical block sensitivity
inferredcites →https://doi.org/10.1145/2699438openalex-snapshot
A Framework for Space Complexity in Algebraic Proof Systems
inferredcites →https://doi.org/10.1145/375827.375835openalex-snapshot
Short proofs are narrow—resolution made simple
inferredcites →https://doi.org/10.1145/378239.379017openalex-snapshot
Chaff
inferredcites →https://doi.org/10.1145/48014.48016openalex-snapshot
Many hard examples for resolution
inferredcites →https://doi.org/10.1145/7531.8928openalex-snapshot
Hard examples for resolution
inferredcites →https://doi.org/10.1287/moor.28.3.470.16391openalex-snapshot
A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
inferredcites →https://doi.org/10.2307/2267634openalex-snapshot
Archie Blake. Canonical expressions in Boolean algebra. Dissertation Chicago 1937. Lithographed. The University of Chicago Libraries, Chicago1938, ii + 60 pp.
inferredcites →https://doi.org/10.2307/2273702openalex-snapshot
The relative efficiency of propositional proof systems
inferredcites →https://doi.org/10.2307/3006767openalex-snapshot
Recent Advances in Mathematical Programming
inferredcites →https://doi.org/10.48550/arxiv.1409.2731openalex-snapshot
Narrow Proofs May Be Maximally Long
inferredcites →https://doi.org/10.5555/2627817.2627928openalex-snapshot
Approximability and proof complexity
inferredcites →https://doi.org/10.5555/2833227.2833250openalex-snapshot
Tight size-degree bounds for sums-of-squares proofs
inferredcites →https://doi.org/10.7907/2k6y-ch43.openalex-snapshot
Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization

What points at this work

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

inferred← citeshttps://doi.org/10.1007/978-3-030-24258-9_1openalex-snapshot
Circular (Yet Sound) 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-031-10769-6_8openalex-snapshot
Preprocessing of Propagation Redundant Clauses
inferred← citeshttps://doi.org/10.1007/978-3-031-24950-1_12openalex-snapshot
CosySEL: Improving SAT Solving Using Local Symmetries
inferred← citeshttps://doi.org/10.1007/s00037-017-0152-4openalex-snapshot
Tight Size-Degree Bounds for Sums-of-Squares Proofs
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/s10817-023-09681-3openalex-snapshot
Preprocessing of Propagation Redundant Clauses
inferred← citeshttps://doi.org/10.1017/9781108242066openalex-snapshot
Proof Complexity
inferred← citeshttps://doi.org/10.1017/9781108242066.001openalex-snapshot
Preface
inferred← citeshttps://doi.org/10.1017/9781108242066.002openalex-snapshot
Introduction
inferred← citeshttps://doi.org/10.1017/9781108242066.003openalex-snapshot
Concepts and Problems
inferred← citeshttps://doi.org/10.1017/9781108242066.004openalex-snapshot
Frege Systems
inferred← citeshttps://doi.org/10.1017/9781108242066.005openalex-snapshot
Sequent Calculus
inferred← citeshttps://doi.org/10.1017/9781108242066.006openalex-snapshot
Quantified Propositional Calculus
inferred← citeshttps://doi.org/10.1017/9781108242066.007openalex-snapshot
Resolution
inferred← citeshttps://doi.org/10.1017/9781108242066.008openalex-snapshot
Algebraic and Geometric Proof Systems
inferred← citeshttps://doi.org/10.1017/9781108242066.009openalex-snapshot
Further 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.015openalex-snapshot
R and R-Like Proof Systems
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.021openalex-snapshot
Hard Tautologies
inferred← citeshttps://doi.org/10.1017/9781108242066.022openalex-snapshot
Model Theory and Lower Bounds
inferred← citeshttps://doi.org/10.1017/9781108242066.023openalex-snapshot
Optimality
inferred← citeshttps://doi.org/10.1017/9781108242066.024openalex-snapshot
The Nature of Proof Complexity
inferred← citeshttps://doi.org/10.1017/9781108242066.025openalex-snapshot
Bibliography
inferred← citeshttps://doi.org/10.1017/9781108242066.026openalex-snapshot
Index
inferred← citeshttps://doi.org/10.1109/focs.2019.00038openalex-snapshot
Automating Resolution is NP-Hard
inferred← citeshttps://doi.org/10.1109/focs54457.2022.00111openalex-snapshot
Separations in Proof Complexity and TFNP
inferred← citeshttps://doi.org/10.1137/16m1109072openalex-snapshot
Supercritical Space-Width Trade-offs for Resolution
inferred← citeshttps://doi.org/10.1137/20m134784xopenalex-snapshot
Proof Complexity and the Binary Encoding of Combinatorial Principles
inferred← citeshttps://doi.org/10.1145/3265985openalex-snapshot
Proof Complexity Meets Algebra
inferred← citeshttps://doi.org/10.1145/3565363openalex-snapshot
MaxSAT Resolution and Subcube Sums
inferred← citeshttps://doi.org/10.1145/3579997openalex-snapshot
Circular (Yet Sound) Proofs in Propositional Logic
inferred← citeshttps://doi.org/10.1145/3663758openalex-snapshot
Separations in Proof Complexity and TFNP
inferred← citeshttps://doi.org/10.1609/aaai.v34i02.5508openalex-snapshot
A Cardinal Improvement to Pseudo-Boolean Solving
inferred← citeshttps://doi.org/10.1613/jair.1.15075openalex-snapshot
Weighted, Circular and Semi-Algebraic Proofs
inferred← citeshttps://doi.org/10.3233/faia200990openalex-snapshot
Chapter 7. Proof Complexity and SAT Solving
inferred← citeshttps://doi.org/10.4086/toc.2016.v012a005openalex-snapshot
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2021.6openalex-snapshot
On the Power and Limitations of Branch and Cut
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2016.56openalex-snapshot
Total Space in Resolution Is at Least Width Squared
inferred← citeshttps://doi.org/10.5555/2833227.2833250openalex-snapshot
Tight size-degree bounds for sums-of-squares proofs
inferred← citeshttps://doi.org/10.5821/dissertation-2117-366561openalex-snapshot
Size bounds for algebraic and semialgebraic proof systems
inferred← citeshttps://doi.org/10.70675/e9194529z1a88z456cz8da5z000c1ce8594dopenalex-snapshot
Contributions to SAT Solving
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.