Branching Process Approach for 2-Sat Thresholds (Q4933200): Difference between revisions

@@ Property / cites work @@
+Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
+Normal rank
@@ Property / cites work @@
+The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
+Normal rank
@@ Property / cites work @@
+On the solution-space geometry of random constraint satisfaction problems
+Normal rank
@@ Property / cites work @@
+The ?(2) limit in the random assignment problem
@@ Property / cites work: The ?(2) limit in the random assignment problem / rank @@
+Normal rank
@@ Property / cites work @@
+A linear-time algorithm for testing the truth of certain quantified Boolean formulas
+Normal rank
@@ Property / cites work @@
+Q2743189
@@ Property / cites work: Q2743189 / rank @@
+Normal rank
@@ Property / cites work @@
+The scaling window of the 2-SAT transition
@@ Property / cites work: The scaling window of the 2-SAT transition / rank @@
+Normal rank
@@ Property / cites work @@
+Q4228436
@@ Property / cites work: Q4228436 / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of theorem-proving procedures
@@ Property / cites work: The complexity of theorem-proving procedures / rank @@
+Normal rank
@@ Property / cites work @@
+Random 2-SAT with prescribed literal degrees
@@ Property / cites work: Random 2-SAT with prescribed literal degrees / rank @@
+Normal rank
@@ Property / cites work @@
+On the satisfiability threshold of formulas with three literals per clause
+Normal rank
@@ Property / cites work @@
+The Forwarding Indices of Random Graphs
@@ Property / cites work: The Forwarding Indices of Random Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Correlation inequalities on some partially ordered sets
+Normal rank
@@ Property / cites work @@
+Sharp thresholds of graph properties, and the $k$-sat problem
+Normal rank
@@ Property / cites work @@
+A threshold for unsatisfiability
@@ Property / cites work: A threshold for unsatisfiability / rank @@
+Normal rank
@@ Property / cites work @@
+Q4434438
@@ Property / cites work: Q4434438 / rank @@
+Normal rank
@@ Property / cites work @@
+Sharp thresholds for constraint satisfaction problems and homomorphisms
+Normal rank
@@ Property / cites work @@
+The probabilistic analysis of a greedy satisfiability algorithm
+Normal rank
@@ Property / cites work @@
+Limit theorems for decomposable multi-dimensional Galton-Watson processes
+Normal rank
@@ Property / cites work @@
+A new look at survey propagation and its generalizations
+Normal rank
@@ Property / cites work @@
+Threshold values of random <i>K</i>‐SAT from the cavity method
+Normal rank
@@ Property / cites work @@
+On the hardness of sampling independent sets beyond the tree threshold
+Normal rank
@@ Property / cites work @@
+Random 2-SAT and unsatisfiability
@@ Property / cites work: Random 2-SAT and unsatisfiability / rank @@
+Normal rank
@@ Property / cites work @@
+Counting independent sets up to the tree threshold
+Normal rank