On the public citation graph

A spectral technique for random satisfiable 3CNF formulas

0 signed · 59 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.1007/3-540-45446-2_21openalex-snapshot
Coupon Collectors, q-Binomial Coefficients and the Unsatisfiability Threshold
inferredcites →https://doi.org/10.1007/3-540-45749-6_51openalex-snapshot
The Probabilistic Analysis of a Greedy Satisfiability Algorithm
inferredcites →https://doi.org/10.1007/3-540-45841-7_15openalex-snapshot
A Probabilistic 3—SAT Algorithm Further Improved
inferredcites →https://doi.org/10.1007/3-540-48224-5_26openalex-snapshot
Recognizing More Unsatisfiable Random 3-SAT Instances Efficiently
inferredcites →https://doi.org/10.1007/3-540-61310-2_26openalex-snapshot
Coloring bipartite hypergraphs
inferredcites →https://doi.org/10.1016/0004-3702(95)00046-1openalex-snapshot
Experimental results on the crossover point in random 3-SAT
inferredcites →https://doi.org/10.1016/0020-0190(92)90029-uopenalex-snapshot
On the greedy algorithm for satisfiability
inferredcites →https://doi.org/10.1016/c2009-0-09109-0openalex-snapshot
Combinatorial Problems and Exercises
inferredcites →https://doi.org/10.1103/physrevlett.88.188701openalex-snapshot
Hiding Solutions in Random Satisfiability Problems: A Statistical Mechanics Approach
inferredcites →https://doi.org/10.1109/sfcs.2003.1238204openalex-snapshot
More on average case vs approximation complexity
inferredcites →https://doi.org/10.1109/sffcs.1999.814612openalex-snapshot
A probabilistic algorithm for k-SAT and constraint satisfaction problems
inferredcites →https://doi.org/10.1137/s0097539794270248openalex-snapshot
A Spectral Technique for Coloring Random 3-Colorable Graphs
inferredcites →https://doi.org/10.1145/375827.375835openalex-snapshot
Short proofs are narrow—resolution made simple
inferredcites →https://doi.org/10.1145/48014.48016openalex-snapshot
Many hard examples for resolution
inferredcites →https://doi.org/10.1145/509907.509985openalex-snapshot
Relations between average case complexity and approximation complexity
inferredcites →https://doi.org/10.1145/73007.73063openalex-snapshot
On the second eigenvalue of random regular graphs
inferredcites →https://doi.org/10.1145/800157.805047openalex-snapshot
The complexity of theorem-proving procedures

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.20089openalex-snapshot
Spectral techniques applied to sparse random graphs
inferred← citeshttps://doi.org/10.1002/rsa.20116openalex-snapshot
A spectral heuristic for bisecting random graphs
inferred← citeshttps://doi.org/10.1002/rsa.20213openalex-snapshot
A spectral technique for random satisfiable 3CNF formulas
inferred← citeshttps://doi.org/10.1007/11538462_24openalex-snapshot
Finding a Maximum Independent Set in a Sparse Random Graph
inferred← citeshttps://doi.org/10.1007/11786986_60openalex-snapshot
An Adaptive Spectral Heuristic for Partitioning Random Graphs
inferred← citeshttps://doi.org/10.1007/11830924_32openalex-snapshot
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
inferred← citeshttps://doi.org/10.1007/978-0-387-09680-3_9openalex-snapshot
Partitioning Random Graphs with General Degree Distributions
inferred← citeshttps://doi.org/10.1007/978-0-387-30162-4_330openalex-snapshot
Random Planted 3-SAT
inferred← citeshttps://doi.org/10.1007/978-0-387-34735-6_22openalex-snapshot
Spectral Partitioning of Random Graphs with Given Expected Degrees
inferred← citeshttps://doi.org/10.1007/978-3-030-80223-3_13openalex-snapshot
Solving Non-uniform Planted and Filtered Random SAT Formulas Greedily
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-540-24605-3_2openalex-snapshot
An Algorithm for SAT Above the Threshold
inferred← citeshttps://doi.org/10.1007/978-3-540-27821-4_28openalex-snapshot
Strong Refutation Heuristics for Random k-SAT
inferred← citeshttps://doi.org/10.1007/978-3-540-30551-4_42openalex-snapshot
On the Hardness and Easiness of Random 4-SAT Formulas
inferred← citeshttps://doi.org/10.1007/978-3-540-70918-3_11openalex-snapshot
Why Almost All k-Colorable Graphs Are Easy
inferred← citeshttps://doi.org/10.1007/978-3-540-74510-5_8openalex-snapshot
Pushing Random Walk Beyond Golden Ratio
inferred← citeshttps://doi.org/10.1007/978-3-540-77120-3_12openalex-snapshot
A Spectral Method for MAX2SAT in the Planted Solution Model
inferred← citeshttps://doi.org/10.1007/978-3-642-02777-2_26openalex-snapshot
A Theoretical Analysis of Search in GSAT
inferred← citeshttps://doi.org/10.1007/978-3-642-03685-9_30openalex-snapshot
On the Security of Goldreich’s One-Way Function
inferred← citeshttps://doi.org/10.1007/978-3-662-48054-0_15openalex-snapshot
Phase Transition for Local Search on Planted SAT
inferred← citeshttps://doi.org/10.1007/s00037-011-0029-xopenalex-snapshot
More on Average Case vs Approximation Complexity
inferred← citeshttps://doi.org/10.1007/s00037-011-0034-0openalex-snapshot
On the security of Goldreich’s one-way function
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.1016/j.ipl.2008.04.011openalex-snapshot
On the tractability of coloring semirandom graphs
inferred← citeshttps://doi.org/10.1017/s096354830600784xopenalex-snapshot
Strong Refutation Heuristics for Random k -SAT
inferred← citeshttps://doi.org/10.1017/s0963548306008182openalex-snapshot
On the Expansion of the Giant Component in Percolated (n, d,λ) Graphs
inferred← citeshttps://doi.org/10.1017/s0963548309990356openalex-snapshot
On the Random Satisfiable Process
inferred← citeshttps://doi.org/10.1109/sfcs.2003.1238204openalex-snapshot
More on average case vs approximation complexity
inferred← citeshttps://doi.org/10.1109/tit.2016.2637959openalex-snapshot
On the Limitation of Spectral Methods: From the Gaussian Hidden Clique Problem to Rank One Perturbations of Gaussian Tensors
inferred← citeshttps://doi.org/10.1137/070699354openalex-snapshot
Finding Planted Partitions in Random Graphs with General Degree Distributions
inferred← citeshttps://doi.org/10.1137/090749323openalex-snapshot
On the Diameter of the Set of Satisfying Assignments in Random Satisfiable k-CNF Formulas
inferred← citeshttps://doi.org/10.1137/1.9781611972962.4openalex-snapshot
Semirandom Models as Benchmarks for Coloring Algorithms
inferred← citeshttps://doi.org/10.1145/2746539.2746577openalex-snapshot
On the Complexity of Random Satisfiability Problems with Planted Solutions
inferred← citeshttps://doi.org/10.1145/2897518.2897561openalex-snapshot
On the effect of randomness on planted 3-coloring models
inferred← citeshttps://doi.org/10.1214/15-ejs1001openalex-snapshot
Optimal testing for planted satisfiability problems
inferred← citeshttps://doi.org/10.3233/sat190033openalex-snapshot
It’s All about the Support: A New Perspective on the Satisfiability Problem
inferred← citeshttps://doi.org/10.4204/eptcs.9.4openalex-snapshot
Random Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.46298/dmtcs.3546openalex-snapshot
Message passing for the coloring problem: Gallager meets Alon and Kahale
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.1603.05183openalex-snapshot
On the effect of randomness on planted 3-coloring models
inferred← citeshttps://doi.org/10.5555/1109557.1109608openalex-snapshot
Solving random satisfiable 3CNF formulas in expected polynomial time
inferred← citeshttps://doi.org/10.82444/warw.33656560openalex-snapshot
On smoothed k-CNF formulas and the Walksat algorithm
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.