### 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^{∗}2^{0.876n} time algorithm. We modify their approach in a way that improves these running times to O^{∗}2^{(1}−1/(2^{7}d))^{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 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 language | English |
---|---|

Title of host publication | 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 |

Editors | Ioannis Chatzigiannakis, Christel Baier, Stefano Leonardi, Paola Flocchini |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Pages | 1-13 |

ISBN (Electronic) | 9783959771092 |

DOIs | |

Publication status | Published - 1 Jul 2019 |

MoE publication type | A4 Article in a conference publication |

Event | International Colloquium on Automata, Languages, and Programming - Patras, Greece Duration: 9 Jul 2019 → 12 Jul 2019 Conference number: 46 |

### Publication series

Name | Leibniz international proceedings in informatics |
---|---|

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Volume | 132 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | International Colloquium on Automata, Languages, and Programming |
---|---|

Abbreviated title | ICALP |

Country | Greece |

City | Patras |

Period | 09/07/2019 → 12/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

*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