Detection of Planted Solutions for Flat Satisfiability Problems

Quentin Berthet, Jordan S. Ellenberg

Type: Preprint

Publication Date: 2015-02-21

Citations: 0

Locations

arXiv (Cornell University) - View

Similar Works

Action	Title	Year	Authors
+	Detection of Planted Solutions for Flat Satisfiability Problems	2015	Quentin Berthet Jordan S. Ellenberg
+	Optimal Testing for Planted Satisfiability Problems	2014	Quentin Berthet
+	Optimal Testing for Planted Satisfiability Problems	2014	Quentin Berthet
+	Quiet planting in the locked constraints satisfaction problems	2009	Lenka Zdeborová Florent Krząkała
+ PDF Chat	On the Complexity of Random Satisfiability Problems with Planted Solutions	2015	Vitaly Feldman Will Perkins Santosh Vempala
+	Learning a SAT Solver from Single-Bit Supervision	2018	Daniel Selsam Matthew Lamm Benedikt Bünz Percy Liang Leonardo de Moura David L. Dill
+	Learning a SAT Solver from Single-Bit Supervision	2018	Daniel Selsam Matthew S. Lamm Benedikt Bünz Percy Liang Leonardo de Moura David L. Dill
+ PDF Chat	Reweighted Belief Propagation and Quiet Planting for Random K-SAT	2014	Florent Krząkała Marc Mézard Lenka Zdeborová
+	On statistical inference when fixed points of belief propagation are unstable	2021	Siqi Liu Sidhanth Mohanty Prasad Raghavendra
+	Probabilistic Model Counting with Short XORs	2017	Dimitris Achlioptas Panos Theodoropoulos
+	Probabilistic Model Counting with Short XORs	2017	Dimitris Achlioptas Panos Theodoropoulos
+ PDF Chat	Counting Solutions to Random CNF Formulas	2021	Andreas Galanis Leslie Ann Goldberg Heng Guo Kuan Yang
+ PDF Chat	Reconstruction and Clustering in Random Constraint Satisfaction Problems	2011	Andrea Montanari Ricardo Restrepo Prasad Tetali
+ PDF Chat	Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively	2007	Hongyang Jia Cristopher Moore Doug Strain
+	Reconstruction and Clustering in Random Constraint Satisfaction Problems	2009	Andrea Montanari Ricardo Restrepo Prasad Tetali
+	Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively	2005	Haixia Jia Cristopher Moore Doug Strain
+	The sparse parity matrix	2021	Amin Coja‐Oghlan Oliver Cooley Mihyun Kang Joon Lee Jean Bernoulli Ravelomanana
+	On the Complexity of Random Satisfiability Problems with Planted Solutions	2013	Vitaly Feldman Will Perkins Santosh Vempala
+	On the Complexity of Random Satisfiability Problems with Planted Solutions	2013	Vitaly Feldman Will Perkins Santosh Vempala
+ PDF Chat	Fast Analysis of the OpenAI O1-Preview Model in Solving Random K-SAT Problem: Does the LLM Solve the Problem Itself or Call an External SAT Solver?	2024	Raffaele Marino

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (13)

Action	Title	Year	Authors
+	Computational barriers in minimax submatrix detection	2015	Zongming Ma Yihong Wu
+	Sparse CCA: Adaptive Estimation and Computational Barriers	2014	Chao Gao Zongming Ma Harrison H. Zhou
+	Semidefinite programming relaxations for semialgebraic problems	2003	Pablo A. Parrilo
+	Global Optimization with Polynomials and the Problem of Moments	2001	Jean B. Lasserre
+	Finding a large hidden clique in a random graph	1998	Noga Alon Michael Krivelevich Benny Sudakov
+	Optimal detection of sparse principal components in high dimension	2013	Quentin Berthet Philippe Rigollet
+ PDF Chat	On the Complexity of Random Satisfiability Problems with Planted Solutions	2015	Vitaly Feldman Will Perkins Santosh Vempala
+ PDF Chat	Incoherence-Optimal Matrix Completion	2015	Yudong Chen
+	Agnostic Learning of Disjunctions on Symmetric Distributions	2014	Vitaly Feldman Pravesh K. Kothari
+	Computational and statistical boundaries for submatrix localization in a large noisy matrix	2017	Tommaso Cai Tengyuan Liang Alexander Rakhlin