On the Complexity of Random Satisfiability Problems with Planted Solutions
From MaRDI portal
Publication:4577186
DOI10.1137/16M1078471zbMath1396.68057OpenAlexW2884374337WikidataQ129516697 ScholiaQ129516697MaRDI QIDQ4577186
Vitaly Feldman, Will Perkins, Santosh Vempala
Publication date: 17 July 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1078471
Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (9)
Tensor clustering with planted structures: statistical optimality and computational limits ⋮ On the Power of Learning from k-Wise Queries ⋮ Polynomial‐time universality and limitations of deep learning ⋮ Adversarial manifold estimation ⋮ Unnamed Item ⋮ Statistical-computational trade-offs in tensor PCA and related problems via communication complexity ⋮ Unnamed Item ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio ⋮ Solving non-uniform planted and filtered random SAT formulas greedily
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Large Sample Properties of Generalized Method of Moments Estimators
- Optimization by Simulated Annealing
- Cryptographic hardness of random local functions. Survey
- More on average case vs approximation complexity
- A complete characterization of statistical query learning with applications to evolvability
- Reconstruction and estimation in the planted partition model
- Approximation resistant predicates from pairwise independence
- Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
- Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
- Inequalities in Fourier analysis
- A polynomial-time algorithm for learning noisy linear threshold functions
- Learning with restricted focus of attention
- A proof of the block model threshold conjecture
- Statistical active learning algorithms for noise tolerance and differential privacy
- On the Fourier tails of bounded functions over the discrete cube
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
- Weakly learning DNF and characterizing statistical query learning using Fourier analysis
- Note on strong refutation algorithms for random k-SAT formulas
- Public-key cryptography from different assumptions
- A Dichotomy for Local Small-Bias Generators
- On the Complexity of Random Satisfiability Problems with Planted Solutions
- Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem
- On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
- An Efficient Sparse Regularity Concept
- Efficient noise-tolerant learning from statistical queries
- A spectral heuristic for bisecting random graphs
- Recognizing more random unsatisfiable 3-SAT instances efficiently
- Sampling-Based Approaches to Calculating Marginal Densities
- Relations between average case complexity and approximation complexity
- Solving random satisfiable 3CNF formulas in expected polynomial time
- Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
- On the Security of Goldreich’s One-Way Function
- Robust Stochastic Approximation Approach to Stochastic Programming
- The Calculation of Posterior Distributions by Data Augmentation
- Gaussian Hilbert Spaces
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization
- Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
- Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Algebraic attacks against random local functions and their countermeasures
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Simulated Annealing for Convex Optimization
- Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions
- Automata, Languages and Programming
- Recognizing More Unsatisfiable Random k-SAT Instances Efficiently
- On ε‐biased generators in NC0
- A simple polynomial-time rescaling algorithm for solving linear programs
This page was built for publication: On the Complexity of Random Satisfiability Problems with Planted Solutions
