Sökning: id:"swepub:oai:lup.lub.lu.se:43d4e602-8be4-48c3-946b-49a2e80b353d" >
Solving systems of ...
Solving systems of polynomial equations over GF(2) by a parity-counting self-reduction
-
- Björklund, Andreas (författare)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
- Kaski, Petteri (författare)
- Aalto University
-
- Williams, Ryan (författare)
- Massachusetts Institute of Technology
-
visa fler...
-
Chatzigiannakis, Ioannis (redaktör/utgivare)
-
Baier, Christel (redaktör/utgivare)
-
Leonardi, Stefano (redaktör/utgivare)
-
Flocchini, Paola (redaktör/utgivare)
-
visa färre...
-
(creator_code:org_t)
- 2019
- 2019
- Engelska.
-
Ingår i: 46th International Colloquium on Automata, Languages, and Programming : ICALP 2019 - ICALP 2019. - 1868-8969. - 9783959771092 ; 132, s. 1-26
- Relaterad länk:
-
http://dx.doi.org/10... (free)
-
visa fler...
-
https://lup.lub.lu.s...
-
https://doi.org/10.4...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Matematik -- Beräkningsmatematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Computational Mathematics (hsv//eng)
Nyckelord
- Equation systems
- Polynomial method
Publikations- och innehållstyp
- kon (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas