Advanced

Solving systems of polynomial equations over GF(2) by a parity-counting self-reduction

Björklund, Andreas LU ; Kaski, Petteri and Williams, Ryan (2019) 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 In Leibniz International Proceedings in Informatics (LIPIcs) 132. p.1-26
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 worst-case algorithms that beat exhaustive search for this problem. In particular for degree-d equations modulo two in n variables, they gave an O2(1−1/(5d))n time algorithm, and for the special case d = 2 they gave an O20.876n time algorithm. We modify their approach in a way that improves these running times to O2(1−1/(27d))n and O20.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 worst-case algorithms that beat exhaustive search for this problem. In particular for degree-d equations modulo two in n variables, they gave an O2(1−1/(5d))n time algorithm, and for the special case d = 2 they gave an O20.876n time algorithm. We modify their approach in a way that improves these running times to O2(1−1/(27d))n and O20.804n, respectively. In particular, our latter bound - that holds for all systems of quadratic equations modulo 2 - comes close to the O20.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.

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
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- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
conference name
46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
conference location
Patras, Greece
conference dates
2019-07-09 - 2019-07-12
external identifiers
  • scopus:85069220126
ISSN
1868-8969
ISBN
9783959771092
DOI
10.4230/LIPIcs.ICALP.2019.26
language
English
LU publication?
yes
id
43d4e602-8be4-48c3-946b-49a2e80b353d
date added to LUP
2019-07-26 11:44:12
date last changed
2019-08-28 04:57:27
@inproceedings{43d4e602-8be4-48c3-946b-49a2e80b353d,
  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 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<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 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.</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         = {1868-8969},
  keyword      = {Equation systems,Polynomial method},
  language     = {eng},
  location     = {Patras, Greece},
  month        = {07},
  pages        = {1--26},
  publisher    = {Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing},
  title        = {Solving systems of polynomial equations over GF(2) by a parity-counting self-reduction},
  url          = {http://dx.doi.org/10.4230/LIPIcs.ICALP.2019.26},
  volume       = {132},
  year         = {2019},
}