Sharp thresholds of graph properties, and the $k$-sat problem
From MaRDI portal
Publication:4257709
DOI10.1090/S0894-0347-99-00305-7zbMath0932.05084WikidataQ62111470 ScholiaQ62111470MaRDI QIDQ4257709
Publication date: 31 August 1999
Published in: Journal of the American Mathematical Society (Search for Journal in Brave)
Random graphs (graph-theoretic aspects) (05C80) Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.) (42C10)
Related Items (only showing first 100 items - show all)
Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random k-SAT ⋮ GD-SAT model and crossover line ⋮ Continuous phase transitions on Galton–Watson trees ⋮ On the solution‐space geometry of random constraint satisfaction problems ⋮ Storage capacity in symmetric binary perceptrons ⋮ Random Instances of Problems in NP – Algorithms and Statistical Physics ⋮ The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘) ⋮ Random k -SAT and the power of two choices ⋮ Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability ⋮ Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability ⋮ On the concentration of the number of solutions of random satisfiability formulas ⋮ Counting Solutions to Random CNF Formulas ⋮ A proof of the Kahn–Kalai conjecture ⋮ Hypercontractivity for global functions and sharp thresholds ⋮ Biased random k‐SAT ⋮ Running Time Predictions for Factoring Algorithms ⋮ \(\boldsymbol{H}\)-Games Played on Vertex Sets of Random Graphs ⋮ Experiments with automated reasoning in the class ⋮ Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor ⋮ Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022 ⋮ Threshold for Steiner triple systems ⋮ Critical window of the symmetric perceptron ⋮ Hypercontractivity on the symmetric group ⋮ KKL's influence on me ⋮ Sharp thresholds in adaptive random graph processes ⋮ The Sharp Threshold for Maximum-Size Sum-Free Subsets in Even-Order Abelian Groups ⋮ The Satisfiability Threshold fork-XORSAT ⋮ Sharp thresholds for nonlinear Hamiltonian cycles in hypergraphs ⋮ Gibbs states and the set of solutions of random constraint satisfaction problems ⋮ Topological transition in disordered planar matching: combinatorial arcs expansion ⋮ On the Random Satisfiable Process ⋮ Another look at the phenomenon of phase transition ⋮ The large deviations of the whitening process in random constraint satisfaction problems ⋮ Constructing concrete hard instances of the maximum independent set problem ⋮ Satisfiability threshold for power law random 2-SAT in configuration model ⋮ Turánnical hypergraphs ⋮ Decision Trees and Influences of Variables Over Product Probability Spaces ⋮ A NEW UPPER BOUND FOR RANDOM (2 + p)-SAT BY FLIPPING TWO VARIABLES ⋮ On the structure of subsets of the discrete cube with small edge boundary ⋮ Finding tight Hamilton cycles in random hypergraphs faster ⋮ HOW SMART DOES AN AGENT NEED TO BE? ⋮ Sharp thresholds for certain Ramsey properties of random graphs ⋮ Noise sensitivity of Boolean functions and applications to percolation ⋮ Between 2- and 3-colorability ⋮ Branching Process Approach for 2-Sat Thresholds ⋮ A lower bound for the 4-satisfiability threshold ⋮ Proof of a hypercontractive estimate via entropy ⋮ Clique percolation ⋮ Combinatorial approach to the interpolation method and scaling limits in sparse random graphs ⋮ Arbitrary Threshold Widths for Monotone, Symmetric Properties ⋮ The Complexity of Propositional Proofs ⋮ Sharp thresholds for constraint satisfaction problems and homomorphisms ⋮ Rigorous results for random (\(2+p)\)-SAT ⋮ Results related to threshold phenomena research in satisfiability: Lower bounds ⋮ Lower bounds for random 3-SAT via differential equations ⋮ Upper bounds on the satisfiability threshold ⋮ Strong noise sensitivity and random graphs ⋮ Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems ⋮ On the threshold for rainbow connection number \(r\) in random graphs ⋮ PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS ⋮ Phase transition of multivariate polynomial systems ⋮ Random 2-XORSAT at the Satisfiability Threshold ⋮ Unnamed Item ⋮ Geometrical organization of solutions to random linear Boolean equations ⋮ On Random Ordering Constraints ⋮ The critical probability for confetti percolation equals 1/2 ⋮ The condensation transition in random hypergraph 2-coloring ⋮ Combinatorial Problems for Horn Clauses ⋮ The threshold for the square of a Hamilton cycle ⋮ Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses ⋮ Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion ⋮ Unnamed Item ⋮ Recognizing more random unsatisfiable 3-SAT instances efficiently ⋮ Selecting Complementary Pairs of Literals ⋮ An efficient local search method for random 3-satisfiability ⋮ The Complexity of Public-Key Cryptography ⋮ Graph bootstrap percolation ⋮ TRANSITIONS TO INTERMITTENCY AND COLLECTIVE BEHAVIOR IN RANDOMLY COUPLED MAP NETWORKS ⋮ Bootstrap percolation on the hypercube ⋮ The threshold for integer homology in random \(d\)-complexes ⋮ A sharp threshold for a random constraint satisfaction problem ⋮ Boolean functions: influence, threshold and noise ⋮ Phase transitions in discrete structures ⋮ Many hard examples in exact phase transitions ⋮ Optimal flow through the disordered lattice ⋮ A sharp threshold in proof complexity yields lower bounds for satisfiability search ⋮ Random subcube intersection graphs. I: Cliques and covering ⋮ Random \(\mathbb{Z}^d\)-shifts of finite type ⋮ An algorithm for random signed 3-SAT with intervals ⋮ On threshold properties of \(k\)-SAT: An additive viewpoint ⋮ Around two theorems and a lemma by Lucio Russo ⋮ The state of SAT ⋮ The unsatisfiability threshold revisited ⋮ Phase transition in a random NK landscape model ⋮ Threshold for monotone symmetric properties through a logarithmic Sobolev inequality ⋮ On the rank of higher inclusion matrices ⋮ Regular random \(k\)-SAT: Properties of balanced formulas ⋮ A threshold for the Maker-Breaker clique game ⋮ Combinatorial theorems in sparse random sets ⋮ Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Component structure in the evolution of random hypergraphs
- Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
- Threshold functions
- Boolean functions with low average sensitivity depend on few coordinates
- On Russo's approximate zero-one law
- Influences of variables and threshold intervals under group symmetries
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Inequalities with applications to percolation and reliability
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
- An approximate zero-one law
- A note on percolation
- Threshold Functions for H-factors
- Every monotone graph property has a sharp threshold
- Perfect matchings in random s‐uniform hypergraphs
- Tail bounds for occupancy and the satisfiability threshold conjecture
- On Random 3-sat
- Analysis of Two Simple Heuristics on a Random Instance ofk-sat
This page was built for publication: Sharp thresholds of graph properties, and the $k$-sat problem
