论文标题
通过正交向量改进Schroeppel和Shamir的算法以获取子集总和
Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors
论文作者
论文摘要
我们提出了一个$ \ MATHCAL {O}^\ Star（2^{0.5n}）$时间和$ \ Mathcal {O}^\ Star（2^{0.249999n}）$ space随机算法，用于求解与$ n $ Integers解决worst-casase casase casase casase subset subs Instances cob $ n $ integers cast。这是对长期的$ \ MATHCAL {O}^\ Star（2^{n/2}）$时间和$ \ Mathcal {O}^\ Star（2^{N/4}）$ Space Algorithm的首次改进。 我们分为两个步骤违反了这一差距：（1）我们向正交矢量问题（OV）提出了空间有效的降低，这是细粒度复杂性中最中心的问题之一。减少是通过复杂的Schroeppel和Shamir方法的复杂组合，以及Howgrave-Graham和Joux（Eurocrypt 2010）提出的表示技术，用于设计平均案例制度的子集总和算法。 （2）我们为OV提供了一种算法，该算法在$ \ {0,1,1 \}^d $中以$ n $中的$ n $中的一个正交对，并带有支撑尺寸$ d/4 $ in PITION $ \ tilde {o} {o}（O}（n \ cdot2^d/\ binom {d/\ binom {d/\ binom {d} d/4} d/4}）$。我们的OV算法基于Fomin，Lokshtanov，Panolan和Saurabh开发的代表性家庭框架（J. ACM 2016）。 我们的还原揭示了子集总和与OV之间的奇怪紧密关系，因为我们的OV算法的任何改进都将暗示对Schroeeppel和Shamir的运行时间的改善，这也是一个长期存在的开放问题。
We present an $\mathcal{O}^\star(2^{0.5n})$ time and $\mathcal{O}^\star(2^{0.249999n})$ space randomized algorithm for solving worst-case Subset Sum instances with $n$ integers. This is the first improvement over the long-standing $\mathcal{O}^\star(2^{n/2})$ time and $\mathcal{O}^\star(2^{n/4})$ space algorithm due to Schroeppel and Shamir (FOCS 1979). We breach this gap in two steps: (1) We present a space efficient reduction to the Orthogonal Vectors Problem (OV), one of the most central problem in Fine-Grained Complexity. The reduction is established via an intricate combination of the method of Schroeppel and Shamir, and the representation technique introduced by Howgrave-Graham and Joux (EUROCRYPT 2010) for designing Subset Sum algorithms for the average case regime. (2) We provide an algorithm for OV that detects an orthogonal pair among $N$ given vectors in $\{0,1\}^d$ with support size $d/4$ in time $\tilde{O}(N\cdot2^d/\binom{d}{d/4})$. Our algorithm for OV is based on and refines the representative families framework developed by Fomin, Lokshtanov, Panolan and Saurabh (J. ACM 2016). Our reduction uncovers a curious tight relation between Subset Sum and OV, because any improvement of our algorithm for OV would imply an improvement over the runtime of Schroeppel and Shamir, which is also a long standing open problem.
