Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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 O∗2(1−1/(5d))n time algorithm, and for the special case d = 2 they gave an O∗20.876n time algorithm. We modify their approach in a way that improves these running times to O∗2(1−1/(27d))n and O∗20.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 O∗2(1−1/(5d))n time algorithm, and for the special case d = 2 they gave an O∗20.876n time algorithm. We modify their approach in a way that improves these running times to O∗2(1−1/(27d))n and O∗20.804n, respectively. In particular, our latter bound - that holds for all systems of quadratic equations modulo 2 - comes close to the O∗20.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
; and
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 : 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 - Leibniz-Zentrum für Informatik
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
2022-04-26 03:26:06
@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    = {{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         = {{1868-8969}},
  keywords     = {{Equation systems; Polynomial method}},
  language     = {{eng}},
  month        = {{07}},
  pages        = {{1--26}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
  series       = {{Leibniz International Proceedings in Informatics (LIPIcs)}},
  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}},
  doi          = {{10.4230/LIPIcs.ICALP.2019.26}},
  volume       = {{132}},
  year         = {{2019}},
}