2026-08-02T00:50:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10602 2024-03-06T10:46:15Z ddc:004 open_access

Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-Reduction Björklund, Andreas Kaski, Petteri Williams, Ryan equation systems polynomial method We consider the problem of finding solutions to systems of polynomial equations over a finite field. Lokshtanov et al. [SODA'17] recently obtained the first worst-case algorithms that beat exhaustive search for this problem. In particular for degree-d equations modulo two in n variables, they gave an O^*(2^{(1-1/(5d))n}) time algorithm, and for the special case d=2 they gave an O^*(2^{0.876n}) time algorithm. We modify their approach in a way that improves these running times to O^*(2^{(1-1/(2.7d))n}) and O^*{2^{0.804n}), respectively. In particular, our latter bound - that holds for all systems of quadratic equations modulo 2 - comes close to the O^*(2^{0.792n}) expected time bound of an algorithm empirically found to hold for random equation systems in Bardet et al. [J. Complexity, 2013]. Our improvement involves three observations: 1) The Valiant-Vazirani lemma can be used to reduce the solution-finding problem to that of counting solutions modulo 2. 2) The monomials in the probabilistic polynomials used in this solution-counting modulo 2 have a special form that we exploit to obtain better bounds on their number than in Lokshtanov et al. [SODA'17]. 3) The problem of solution-counting modulo 2 can be "embedded" in a smaller instance of the original problem, which enables us to apply the algorithm as a subroutine to itself. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andreas Björklund and Petteri Kaski and Ryan Williams 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.26 urn:nbn:de:0030-drops-106023 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.26 eng https://creativecommons.org/licenses/by/3.0/legalcode