Solving systems of polynomial equations over GF(2) by a parity-counting self-reduction
(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)
- author
- Björklund, Andreas LU ; Kaski, Petteri and Williams, Ryan
- organization
- publishing date
- 2019-07-01
- 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}}, }