On the public citation graph

Space complexity of random formulae in resolution

0 signed · 67 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/1098-2418(200009)17:2<103::aid-rsa2>3.0.co;2-popenalex-snapshot
Bounding the unsatisfiability threshold of random 3-SAT
inferredcites →https://doi.org/10.1007/3-540-48168-0_26openalex-snapshot
Lower Bounds for Space in Resolution
inferredcites →https://doi.org/10.1016/0304-3975(85)90144-6openalex-snapshot
The intractability of resolution
inferredcites →https://doi.org/10.1109/sfcs.1996.548486openalex-snapshot
Simplified and improved resolution lower bounds
inferredcites →https://doi.org/10.1137/s0097539700366735openalex-snapshot
Space Complexity in Propositional Calculus
inferredcites →https://doi.org/10.1137/s0097539700369156openalex-snapshot
The Efficiency of Resolution and Davis--Putnam Procedures
inferredcites →https://doi.org/10.1145/276698.276870openalex-snapshot
On the complexity of unsatisfiability proofs for random k-CNF formulas
inferredcites →https://doi.org/10.1145/301250.301392openalex-snapshot
Short proofs are narrow—resolution made simple
inferredcites →https://doi.org/10.1145/335305.335309openalex-snapshot
Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
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.2307/2273702openalex-snapshot
The relative efficiency of propositional proof systems
inferredcites →https://doi.org/10.48550/arxiv.cs/0211036openalex-snapshot
Typical random 3-SAT formulae and the satisfiability threshold

What points at this work

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

