On the public citation graph
Why almost all satisfiable $k$-CNF formulas are easy
0 signed · 30 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/(sici)1098-2418(199810/12)13:3/4<457::aid-rsa14>3.3.co;2-kopenalex-snapshot
Finding a large hidden clique in a random graph
inferredcites →https://doi.org/10.1002/(sici)1098-2418(200003)16:2<195::aid-rsa5>3.0.co;2-aopenalex-snapshot
Finding and certifying a large hidden clique in a semirandom graph
inferredcites →https://doi.org/10.1002/rsa.20057openalex-snapshot
Survey propagation: An algorithm for satisfiability
inferredcites →https://doi.org/10.1002/rsa.20213openalex-snapshot
A spectral technique for random satisfiable 3CNF formulas
inferredcites →https://doi.org/10.1006/jagm.1995.1034openalex-snapshot
Coloring Random and Semi-Random k-Colorable Graphs
inferredcites →https://doi.org/10.1007/11830924_32openalex-snapshot
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
inferredcites →https://doi.org/10.1007/3-540-08442-8_114openalex-snapshot
Expected Behavior of Graph Coloring Algorithms
inferredcites →https://doi.org/10.1007/3-540-61310-2_26openalex-snapshot
Coloring bipartite hypergraphs
inferredcites →https://doi.org/10.1007/978-1-4612-4808-8_26openalex-snapshot
Average Case Complete Problems
inferredcites →https://doi.org/10.1007/978-3-540-24605-3_2openalex-snapshot
An Algorithm for SAT Above the Threshold
inferredcites →https://doi.org/10.1007/s00224-009-9231-5openalex-snapshot
Why Almost All k-Colorable Graphs Are Easy to Color
inferredcites →https://doi.org/10.1090/s0894-0347-99-00305-7openalex-snapshot
Sharp thresholds of graph properties, and the $k$-sat problem
inferredcites →https://doi.org/10.1103/physrevlett.94.197205openalex-snapshot
Clustering of Solutions in the Random Satisfiability Problem
inferredcites →https://doi.org/10.1137/s0097539794270248openalex-snapshot
A Spectral Technique for Coloring Random 3-Colorable Graphs
inferredcites →https://doi.org/10.1145/1109557.1109608openalex-snapshot
Solving random satisfiable 3CNF formulas in expected polynomial time
inferredcites →https://doi.org/10.1145/1132516.1132537openalex-snapshot
On the solution-space geometry of random constraint satisfaction problems
inferredcites →https://doi.org/10.1145/258533.258536openalex-snapshot
Some optimal inapproximability results
inferredcites →https://doi.org/10.1145/509984.509985openalex-snapshot
Relations between average case complexity and approximation complexity
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-319-09284-3_28openalex-snapshot
Approximating Highly Satisfiable Random 2-SAT
inferred← citeshttps://doi.org/10.1007/978-3-319-45741-3_3openalex-snapshot
On Manufacturing Resilient Opaque Constructs Against Static Analysis
inferred← citeshttps://doi.org/10.1007/978-3-642-40328-6_24openalex-snapshot
Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration
inferred← citeshttps://doi.org/10.1007/s00224-009-9231-5openalex-snapshot
Why Almost All k-Colorable Graphs Are Easy to Color
inferred← citeshttps://doi.org/10.1016/j.artint.2009.06.005openalex-snapshot
Data reductions, fixed parameter tractability, and random weighted d-CNF satisfiability
inferred← citeshttps://doi.org/10.1017/s0963548309990356openalex-snapshot
On the Random Satisfiable Process
inferred← citeshttps://doi.org/10.1214/15-ejs1001openalex-snapshot
Optimal testing for planted satisfiability problems
inferred← citeshttps://doi.org/10.48550/arxiv.0806.4652openalex-snapshot
A Fixed-Parameter Algorithm for Random Instances of Weighted d-CNF Satisfiability
inferred← citeshttps://doi.org/10.48550/arxiv.1008.1260openalex-snapshot
Structure of random r-SAT below the pure literal threshold
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.