Optimal testing for planted satisfiability problems

DOI10.1214/15-EJS1001zbMATH Open1307.62015arXiv1401.2205OpenAlexW2963167765MaRDI QIDQ2259537FDOQ2259537

Authors: Quentin Berthet 

Publication date: 4 March 2015

Published in: Electronic Journal of Statistics (Search for Journal in Brave)

Abstract: We study the problem of detecting planted solutions in a random satisfiability formula. Adopting the formalism of hypothesis testing in statistical analysis, we describe the minimax optimal rates of detection. Our analysis relies on the study of the number of satisfying assignments, for which we prove new results. We also address algorithmic issues, and give a computationally efficient test with optimal statistical performance. This result is compared to an average-case hypothesis on the hardness of refuting satisfiability of random formulas.

Full work available at URL: https://arxiv.org/abs/1401.2205

Recommendations

• On the complexity of random satisfiability problems with planted solutions
• On the complexity of random satisfiability problems with planted solutions (extended abstract)
• Average-Case Analysis for the MAX-2SAT Problem
• Phase transition for local search on planted SAT
• Pushing Random Walk Beyond Golden Ratio

zbMATH Keywords

polynomial-time algorithmssatisfiability problemhigh-dimensional detection

Mathematics Subject Classification ID

Minimax procedures in statistical decision theory (62C20) General topics of discrete mathematics in relation to computer science (68R01) Combinatorial probability (60C05)

Cites Work

• Detection boundary in sparse regression
• Minimax detection of a signal for \(l^ n\)-balls.
• Higher criticism for detecting sparse heterogeneous mixtures.
• Detection of an anomalous cluster in a network
• Community detection in dense random networks
• Relations between average case complexity and approximation complexity
• Optimal detection of sparse principal components in high dimension
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• On combinatorial testing problems
• The Complexity of Enumeration and Reliability Problems
• Gibbs states and the set of solutions of random constraint satisfaction problems
• On the concentration of the number of solutions of random satisfiability formulas
• Proof of the satisfiability conjecture for large \(k\)
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The asymptotic \(k\)-SAT threshold
• On the complexity of random satisfiability problems with planted solutions (extended abstract)
• Computational and statistical tradeoffs via convex relaxation
• On the solution-space geometry of random constraint satisfaction problems
• Statistical and computational trade-offs in estimation of sparse principal components
• Incoherence-Optimal Matrix Completion
• Title not available (Why is that?)
• Detection of correlations
• Statistical algorithms and a lower bound for detecting planted cliques
• Title not available (Why is that?)
• Solving random satisfiable 3CNF formulas in expected polynomial time
• Title not available (Why is that?)
• Survey propagation: An algorithm for satisfiability
• Computational barriers in minimax submatrix detection
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Reconstruction and clustering in random constraint satisfaction problems
• Going after the \(k\)-SAT threshold
• Can rare SAT formulae be easily recognized? On the efficiency of message-passing algorithms forK-SAT at large clause-to-variable ratios
• Why almost all satisfiable k-CNF formulas are easy
• Generating hard satisfiable formulas by hiding solutions deceptively
• Title not available (Why is that?)
• Computational sample complexity and attribute-efficient learning
• Conditional random fields, planted constraint satisfaction, and entropy concentration
• Computational Sample Complexity
• The decimation process in random \(k\)-SAT
• Reweighted belief propagation and quiet planting for random \(K\)-SAT
• Hard satisfiable clause sets for benchmarking equivalence reasoning techniques

Cited In (5)

• On the complexity of random satisfiability problems with planted solutions
• Quiet planting in the locked constraint satisfaction problems
• Solving non-uniform planted and filtered random SAT formulas greedily
• Self-planting: digging holes in rough landscapes
• On the complexity of random satisfiability problems with planted solutions (extended abstract)

This page was built for publication: Optimal testing for planted satisfiability problems

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