Learning Centre

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

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Björklund, Andreas
dc.contributor.author Kaski, Petteri
dc.contributor.author Williams, Ryan
dc.contributor.editor Chatzigiannakis, Ioannis
dc.contributor.editor Baier, Christel
dc.contributor.editor Leonardi, Stefano
dc.contributor.editor Flocchini, Paola
dc.date.accessioned 2019-08-15T08:27:40Z
dc.date.available 2019-08-15T08:27:40Z
dc.date.issued 2019-07-01
dc.identifier.citation 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 . , 26 , Leibniz international proceedings in informatics , vol. 132 , Schloss Dagstuhl-Leibniz-Zentrum für Informatik , pp. 1-13 , International Colloquium on Automata, Languages and Programming , Patras , Greece , 08/07/2019 . https://doi.org/10.4230/LIPIcs.ICALP.2019.26 en
dc.identifier.isbn 9783959771092
dc.identifier.issn 1868-8969
dc.identifier.other PURE UUID: d50f6c09-f0bf-46aa-81be-91e6587ce444
dc.identifier.other PURE ITEMURL: https://research.aalto.fi/en/publications/d50f6c09-f0bf-46aa-81be-91e6587ce444
dc.identifier.other PURE LINK: http://www.scopus.com/inward/record.url?scp=85069220126&partnerID=8YFLogxK
dc.identifier.other PURE FILEURL: https://research.aalto.fi/files/35681013/LIPIcs_ICALP_2019_26.pdf
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/39757
dc.description.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 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. en
dc.format.extent 1-13
dc.format.mimetype application/pdf
dc.language.iso en en
dc.publisher Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
dc.relation.ispartof International Colloquium on Automata, Languages, and Programming en
dc.relation.ispartofseries 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019 en
dc.relation.ispartofseries Leibniz international proceedings in informatics en
dc.relation.ispartofseries Volume 132 en
dc.rights openAccess en
dc.title Solving systems of polynomial equations over GF(2) by a parity-counting self-reduction en
dc.type A4 Artikkeli konferenssijulkaisussa fi
dc.description.version Peer reviewed en
dc.contributor.department Lund University
dc.contributor.department Helsinki Institute for Information Technology (HIIT)
dc.contributor.department Massachusetts Institute of Technology
dc.contributor.department Department of Computer Science en
dc.subject.keyword Equation systems
dc.subject.keyword Polynomial method
dc.identifier.urn URN:NBN:fi:aalto-201908154802
dc.identifier.doi 10.4230/LIPIcs.ICALP.2019.26
dc.type.version publishedVersion

Files in this item

Files Size Format View

There are no open access files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search archive

Advanced Search

article-iconSubmit a publication