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

Andreas Björklund, Petteri Kaski, Ryan Williams

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

6 Downloads (Pure)

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 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.

Original languageEnglish
Title of host publication46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
EditorsIoannis Chatzigiannakis, Christel Baier, Stefano Leonardi, Paola Flocchini
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages1-13
ISBN (Electronic)9783959771092
DOIs
Publication statusPublished - 1 Jul 2019
MoE publication typeA4 Article in a conference publication
EventInternational Colloquium on Automata, Languages, and Programming - Patras, Greece
Duration: 9 Jul 201912 Jul 2019
Conference number: 46

Publication series

NameLeibniz international proceedings in informatics
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume132
ISSN (Print)1868-8969

Conference

ConferenceInternational Colloquium on Automata, Languages, and Programming
Abbreviated titleICALP
CountryGreece
CityPatras
Period09/07/201912/07/2019

Keywords

  • Equation systems
  • Polynomial method

Fingerprint Dive into the research topics of 'Solving systems of polynomial equations over GF(2) by a parity-counting self-reduction'. Together they form a unique fingerprint.

  • Cite this

    Björklund, A., Kaski, P., & Williams, R. (2019). Solving systems of polynomial equations over GF(2) by a parity-counting self-reduction. In I. Chatzigiannakis, C. Baier, S. Leonardi, & P. Flocchini (Eds.), 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 (pp. 1-13). [26] (Leibniz international proceedings in informatics; Vol. 132). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ICALP.2019.26