Complexity Theory and Nearest Boolean Vector: Advancements and Insights
Explore the latest research on complexity theory, Boolean vectors, and Sherrington-Kirkpatrick Hamiltonian. Discover the implications of nearest Boolean vectors and the challenges in efficiently computing certificates for subspaces. Dive into the depths of complexity classes and reductions in this fascinating field of study.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Andrej Bogdanov University of Ottawa with Alon Rosen Bocconi Univ. and Reichman Univ. COMPLEXITY OF NEAREST BOOLEAN VECTOR institution Simons Institute February 2023 date
SAT MCSP MKTP P
[Brennan-Bresler 2020] BH MCSP MKTP SAT CLIQUE AvgP
complexity theory A is no harder than B reductions no reduction from A to B complexity classes
SAT MCSP MKTP P
[Feige-Kim-Ofek 2006] BH MCSP MKTP SAT CLIQUE AvgP
nearest Boolean vector {-1, 1}m YES dist(A, { 1}m) m NO dist(A, { 1}m) > m [Mohanty-Raghavendra-Xu 2020]
Sherrington-Kirkpatrick Hamiltonian SK(M) = max xTMx x {-1, 1}m M ~ GOE = max(M) 2m3/2 SK(M) max xTMx x = m SK(M) 1.526 m3/2 [Parisi 1979, Talagrand 2011] SK HeurP [Montanari 2019]
? SK NBV SK AvgP If NBV AvgP for n/m, = 0.01 can certify that most SK(M) 1.99 Sum-of-squares thinks A { 1}m m = n1.01, level 4 [Mohanty-Raghavendra-Xu 2020] [Ghosh-Jeronimo-Jones- Potechin-Rajendran 2020] m = n1.49, level n0.01
our result BH NBV with m = 100n log n , = 2-o(n) and = 0.01/mn3/2 log1/2n/ is in Avg SZK MCSP MKTP SAT CLIQUE NBV AvgP
corollary For all but 2-o(n) subspaces A we can verify they are somewhat far from {-1, 1}m but we don t know how to efficiently compute the certificate
-0.60 3 -0.766 0.030 -0.282 -0.556 -1.043 -0.373 0.404 -1.261 -1.875 -0.484 0.482 -0.411 0.258 -0.817 0.495 -0.711 -1.281 0.416 0.824 0.657 -0.029 1.221 -0.238 -0.895 0.544 -0.685 -0.619 1.136 -0.985 0.055 0.715 -1.533 1.321 -1.298 0.138 -2.402 -0.168 0.476 -0.240 A B
A B
{1}mA { 1}m B
A g ~ N(0, 1)n vs +1 -1 -1 +1 -1 N(0, 1)m n (A, round(xA)) and (A, round(g)) are (A, round(xA)) and (A, round(g)) are O( n logn /m )-close O( n logn /m )-close [B., Cueto Noval, Hoffmann, Rosen 2022]
linearization +1 -1 -1 +1 -1 A w A 2 w 2 1
{1}mA mod P { 1}m B mod P
A A mod P +1 -1 -1 +1 P (A, P, {x{ AP-1}p}) and (A, P, R) are exp(- (m)) -close if m n log n
the smallest eigenvalue 1/ max(P-1) = min(P) A P( min(P) 1/ n) = (1) P P(A contains good P) ? Greedy algorithm finds P with prob 2- (m)
LLLization [Lagarias-Odlyzko 1983] NBV SVP A { 1}m = ( = 0) min v 2-m random A min v 1 GapSVP m coNP [Aharonov-Regev 2004]
conclusion and open questions Complexity of NBV depends on n/m, not fully captured by SoS lower bounds In or out of coNP for n/m, = (1)? Phase transition? Related to SVP? Other natural problems in DistNP AvgcoNP \ AvgP?
