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

DOI10.1145/2746539.2746577zbMATH Open1321.68280arXiv1311.4821OpenAlexW2042038477MaRDI QIDQ2941491FDOQ2941491

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)

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].

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

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

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)

Cites Work

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

Cited In (18)

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

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)