论文标题
通过内部产品和与永久性的关系计数短矢量对
Counting Short Vector Pairs by Inner Product and Relations to the Permanent
论文作者
论文摘要
给出作为输入两个$ n $ element集合$ \ MATHCAL A，\ MATHCAL B \ subseteq \ {0,1 \}^d $带有$ d = C \ log N \ leq（\ log n）^2/（\ log n）^2/（\ log log \ log \ log \ \ log \ h）对$（x，y）\ in \ Mathcal a \ times \ times \ Mathcal b $与整数内部产品$ \ langle x，y \ rangle = t $确定性，在$ n^2/2^{ω\ bigl（\！\！\！\！\！这表明，可以在确定性的亚二次时间时间中解决这个问题，几乎可以达到$ \ log^2 n $尺寸，几乎与Alman和Williams的亚段随机检测算法的维度结合匹配[FOCS 2015]。我们还展示了如何修改其随机算法以计数对W.H.P.的计数，以获得快速的随机算法。我们的确定性算法建立在一种新型技术的基础上，该技术是通过主要残基从汇聚物中重建功能的新技术，可以将其视为中国剩余定理的{\ em添加剂}类似物。作为我们的第二个贡献，我们将通过内部产物计数矢量对的任务的细粒度复杂性与计算整数上的零矩阵永久性的任务相关联。
Given as input two $n$-element sets $\mathcal A,\mathcal B\subseteq\{0,1\}^d$ with $d=c\log n\leq(\log n)^2/(\log\log n)^4$ and a target $t\in \{0,1,\ldots,d\}$, we show how to count the number of pairs $(x,y)\in \mathcal A\times \mathcal B$ with integer inner product $\langle x,y \rangle=t$ deterministically, in $n^2/2^{Ω\bigl(\!\sqrt{\log n\log \log n/(c\log^2 c)}\bigr)}$ time. This demonstrates that one can solve this problem in deterministic subquadratic time almost up to $\log^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.
