Bounding Laconic Proof Systems by Solving CSPs in Parallel
| Title | Bounding Laconic Proof Systems by Solving CSPs in Parallel |
| Publication Type | Conference Paper |
| Year of Publication | 2017 |
| Authors | Li, Jason, O'Donnell, Ryan |
| Conference Name | Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures |
| Publisher | ACM |
| Conference Location | New York, NY, USA |
| ISBN Number | 978-1-4503-4593-4 |
| Keywords | Complexity theory, composability, compositionality, constraint satisfaction problems, pubcrawl, semidefinite programming, theoretical cryptography |
| Abstract | 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. |
| URL | https://dl.acm.org/citation.cfm?doid=3087556.3087557 |
| DOI | 10.1145/3087556.3087557 |
| Citation Key | li_bounding_2017 |