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 : ICALP 2019  ICALP 2019
 series title
 Leibniz International Proceedings in Informatics (LIPIcs)
 editor
 Chatzigiannakis, Ioannis ; Baier, Christel ; Leonardi, Stefano and Flocchini, Paola
 volume
 132
 article number
 26
 pages
 1  26
 publisher
 Schloss Dagstuhl  LeibnizZentrum für Informatik
 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
 20220426 03:26:06
@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 = {{46th International Colloquium on Automata, Languages, and Programming : ICALP 2019}}, editor = {{Chatzigiannakis, Ioannis and Baier, Christel and Leonardi, Stefano and Flocchini, Paola}}, isbn = {{9783959771092}}, issn = {{18688969}}, keywords = {{Equation systems; Polynomial method}}, language = {{eng}}, month = {{07}}, pages = {{126}}, publisher = {{Schloss Dagstuhl  LeibnizZentrum für Informatik}}, series = {{Leibniz International Proceedings in Informatics (LIPIcs)}}, title = {{Solving systems of polynomial equations over GF(2) by a paritycounting selfreduction}}, url = {{http://dx.doi.org/10.4230/LIPIcs.ICALP.2019.26}}, doi = {{10.4230/LIPIcs.ICALP.2019.26}}, volume = {{132}}, year = {{2019}}, }