Counting Short Vector Pairs by Inner Product and Relations to the Permanent

arXiv2007.14092MaRDI QIDQ6345984FDOQ6345984

Authors: Andreas Björklund, Petteri Kaski 

Publication date: 28 July 2020

Abstract: Given as input two $n$-element sets $mathcalA,mathcalBsubseteq{0,1}^d$ with $d=clognleq(logn{)}^2/(loglogn{)}^4$ and a target $tin0,1,ldots,d$, we show how to count the number of pairs $(x,y)inmathcalAimesmathcalB$ with integer inner product $langlex,yangle=t$ deterministically, in $$ time. This demonstrates that one can solve this problem in deterministic subquadratic time almost up to $lo{g}^{2}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, which can be seen as an {em 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.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Exact enumeration problems, generating functions (05A15) Determinants, permanents, traces, other special matrix functions (15A15)

This page was built for publication: Counting Short Vector Pairs by Inner Product and Relations to the Permanent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6345984)