On the public citation graph
Minimum propositional proof length is NP-hard to linearly approximate
0 signed · 54 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.1006/jcss.1997.1472openalex-snapshot
The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations
inferredcites →https://doi.org/10.1007/3-540-60178-3_86openalex-snapshot
Some consequences of cryptographical conjectures for S 2 1 and EF
inferredcites →https://doi.org/10.1007/3-540-63307-3_70openalex-snapshot
Intractability of assembly sequencing: Unit disks in the plane
inferredcites →https://doi.org/10.1007/978-1-4612-2566-9_4openalex-snapshot
On Gödel’s Theorems on Lengths of Proofs II: Lower Bounds for Recognizing k Symbol Provability
inferredcites →https://doi.org/10.1007/bf02391554openalex-snapshot
Some remarks on lengths of propositional proofs
inferredcites →https://doi.org/10.1007/bfb0029974openalex-snapshot
Complexity of finding short resolution proofs
inferredcites →https://doi.org/10.1016/j.ipl.2003.11.007openalex-snapshot
On the hardness of approximating label-cover
inferredcites →https://doi.org/10.1016/s0049-237x(09)70442-2openalex-snapshot
Complexity of Derivations from Quantifier-Free Horn Formulae, Mechanical Introduction of Explicit Definitions, and Refinement of Completeness Theorems
inferredcites →https://doi.org/10.1109/ccc.1997.612323openalex-snapshot
Constraint satisfaction: the approximability of minimization problems
inferredcites →https://doi.org/10.1109/sfcs.1996.548486openalex-snapshot
Simplified and improved resolution lower bounds
inferredcites →https://doi.org/10.1109/sfcs.1997.646114openalex-snapshot
No feasible interpolation for TC/sup 0/-Frege 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.1145/167088.167174openalex-snapshot
Efficient probabilistically checkable proofs and applications to approximations
inferredcites →https://doi.org/10.1145/185675.306789openalex-snapshot
On the hardness of approximating minimization problems
inferredcites →https://doi.org/10.1145/195058.195467openalex-snapshot
Efficient probabilistic checkable proofs and applications to approximation
inferredcites →https://doi.org/10.1145/230514.571641openalex-snapshot
SIGACT News Complexity Theory Column 12
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/237814.237977openalex-snapshot
A threshold of ln n for approximating set cover (preliminary version)
inferredcites →https://doi.org/10.1145/258533.258641openalex-snapshot
A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP
inferredcites →https://doi.org/10.1145/261342.571216openalex-snapshot
Approximation Algorithms for NP-Hard Problems
inferredcites →https://doi.org/10.1145/285055.285059openalex-snapshot
A threshold of ln n for approximating set cover
inferredcites →https://doi.org/10.2307/2273702openalex-snapshot
The relative efficiency of propositional proof systems
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/11814948_6openalex-snapshot
Minimum Witnesses for Unsatisfiable 2CNFs
inferred← citeshttps://doi.org/10.1007/3-540-36184-7_7openalex-snapshot
On Determining the Minimum Length, Tree-Like Resolution Refutation of 2SAT, and Extended 2SAT Formulas
inferred← citeshttps://doi.org/10.1007/3-540-44985-x_20openalex-snapshot
Approximation Algorithms for the Label-Cover MAX and Red-Blue Set Cover Problems
inferred← citeshttps://doi.org/10.1007/978-3-030-14812-6_36openalex-snapshot
Read-Once Certification of Linear Infeasibility in UTVPI Constraints
inferred← citeshttps://doi.org/10.1007/978-3-031-71294-4_6openalex-snapshot
A Certifying Algorithm for Linear (and Integer) Feasibility in Horn Constraint Systems
inferred← citeshttps://doi.org/10.1007/978-3-319-25150-9_20openalex-snapshot
A Graphical Theorem of the Alternative for UTVPI Constraints
inferred← citeshttps://doi.org/10.1007/978-3-540-79309-0_13openalex-snapshot
Frugal Routing on Wireless Ad-Hoc Networks
inferred← citeshttps://doi.org/10.1007/s00037-011-0014-4openalex-snapshot
PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability
inferred← citeshttps://doi.org/10.1007/s00165-011-0186-3openalex-snapshot
Improved algorithms for optimal length resolution refutation in difference constraint systems
inferred← citeshttps://doi.org/10.1007/s00453-019-00554-zopenalex-snapshot
A Polynomial Time Algorithm for Read-Once Certification of Linear Infeasibility in UTVPI Constraints
inferred← citeshttps://doi.org/10.1007/s10472-022-09800-7openalex-snapshot
On the lengths of tree-like and Dag-like cutting plane refutations of Horn constraint systems
inferred← citeshttps://doi.org/10.1007/s10817-009-9139-4openalex-snapshot
Optimal Length Resolution Refutations of Difference Constraint Systems
inferred← citeshttps://doi.org/10.1016/j.comgeo.2024.102148openalex-snapshot
Parameterized inapproximability of Morse matching
inferred← citeshttps://doi.org/10.1016/j.dam.2020.10.016openalex-snapshot
Polynomial time algorithms for optimal length tree-like refutations of linear infeasibility in UTVPI constraints
inferred← citeshttps://doi.org/10.1016/j.disopt.2012.11.001openalex-snapshot
A combinatorial algorithm for Horn programs
inferred← citeshttps://doi.org/10.1016/j.ipl.2003.11.007openalex-snapshot
On the hardness of approximating label-cover
inferred← citeshttps://doi.org/10.1016/s0166-218x(02)00408-0openalex-snapshot
On the limit of branching rules for hard random unsatisfiable 3-SAT
inferred← citeshttps://doi.org/10.1017/s096012952000016xopenalex-snapshot
NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability
inferred← citeshttps://doi.org/10.1017/s0960129523000300openalex-snapshot
Constrained read-once refutations in UTVPI constraint systems: A parallel perspective
inferred← citeshttps://doi.org/10.1109/sfcs.1998.743514openalex-snapshot
Exponential separations between restricted resolution and cutting planes proof systems
inferred← citeshttps://doi.org/10.1109/sfcs.2001.959895openalex-snapshot
Resolution is not automatizable unless W[P] is tractable
inferred← citeshttps://doi.org/10.1109/sffcs.1999.814619openalex-snapshot
Hardness of approximating Σ/sub 2//sup p/ minimization problems
inferred← citeshttps://doi.org/10.1145/568425.568432openalex-snapshot
SIGACT news complexity theory column 34
inferred← citeshttps://doi.org/10.1145/601819.601829openalex-snapshot
SIGACT news complexity theory column 38
inferred← citeshttps://doi.org/10.1145/976706.976711openalex-snapshot
Optimal length tree-like resolution refutations for 2SAT formulas
inferred← citeshttps://doi.org/10.1155/2011/895398openalex-snapshot
VCG with Communities on Random Ad Hoc Networks
inferred← citeshttps://doi.org/10.1613/jair.1.12278openalex-snapshot
Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics
inferred← citeshttps://doi.org/10.2307/2694916openalex-snapshot
Minimum propositional proof length is NP-hard to linearly approximate
inferred← citeshttps://doi.org/10.3233/sat190066openalex-snapshot
Algorithms and Complexity Results for Input and Unit Resolution
inferred← citeshttps://doi.org/10.33915/etd.3843openalex-snapshot
Analyzing Satisfiability and Refutability in Selected Constraint Systems
inferred← citeshttps://doi.org/10.5555/338219.338271openalex-snapshot
On the red-blue set cover problem
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.