On the Complexity of Random Satisfiability Problems with Planted Solutions
type: Item
instance of: scholarly article
title: On the Complexity of Random Satisfiability Problems with Planted Solutions
zbMATH Open document ID: 1321.68280
DOI: 10.1145/2746539.2746577
author: Vitaly Feldman
author: Will Perkins
author: Santosh S. Vempala
published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing
publication date: 2015-08-21T00:00:00Z
full work available at URL: https://arxiv.org/abs/1311.4821
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6474709
zbMATH Keywords: hypergraph partitioning
zbMATH Keywords: \(k\)-SAT
zbMATH Keywords: planted satisfiability
zbMATH Keywords: refutation
zbMATH Keywords: statistical algorithms
describes a project that uses: Graphs
MaRDI profile type: Publication
OpenAlex ID: W2042038477
arXiv ID: 1311.4821
cites work: On Approximate Distance Labels and Routing Schemes with Affine Stretch
cites work: On sparse spanners of weighted graphs
cites work: Near-Linear Time Construction of Sparse Neighborhood Covers
cites work: Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
cites work: Approximate distance oracles with constant query time
cites work: Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
cites work: Ramsey partitions and proximity data structures
cites work: Q5414573
cites work: Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
cites work: Automata, Languages and Programming
cites work: Shortest-path queries in static networks
cites work: Approximate distance oracles
description: scientific article