论文标题
通过多个奇偶校验计算，改进了与GF（2）求解多项式系统的算法
Improved Algorithms for Solving Polynomial Systems over GF(2) by Multiple Parity-Counting
论文作者
论文摘要
我们考虑了找到$ n $ n $变量的多元多项式方程系统的解决方案，超过$ \ mathbb {f} _2 $。对于$ d = 2 $，该问题最著名的算法是Bardet等人。 [J。复杂性，2013年]，并显示在时间$ o（2^{0.792n}）$下运行，在实验发现的假设下，该假设可容纳随机方程系统。该问题最著名的最坏情况算法是Björklund等人。 [ICALP'19]。它在$ d = 2 $和$ o（2^{（1-1/（2.7d））n} n}）n $ d = 2 $（2^{0.804n}）$上运行$ o（2^{0.804n}）$ for $ d> 2 $。 在本文中，我们设计了一种最糟糕的算法，该算法改进了Björklund等人。它在时间上运行$ O（2^{0.6943n}）$（或$ o（1.6181^n）$），$ d = 2 $和$ o（2^{（1-1/（2d））n n} n} n} n} n}）$ for $ d>> 2 $。因此，我们的算法优于所有已知的最坏情况算法，以及对随机方程系统进行分析的算法。我们还设计了第二种算法，该算法将所有解决方案输出到多项式系统，并且具有与第一个系统相似的复杂性（前提是解决方案的数量不太大）。 Björklund等人的工作中的一个核心思想。是为了减少在$ \ mathbb {f} _2 $上找到对多项式系统的解决方案的问题，以计算所有解决方案的奇偶校验。然后，将均衡实例简化为许多较小的平等计数实例。我们的主要观察结果是，这些较小的实例是相关的，可以通过新算法与我们称之为多个奇偶校验计数的问题更有效地解决。
We consider the problem of finding a solution to a multivariate polynomial equation system of degree $d$ in $n$ variables over $\mathbb{F}_2$. For $d=2$, the best-known algorithm for the problem is by Bardet et al. [J. Complexity, 2013] and was shown to run in time $O(2^{0.792n})$ under assumptions that were experimentally found to hold for random equation systems. The best-known worst-case algorithm for the problem is due to Björklund et al. [ICALP'19]. It runs in time $O(2^{0.804n})$ for $d = 2$ and $O(2^{(1 - 1/(2.7d))n})$ for $d > 2$. In this paper, we devise a worst-case algorithm that improves the one by Björklund et al. It runs in time $O(2^{0.6943n})$ (or $O(1.6181^n)$) for $d = 2$ and $O(2^{(1 - 1/(2d))n})$ for $d > 2$. Our algorithm thus outperforms all known worst-case algorithms, as well as ones analyzed for random equation systems. We also devise a second algorithm that outputs all solutions to a polynomial system and has similar complexity to the first (provided that the number of solutions is not too large). A central idea in the work of Björklund et al. was to reduce the problem of finding a solution to a polynomial system over $\mathbb{F}_2$ to the problem of counting the parity of all solutions. A parity-counting instance was then reduced to many smaller parity-counting instances. Our main observation is that these smaller instances are related and can be solved more efficiently by a new algorithm to a problem which we call multiple parity-counting.
