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

Ehud Friedgut

Publication date: 31 August 1999

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)


zbMATH Keywords

random graphsmonotone graph propertiescoarse thresholds


Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.) (42C10)


Related Items

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, Unnamed Item, A general model and thresholds for random constraint satisfaction problems, Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances, Combinatorial sharpness criterion and phase transition classification for random CSPs, Proof of the satisfiability conjecture for large \(k\), On the thresholds in linear and nonlinear Boolean equations, A stability result for the cube edge isoperimetric inequality, The junta method in extremal hypergraph theory and Chvátal's conjecture, Monochromatic trees in random graphs, Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs, Generalized satisfiability problems: Minimal elements and phase transitions., Random 2 XORSAT phase transition, The asymptotic \(k\)-SAT threshold, CHAMP: a multipass algorithm for Max Sat based on saver variables, Phase transition of degeneracy in minor-closed families, Scaling limits for the threshold window: when does a monotone Boolean function flip its outcome?, Go-MOCE: greedy order method of conditional expectations for Max Sat, Lower bounds for \(k\)-DNF resolution on random 3-CNFs, On sharp transitions in making squares, Hypercontractivity via tensor calculus, A structure theorem for Boolean functions with small total influences, Percolation on fitness landscapes: effects of correlation, phenotype, and incompatibilities, On a biased edge isoperimetric inequality for the discrete cube, Towards a proof of the Fourier-entropy conjecture?, Computational approaches to finding and measuring inconsistency in arbitrary knowledge bases, The cook-book approach to the differential equation method, Phase transitions of contingent planning problem, The scaling window of the 2-SAT transition, Thresholds and expectation-thresholds of monotone properties with small minterms, The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture, Thresholds versus fractional expectation-thresholds, On the freezing of variables in random constraint satisfaction problems, On the satisfiability threshold and clustering of solutions of random 3-SAT formulas, Pairs of SAT-assignments in random Boolean formulæ, On the phase transitions of random \(k\)-constraint satisfaction problems, Connectivity and equilibrium in random games, Noise stability of functions with low influences: invariance and optimality, Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT, Space proof complexity for random 3-CNFs, Random sum-free subsets of abelian groups, On the satisfiability threshold of formulas with three literals per clause, Correlations between Horn fractions, satisfiability and solver performance for fixed density random 3-CNF instances, Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT, Gibbs measures and phase transitions on sparse random graphs, Destruction of dissipative structures under random actions, On topological minors in random simplicial complexes, The typical structure of sparse $K_{r+1}$-free graphs, Stability versions of Erdős-Ko-Rado type theorems via isoperimetry, Colorings of partial Steiner systems and their applications, Probabilistic characterization of random Max \(r\)-Sat, The structure of the set of satisfying assignments for a random \(k\)-CNF, Phase Transitions in Discrete Structures, The set of solutions of random XORSAT formulae, The Normalized Autocorrelation Length of Random Max  $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$, Sharp threshold for the Ising perceptron model, The SAT-UNSAT transition for random constraint satisfaction problems, A sharp threshold for van der Waerden's theorem in random subsets, Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT, Length of prime implicants and number of solutions of random CNF formulae, Instability, complexity, and evolution, The property of having a k -regular subgraph has a sharp threshold, Super solutions of random \((3 + p)\)-SAT, When does the giant component bring unsatisfiability?, Weak lumpability in the \(k\)-SAT problem, Delaying satisfiability for random 2SAT, Belief propagation on the random \(k\)-SAT model, Using the method of conditional expectations to supply an improved starting point for CCLS, A hierarchy of randomness for graphs, Concentration on the Boolean hypercube via pathwise stochastic analysis, On the distribution of the Fourier spectrum of Boolean functions, The Horn renamability, q-Horn and SLUR threshold for random \(k\)-CNF formulas, A sharp threshold for the renameable-Horn and the \(q\)-Horn properties, Typical case complexity of satisfiability algorithms and the threshold phenomenon, Threshold properties of random Boolean constraint satisfaction problems, Analytic description of the phase transition of inhomogeneous multigraphs, Spines of random constraint satisfaction problems: definition and connection with computational complexity, Solving non-uniform planted and filtered random SAT formulas greedily, Waiter-client and client-waiter Hamiltonicity games on random graphs



Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:4257709&oldid=18157422"
Powered by MediaWiki