Solving systems of polynomial equations over GF(2) by a paritycounting selfreduction
(2019) 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 In Leibniz International Proceedings in Informatics (LIPIcs) 132. p.126 Abstract
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 worstcase algorithms that beat exhaustive search for this problem. In particular for degreed 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^{7}d))^{n} and O^{∗}2^{0.804n}, respectively. In particular, our latter bound  that holds for all systems of quadratic equations modulo 2  comes close... (More)
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 worstcase algorithms that beat exhaustive search for this problem. In particular for degreed 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^{7}d))^{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 ValiantVazirani lemma can be used to reduce the solutionfinding problem to that of counting solutions modulo 2. 2. The monomials in the probabilistic polynomials used in this solutioncounting 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 solutioncounting 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.
(Less)
 author
 Björklund, Andreas ^{LU} ; Kaski, Petteri and Williams, Ryan
 organization
 publishing date
 20190701
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 Equation systems, Polynomial method
 host publication
 46th International Colloquium on Automata, Languages, and Programming
 series title
 Leibniz International Proceedings in Informatics (LIPIcs)
 editor
 Chatzigiannakis, Ioannis; Baier, Christel; Leonardi, Stefano; Flocchini, Paola; ; ; and
 volume
 132
 pages
 1  26
 publisher
 Schloss Dagstuhl LeibnizZentrum fur Informatik GmbH, Dagstuhl Publishing
 conference name
 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
 conference location
 Patras, Greece
 conference dates
 20190709  20190712
 external identifiers

 scopus:85069220126
 ISSN
 18688969
 ISBN
 9783959771092
 DOI
 10.4230/LIPIcs.ICALP.2019.26
 language
 English
 LU publication?
 yes
 id
 43d4e6028be448c3946b49a2e80b353d
 date added to LUP
 20190726 11:44:12
 date last changed
 20190828 04:57:27
@inproceedings{43d4e6028be448c3946b49a2e80b353d, abstract = {<p>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 worstcase algorithms that beat exhaustive search for this problem. In particular for degreed equations modulo two in n variables, they gave an O<sup>∗</sup>2<sup>(1</sup>−1/(5d))<sup>n</sup> time algorithm, and for the special case d = 2 they gave an O<sup>∗</sup>2<sup>0.876n</sup> time algorithm. We modify their approach in a way that improves these running times to O<sup>∗</sup>2<sup>(1</sup>−1/(2<sup>7</sup>d))<sup>n</sup> and O<sup>∗</sup>2<sup>0.804n</sup>, respectively. In particular, our latter bound  that holds for all systems of quadratic equations modulo 2  comes close to the O<sup>∗</sup>2<sup>0.792n</sup> 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 ValiantVazirani lemma can be used to reduce the solutionfinding problem to that of counting solutions modulo 2. 2. The monomials in the probabilistic polynomials used in this solutioncounting 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 solutioncounting 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.</p>}, author = {Björklund, Andreas and Kaski, Petteri and Williams, Ryan}, booktitle = {Leibniz International Proceedings in Informatics (LIPIcs)}, editor = {Chatzigiannakis, Ioannis and Baier, Christel and Leonardi, Stefano and Flocchini, Paola}, isbn = {9783959771092}, issn = {18688969}, keyword = {Equation systems,Polynomial method}, language = {eng}, location = {Patras, Greece}, month = {07}, pages = {126}, publisher = {Schloss Dagstuhl LeibnizZentrum fur Informatik GmbH, Dagstuhl Publishing}, title = {Solving systems of polynomial equations over GF(2) by a paritycounting selfreduction}, url = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2019.26}, volume = {132}, year = {2019}, }