inferred← citeshttps://doi.org/10.1002/rsa.21168openalex-snapshot
The impact of heterogeneity and geometry on the proof complexity of random satisfiability
inferred← citeshttps://doi.org/10.1007/11538462_34openalex-snapshot
A Generating Function Method for the Average-Case Analysis of DPLL
inferred← citeshttps://doi.org/10.1007/978-3-030-51825-7_14openalex-snapshot
Simplified and Improved Separations Between Regular and General Resolution by Lifting
inferred← citeshttps://doi.org/10.1007/978-3-319-09284-3_1openalex-snapshot
A (Biased) Proof Complexity Survey for SAT Practitioners
inferred← citeshttps://doi.org/10.1007/978-3-319-40970-2_11openalex-snapshot
Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers
inferred← citeshttps://doi.org/10.1007/978-3-642-13562-0_6openalex-snapshot
Different Approaches to Proof Systems
inferred← citeshttps://doi.org/10.1007/978-3-642-22006-7_54openalex-snapshot
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution
inferred← citeshttps://doi.org/10.1007/978-3-642-33558-7_25openalex-snapshot
Relating Proof Complexity Measures and Practical Hardness of SAT
inferred← citeshttps://doi.org/10.1007/978-3-642-39206-1_37openalex-snapshot
Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds
inferred← citeshttps://doi.org/10.1007/s00037-025-00266-7openalex-snapshot
Pseudo-Deterministic Query Complexity of Search Problems
inferred← citeshttps://doi.org/10.1016/j.ic.2017.06.003openalex-snapshot
Space proof complexity for random 3-CNFs
inferred← citeshttps://doi.org/10.1016/j.ipl.2009.06.006openalex-snapshot
A simplified way of proving trade-off results for resolution
inferred← citeshttps://doi.org/10.1016/j.ipl.2018.04.007openalex-snapshot
On semantic cutting planes with very small coefficients
inferred← citeshttps://doi.org/10.1016/j.jcss.2007.06.025openalex-snapshot
A combinatorial characterization of resolution width
inferred← citeshttps://doi.org/10.1016/j.tcs.2004.04.004openalex-snapshot
On the complexity of resolution with bounded conjunctions
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.1109/ccc.2010.22openalex-snapshot
On the Relative Strength of Pebbling and Resolution
inferred← citeshttps://doi.org/10.1109/ccc.2012.27openalex-snapshot
Space Complexity in Polynomial Calculus
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/ccc.2014.36openalex-snapshot
Narrow Proofs May Be Maximally Long
inferred← citeshttps://doi.org/10.1109/focs.2008.42openalex-snapshot
Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution
inferred← citeshttps://doi.org/10.1109/focs.2014.74openalex-snapshot
Total Space in Resolution
inferred← citeshttps://doi.org/10.1109/focs.2019.00081openalex-snapshot
Polynomial Calculus Space and Resolution Width
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/icaica50127.2020.9182436openalex-snapshot
Computing Method about the Optimal Spontaneous Fission Quantity of Agent during Ultra High Frequency High-Dimensional Linear Computing
inferred← citeshttps://doi.org/10.1137/060668250openalex-snapshot
Narrow Proofs May Be Spacious:Separating Space and Width in Resolution
inferred← citeshttps://doi.org/10.1137/080723880openalex-snapshot
Size-Space Tradeoffs for Resolution
inferred← citeshttps://doi.org/10.1137/1.9781611976465.4openalex-snapshot
The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability
inferred← citeshttps://doi.org/10.1137/120895950openalex-snapshot
Space Complexity in Polynomial Calculus
inferred← citeshttps://doi.org/10.1137/15m1023269openalex-snapshot
Total Space in Resolution
inferred← citeshttps://doi.org/10.1137/16m1109072openalex-snapshot
Supercritical Space-Width Trade-offs for Resolution
inferred← citeshttps://doi.org/10.1145/1132516.1132590openalex-snapshot
Narrow proofs may be spacious
inferred← citeshttps://doi.org/10.1145/1374376.1374478openalex-snapshot
Towards an optimal separation of space and length in resolution
inferred← citeshttps://doi.org/10.1145/2159531.2159538openalex-snapshot
On the Relative Strength of Pebbling and Resolution
inferred← citeshttps://doi.org/10.1145/2213977.2214000openalex-snapshot
On the virtue of succinct proofs
inferred← citeshttps://doi.org/10.1145/2422436.2422486openalex-snapshot
Pseudo-partitions, transversality and locality
inferred← citeshttps://doi.org/10.1145/2488608.2488711openalex-snapshot
Some trade-off results for polynomial calculus
inferred← citeshttps://doi.org/10.1145/2699438openalex-snapshot
A Framework for Space Complexity in Algebraic Proof Systems
inferred← citeshttps://doi.org/10.1145/2746339openalex-snapshot
From Small Space to Small Width in Resolution
inferred← citeshttps://doi.org/10.1145/2815493.2815497openalex-snapshot
On the interplay between proof complexity and SAT solving
inferred← citeshttps://doi.org/10.1145/2898435openalex-snapshot
Narrow Proofs May Be Maximally Long
inferred← citeshttps://doi.org/10.1145/509907.509975openalex-snapshot
Size space tradeoffs for resolution
inferred← citeshttps://doi.org/10.14288/1.0043897openalex-snapshot
Mini-tutorial on weak proof systems and connections to SAT solving
inferred← citeshttps://doi.org/10.3233/faia200990openalex-snapshot
Chapter 7. Proof Complexity and SAT Solving
inferred← citeshttps://doi.org/10.4036/iis.2015.l.02openalex-snapshot
An Introduction to Lower Bounds on Resolution Proof Systems
inferred← citeshttps://doi.org/10.4086/toc.2013.v009a014openalex-snapshot
inferred← citeshttps://doi.org/10.4230/dagsemproc.08381.6openalex-snapshot
Understanding space in resolution: optimal lower bounds and exponential trade-offs
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.48550/arxiv.0803.0661openalex-snapshot
Towards an Optimal Separation of Space and Length in Resolution
inferred← citeshttps://doi.org/10.48550/arxiv.1008.1789openalex-snapshot
Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions
inferred← citeshttps://doi.org/10.48550/arxiv.1411.1619openalex-snapshot
Space proof complexity for random $3$-CNFs via a $(2-ε)$-Hall's Theorem
inferred← citeshttps://doi.org/10.5555/2833227.2833249openalex-snapshot
The space complexity of cutting planes refutations
inferred← citeshttps://doi.org/10.5821/dissertation-2117-94931openalex-snapshot
On the complexity of resolution-based proof systems
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.