Optimal testing for planted satisfiability problems

DOI10.1214/15-EJS1001zbMath1307.62015arXiv1401.2205OpenAlexW2963167765MaRDI QIDQ2259537

Quentin Berthet

Publication date: 4 March 2015

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

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

zbMATH Keywords

satisfiability problempolynomial-time algorithmshigh-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)

Related Items (1)

Solving non-uniform planted and filtered random SAT formulas greedily

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Statistical and computational trade-offs in estimation of sparse principal components
• Optimal detection of sparse principal components in high dimension
• Detection of correlations
• On combinatorial testing problems
• Minimax detection of a signal for \(l^ n\)-balls.
• Higher criticism for detecting sparse heterogeneous mixtures.
• Detection boundary in sparse regression
• Computational barriers in minimax submatrix detection
• Detection of an anomalous cluster in a network
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Community detection in dense random networks
• On the concentration of the number of solutions of random satisfiability formulas
• Proof of the Satisfiability Conjecture for Large k
• On the Complexity of Random Satisfiability Problems with Planted Solutions
• Incoherence-Optimal Matrix Completion
• The Decimation Process in Random k-SAT
• Reconstruction and Clustering in Random Constraint Satisfaction Problems
• Can rare SAT formulae be easily recognized? On the efficiency of message-passing algorithms forK-SAT at large clause-to-variable ratios
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Relations between average case complexity and approximation complexity
• Solving random satisfiable 3CNF formulas in expected polynomial time
• The Complexity of Enumeration and Reliability Problems
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Computational Sample Complexity
• Computational and statistical tradeoffs via convex relaxation
• The asymptotic k-SAT threshold
• Survey propagation: An algorithm for satisfiability
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Statistical algorithms and a lower bound for detecting planted cliques
• Going after the k-SAT threshold
• On the solution-space geometry of random constraint satisfaction problems
• Computational sample complexity and attribute-efficient learning

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