On smoothed analysis in dense graphs and formulas

DOI10.1002/RSA.20097MaRDI QIDQ3419587zbMATH OpenOpenAlexFDO

Authors Michael Krivelevich, Benny Sudakov, Prasad Tetali

Publication date 7 February 2007

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20097

zbMATH Keywords

random graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Ramsey theory (05D10)

Recommendations

• Sharp thresholds of graph properties, and the k-sat problem
• On smoothed \(k\)-CNF formulas and the \texttt{Walksat} algorithm
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• On sharp thresholds in random geometric graphs
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold

Cites work

• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))

Cited in

(28)

• Small rainbow cliques in randomly perturbed dense graphs
• An asymmetric random Rado theorem: 1-statement
• Isoperimetric numbers of randomly perturbed intersection graphs
• Smoothed Analysis on Connected Graphs
• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• Smoothed Analysis on Connected Graphs
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Vertex Ramsey properties of randomly perturbed graphs
• Smoothed analysis of local search algorithms
• The effect of adding randomly weighted edges
• Ramsey properties of randomly perturbed graphs: cliques and cycles
• Maker-Breaker games on randomly perturbed graphs
• Large Rainbow Cliques in Randomly Perturbed Dense Graphs
• Tree decompositions of graphs without large bipartite holes
• Tilings in randomly perturbed dense graphs
• Monochromatic Schur Triples in Randomly Perturbed Dense Sets of Integers
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Triangles in randomly perturbed graphs
• Expansion and Lack Thereof in Randomly Perturbed Graphs
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• Factors in randomly perturbed hypergraphs
• Rainbow cliques in randomly perturbed dense graphs
• Schur properties of randomly perturbed sets
• Ramsey properties of randomly perturbed hypergraphs
• Average-case and smoothed analysis of graph isomorphism
• Minors, connectivity, and diameter in randomly perturbed sparse graphs
• Smoothed analysis of the Komlós conjecture: Rademacher noise
• Rainbow connectivity of randomly perturbed graphs

This page was built for publication: On smoothed analysis in dense graphs and formulas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3419587)