On the complexity of random satisfiability problems with planted solutions (extended abstract)

DOI10.1145/2746539.2746577MaRDI QIDQ2941491zbMATH OpenOpenAlexFDO

Authors Vitaly Feldman, Will Perkins, Santosh S. Vempala

Publication date 21 August 2015

Published in Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

refutationhypergraph partitioningstatistical algorithms\(k\)-SATplanted satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: The problem of identifying a planted assignment given a random $k$-SAT formula consistent with the assignment exhibits a large algorithmic gap: while the planted solution becomes unique and can be identified given a formula with $O(nlogn)$ clauses, there are distributions over clauses for which the best known efficient algorithms require $n^{k/2}$ clauses. We propose and study a unified model for planted $k$-SAT, which captures well-known special cases. An instance is described by a planted assignment $sigma$ and a distribution on clauses with $k$ literals. We define its distribution complexity as the largest $r$ for which the distribution is not $r$-wise independent ($1lerlek$ for any distribution with a planted assignment). Our main result is an unconditional lower bound, tight up to logarithmic factors, for statistical (query) algorithms [Kearns 1998, Feldman et. al 2012], matching known upper bounds, which, as we show, can be implemented using a statistical algorithm. Since known approaches for problems over distributions have statistical analogues (spectral, MCMC, gradient-based, convex optimization etc.), this lower bound provides a rigorous explanation of the observed algorithmic gap. The proof introduces a new general technique for the analysis of statistical query algorithms. It also points to a geometric paring phenomenon in the space of all planted assignments. We describe consequences of our lower bounds to Feige's refutation hypothesis [Feige 2002] and to lower bounds on general convex programs that solve planted $k$-SAT. Our bounds also extend to other planted $k$-CSP models, and, in particular, provide concrete evidence for the security of Goldreich's one-way function and the associated pseudorandom generator when used with a sufficiently hard predicate [Goldreich 2000].

Recommendations

• On the complexity of random satisfiability problems with planted solutions
• Optimal testing for planted satisfiability problems
• Statistical algorithms and a lower bound for detecting planted cliques
• Statistical algorithms and a lower bound for detecting planted cliques
• Reweighted belief propagation and quiet planting for random \(K\)-SAT

Cites work

• Approximate distance oracles
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast C-K-R partitions of sparse graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On approximate distance labels and routing schemes with affine stretch
• On sparse spanners of weighted graphs
• Ramsey partitions and proximity data structures
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Shortest-path queries in static networks

Cited in

(17)

• scientific article; zbMATH DE number 2083805 (Why is no real title available?)
• Quiet planting in the locked constraint satisfaction problems
• Fast pseudorandom functions based on expander graphs
• Expander-based cryptography meets natural proofs
• On the complexity of random satisfiability problems with planted solutions
• Algebraic attacks against random local functions and their countermeasures
• Statistical algorithms and a lower bound for detecting planted cliques
• Expander-Based Cryptography Meets Natural Proofs
• Statistical algorithms and a lower bound for detecting planted cliques
• The replica symmetric phase of random constraint satisfaction problems
• Optimal testing for planted satisfiability problems
• Charting the replica symmetric phase
• Reweighted belief propagation and quiet planting for random \(K\)-SAT
• Cryptographic hardness of random local functions. Survey
• Information-theoretic and algorithmic thresholds for group testing
• scientific article; zbMATH DE number 6866300 (Why is no real title available?)
• SAT distributions with planted assignments and phase transitions between decision and optimization problems

Describes a project that uses

Uses Software

• Graphs

This page was built for publication: On the complexity of random satisfiability problems with planted solutions (extended abstract)

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