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