scientific article; zbMATH DE number 2079360

MaRDI QIDQ4471319zbMATH OpenFDO

Authors Don Coppersmith, David Gamarnik, Gregory B. Sorkin, Mohammad T. Hajiaghayi

Publication date 28 July 2004

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Random MAX SAT, random MAX CUT, and their phase transitions
• An Empirical Study of MAX-2-SAT Phase Transitions
• scientific article; zbMATH DE number 2083805
• Limit Theorems for Random MAX-2-XORSAT
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold

Cited in

(17)

• On the lower bounds of random Max 3 and 4-SAT
• Structure of large random hypergraphs
• Probabilistic characterization of random Max r-Sat
• MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
• SAT distributions with planted assignments and phase transitions between decision and optimization problems
• On a class of optimization problems with no ``efficiently computable solution
• The scaling window of the 2-SAT transition
• The Normalized Autocorrelation Length of Random Max  $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$
• SAT Distributions with Phase Transitions between Decision and Optimization Problems
• An Empirical Study of MAX-2-SAT Phase Transitions
• scientific article; zbMATH DE number 1107723 (Why is no real title available?)
• scientific article; zbMATH DE number 2084703 (Why is no real title available?)
• On the Lower Bounds of Random Max 3 and 4-SAT
• Random MAX SAT, random MAX CUT, and their phase transitions
• Tricritical points in random combinatorics: the -SAT case
• Sparse graphs: metrics and random models
• Mind the gap: achieving a super-Grover quantum speedup by jumping to the end

This page was built for publication:

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