The threshold for SDP-refutation of random regular NAE-3SAT
Publication:5236327
DOI10.1137/1.9781611975482.140zbMath1432.68413arXiv1804.05230OpenAlexW3203023708MaRDI QIDQ5236327
Subhabrata Sen, Yash Deshpande, Tselil Schramm, Ryan O'Donnell, Andrea Montanari
Publication date: 15 October 2019
Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1804.05230
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational aspects of satisfiability (68R07)
Related Items (4)
This page was built for publication: The threshold for SDP-refutation of random regular NAE-3SAT