2026-07-23T08:19:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14098 2024-03-06T10:53:28Z ddc:004 open_access

Counting Short Vector Pairs by Inner Product and Relations to the Permanent Björklund, Andreas Kaski, Petteri additive reconstruction Chinese Remainder Theorem counting inner product modular tomography orthogonal vectors permanent Given as input two n-element sets A, B ⊆ {0,1}^d with d = clog n ≤ (log n)²/(log log n)⁴ and a target t ∈ {0,1,…,d}, we show how to count the number of pairs (x,y) ∈ A× B with integer inner product ⟨ x,y ⟩ = t deterministically, in n²/2^{Ω(√{log nlog log n/(clog² c)})} time. This demonstrates that one can solve this problem in deterministic subquadratic time almost up to log² n dimensions, nearly matching the dimension bound of a subquadratic randomized detection algorithm of Alman and Williams [FOCS 2015]. We also show how to modify their randomized algorithm to count the pairs w.h.p., to obtain a fast randomized algorithm. Our deterministic algorithm builds on a novel technique of reconstructing a function from sum-aggregates by prime residues, or modular tomography, which can be seen as an additive analog of the Chinese Remainder Theorem. As our second contribution, we relate the fine-grained complexity of the task of counting of vector pairs by inner product to the task of computing a zero-one matrix permanent over the integers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andreas Björklund and Petteri Kaski 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.29 urn:nbn:de:0030-drops-140988 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.29 eng https://creativecommons.org/licenses/by/4.0/legalcode