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

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

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.

Details

Authors
Organisations
External organisations
  • Massachusetts Institute of Technology
  • Aalto University
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computational Mathematics

Keywords

  • Equation systems, Polynomial method
Original languageEnglish
Title of host publication46th International Colloquium on Automata, Languages, and Programming
Subtitle of host publicationICALP 2019
EditorsIoannis Chatzigiannakis, Christel Baier, Stefano Leonardi, Paola Flocchini
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages26:1-26:13
Volume132
ISBN (Electronic)9783959771092
Publication statusPublished - 2019 Jul 1
Publication categoryResearch
Peer-reviewedYes
Event46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 - Patras, Greece
Duration: 2019 Jul 92019 Jul 12

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
ISSN (Print)1868-8969

Conference

Conference46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
CountryGreece
CityPatras
Period2019/07/092019/07/12