2026-07-23T04:16:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18080 2024-03-06T11:00:57Z ddc:004 open_access

Nondeterministic Interactive Refutations for Nearest Boolean Vector Bogdanov, Andrej Rosen, Alon average-case complexity statistical zero-knowledge nondeterministic refutation Sherrington-Kirkpatrick Hamiltonian complexity of statistical inference lattice smoothing Most n-dimensional subspaces 𝒜 of ℝ^m are Ω(√m)-far from the Boolean cube {-1, 1}^m when n < cm for some constant c > 0. How hard is it to certify that the Nearest Boolean Vector (NBV) is at least γ √m far from a given random 𝒜? Certifying NBV instances is relevant to the computational complexity of approximating the Sherrington-Kirkpatrick Hamiltonian, i.e. maximizing x^TAx over the Boolean cube for a matrix A sampled from the Gaussian Orthogonal Ensemble. The connection was discovered by Mohanty, Raghavendra, and Xu (STOC 2020). Improving on their work, Ghosh, Jeronimo, Jones, Potechin, and Rajendran (FOCS 2020) showed that certification is not possible in the sum-of-squares framework when m ≪ n^1.5, even with distance γ = 0. We present a non-deterministic interactive certification algorithm for NBV when m ≫ n log n and γ ≪ 1/mn^1.5. The algorithm is obtained by adapting a public-key encryption scheme of Ajtai and Dwork. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrej Bogdanov and Alon Rosen 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.28 urn:nbn:de:0030-drops-180801 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.28 eng https://creativecommons.org/licenses/by/4.0/legalcode