Björklund, Andreas ;
Kaski, Petteri ;
Williams, Ryan
Solving Systems of Polynomial Equations over GF(2) by a ParityCounting SelfReduction
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 worstcase algorithms that beat exhaustive search for this problem. In particular for degreed equations modulo two in n variables, they gave an O^*(2^{(11/(5d))n}) time algorithm, and for the special case d=2 they gave an O^*(2^{0.876n}) time algorithm.
We modify their approach in a way that improves these running times to O^*(2^{(11/(2.7d))n}) and O^*{2^{0.804n}), respectively. In particular, our latter bound  that holds for all systems of quadratic equations modulo 2  comes close to the O^*(2^{0.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 ValiantVazirani lemma can be used to reduce the solutionfinding problem to that of counting solutions modulo 2.
2) The monomials in the probabilistic polynomials used in this solutioncounting 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 solutioncounting 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.
BibTeX  Entry
@InProceedings{bjrklund_et_al:LIPIcs:2019:10602,
author = {Andreas Bj{\"o}rklund and Petteri Kaski and Ryan Williams},
title = {{Solving Systems of Polynomial Equations over GF(2) by a ParityCounting SelfReduction}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {26:126:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10602},
URN = {urn:nbn:de:0030drops106023},
doi = {10.4230/LIPIcs.ICALP.2019.26},
annote = {Keywords: equation systems, polynomial method}
}
04.07.2019
Keywords: 

equation systems, polynomial method 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 