On the public citation graph

Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems

0 signed · 63 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/(sici)1098-2418(199701/03)10:1/2<5::aid-rsa2>3.0.co;2-zopenalex-snapshot
Algorithmic theory of random graphs
inferredcites →https://doi.org/10.1002/(sici)1098-2418(199810/12)13:3/4<457::aid-rsa14>3.0.co;2-wopenalex-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.1006/jagm.1995.1034openalex-snapshot
Coloring Random and Semi-Random k-Colorable Graphs
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-61310-2_26openalex-snapshot
Coloring bipartite hypergraphs
inferredcites →https://doi.org/10.1007/978-1-4612-0865-5_26openalex-snapshot
Probability Inequalities for sums of Bounded Random Variables
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.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.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.1109/18.910572openalex-snapshot
Factor graphs and the sum-product algorithm
inferredcites →https://doi.org/10.1109/18.910575openalex-snapshot
Efficient erasure correcting codes
inferredcites →https://doi.org/10.1109/18.910576openalex-snapshot
Improved low-density parity-check codes using irregular graphs
inferredcites →https://doi.org/10.1109/18.910578openalex-snapshot
Design of capacity-approaching irregular low-density parity-check codes
inferredcites →https://doi.org/10.1109/sfcs.2003.1238209openalex-snapshot
Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs
inferredcites →https://doi.org/10.1109/tit.1962.1057683openalex-snapshot
Low-density parity-check codes
inferredcites →https://doi.org/10.1137/s0097539794270248openalex-snapshot
A Spectral Technique for Coloring Random 3-Colorable Graphs
inferredcites →https://doi.org/10.1145/195058.195187openalex-snapshot
A spectral technique for coloring random 3-colorable graphs (preliminary version)
inferredcites →https://doi.org/10.1145/258533.258536openalex-snapshot
Some optimal inapproximability results
inferredcites →https://doi.org/10.1145/276698.276756openalex-snapshot
Analysis of low density codes and improved designs using irregular graphs
inferredcites →https://doi.org/10.1145/3501714.3501727openalex-snapshot
Reverend Bayes on Inference Engines: A Distributed Hierarchical Approach
inferredcites →https://doi.org/10.1145/800157.805047openalex-snapshot
The complexity of theorem-proving procedures
inferredcites →https://doi.org/10.48550/arxiv.cs/0211036openalex-snapshot
Typical random 3-SAT formulae and the satisfiability threshold
inferredcites →https://doi.org/10.5555/1077450.1077456openalex-snapshot
Survey propagation: An algorithm for satisfiability
inferredcites →https://doi.org/10.5555/1109557.1109608openalex-snapshot
Solving random satisfiable 3CNF formulas in expected polynomial time
inferredcites →https://doi.org/10.5555/251040.251043openalex-snapshot
Algorithmic theory of random graphs
inferredcites →https://doi.org/10.5555/313559.313794openalex-snapshot
On the satisfiability and maximum satisfiability of random 3-CNF formulas
inferredcites →https://doi.org/10.5555/644108.644166openalex-snapshot
A spectral technique for random satisfiable 3CNF formulas

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-0-387-30162-4_330openalex-snapshot
Random Planted 3-SAT
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-540-70918-3_11openalex-snapshot
Why Almost All k-Colorable Graphs Are Easy
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-03751-1_5openalex-snapshot
Loopy Substructural Local Search for the Bayesian Optimization Algorithm
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/978-3-662-48054-0_15openalex-snapshot
Phase Transition for Local Search on Planted SAT
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.1007/s10898-019-00749-2openalex-snapshot
Convergence and correctness of belief propagation for the Chinese postman problem
inferred← citeshttps://doi.org/10.1017/s096354830900981xopenalex-snapshot
A Spectral Approach to Analysing Belief Propagation for 3-Colouring
inferred← citeshttps://doi.org/10.1017/s0963548309990356openalex-snapshot
On the Random Satisfiable Process
inferred← citeshttps://doi.org/10.1088/1751-8113/40/5/001openalex-snapshot
Can rare SAT formulae be easily recognized? On the efficiency of message-passing algorithms for K -SAT at large clause-to-variable ratios
inferred← citeshttps://doi.org/10.1103/physreve.79.031102openalex-snapshot
From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
inferred← citeshttps://doi.org/10.1109/tit.2022.3145232openalex-snapshot
Iterative Message Passing Algorithm for Vertex-Disjoint Shortest Paths
inferred← citeshttps://doi.org/10.1137/090750755openalex-snapshot
Quiet Planting in the Locked Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1137/090753115openalex-snapshot
Belief Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
inferred← citeshttps://doi.org/10.1137/1.9781611973082.74openalex-snapshot
On Belief Propagation Guided Decimation for Random k -SAT
inferred← citeshttps://doi.org/10.1145/2213977.2214058openalex-snapshot
Catching the k-NAESAT threshold
inferred← citeshttps://doi.org/10.1214/15-ejs1001openalex-snapshot
Optimal testing for planted satisfiability problems
inferred← citeshttps://doi.org/10.1360/n112016-00248openalex-snapshot
Sufficient conditions for convergence of the survey propagation algorithm
inferred← citeshttps://doi.org/10.1360/n112018-00260openalex-snapshot
A warning propagation algorithm to solve the double-objective minimum spanning tree
inferred← citeshttps://doi.org/10.18178/wcse.2016.06.081openalex-snapshot
Probability Conditions for Convergence of the Warning Propagation Algorithm
inferred← citeshttps://doi.org/10.21248/gups.61061openalex-snapshot
Large discrete structures : statistical inference, combinatorics and limits
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.4086/toc.2013.v009a019openalex-snapshot
inferred← citeshttps://doi.org/10.46298/dmtcs.3538openalex-snapshot
Why almost all satisfiable $k$-CNF formulas are easy
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.0709.1667openalex-snapshot
Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
inferred← citeshttps://doi.org/10.48550/arxiv.0802.1829openalex-snapshot
A review of the Statistical Mechanics approach to Random Optimization Problems
inferred← citeshttps://doi.org/10.48550/arxiv.1504.08316openalex-snapshot
Concentration of the number of solutions of random planted CSPs and Goldreich's one-way candidates
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0508097openalex-snapshot
Tightness of LP via Max-product Belief Propagation
inferred← citeshttps://doi.org/10.5555/2133036.2133110openalex-snapshot
On belief propagation guided decimation for random k-SAT
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.