Optimal testing for planted satisfiability problems
Copyright policy )Optimal testing for planted satisfiability problems
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.
- California Institute of Technology United States
- College of New Jersey United States
FOS: Computer and information sciences, 62C20, Combinatorial probability, Minimax procedures in statistical decision theory, satisfiability problem, Probability (math.PR), 68R01, Mathematics - Statistics Theory, General topics of discrete mathematics in relation to computer science, Statistics Theory (math.ST), Computational Complexity (cs.CC), high-dimensional detection, polynomial-time algorithms, 510, 004, Computer Science - Computational Complexity, FOS: Mathematics, 60C05, Satisfiability problem, Mathematics - Probability
FOS: Computer and information sciences, 62C20, Combinatorial probability, Minimax procedures in statistical decision theory, satisfiability problem, Probability (math.PR), 68R01, Mathematics - Statistics Theory, General topics of discrete mathematics in relation to computer science, Statistics Theory (math.ST), Computational Complexity (cs.CC), high-dimensional detection, polynomial-time algorithms, 510, 004, Computer Science - Computational Complexity, FOS: Mathematics, 60C05, Satisfiability problem, Mathematics - Probability
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!