Biblio
Filters: Author is O'Donnell, Ryan [Clear All Filters]
.
2017. Bounding Laconic Proof Systems by Solving CSPs in Parallel. Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures. :95–100.
We show that the basic semidefinite programming relaxation value of any constraint satisfaction problem can be computed in NC; that is, in parallel polylogarithmic time and polynomial work. As a complexity-theoretic consequence we get that $\backslash$MIPone[k,c,s] $\backslash$subseteq $\backslash$PSPACE provided s/c $\backslash$leq (.62-o(1))k/2textasciicircumk, resolving a question of Austrin, H$\backslash$aa stad, and Pass. Here $\backslash$MIPone[k,c,s] is the class of languages decidable with completeness c and soundness s by an interactive proof system with k provers, each constrained to communicate just 1 bit.