Abstract
This paper provides both positive and negative results for counting solutions to systems of polynomial equations over a finite field. The general idea is to try to reduce the problem to counting solutions to a single polynomial, where the task is easier. In both cases, simple methods are utilized that we expect will have wider applicability (far beyond algebra).
First, we give an efficient deterministic reduction from approximate counting for a system of (arbitrary) polynomial equations to approximate counting for one equation, over any finite field. We apply this reduction to give a deterministic poly(n,s,log p)/eps^2 time algorithm for approximately counting the fraction of solutions to a system of s quadratic nvariate polynomials over F_p (the finite field of prime order p) to within an additive eps factor, for any prime p. Note that uniform random sampling would already require Omega(s/eps^2) time, so our algorithm behaves as a full derandomization of uniform sampling. The approximatecounting algorithm yields efficient approximate counting for other wellknown problems, such as 2SAT, NAE3SAT, and 3Coloring. As a corollary, there is a deterministic algorithm (with analogous running time) for producing solutions to such systems which have at least eps p^n solutions.
Second, we consider the difficulty of exactly counting solutions to a single polynomial of constant degree, over a finite field. (Note that finding a solution in this case is easy.) It has been known for over 20 years that this counting problem is already NPhard for degreethree polynomials over F_2; however, all known reductions increased the number of variables by a considerable amount. We give a subexponentialtime reduction from counting solutions to kCNF formulas to counting solutions to a degreek^{O(k)} polynomial (over any finite field of O(1) order) which exactly preserves the number of variables. As a corollary, the Strong Exponential Time Hypothesis (even its weak counting variant #SETH) implies that counting solutions to constantdegree polynomials (even over F_2) requires essentially 2^n time. Similar results hold for counting orthogonal pairs of vectors over F_p.
BibTeX  Entry
@InProceedings{williams:OASIcs:2018:8307,
author = {R. Ryan Williams},
title = {{Counting Solutions to Polynomial Systems via Reductions}},
booktitle = {1st Symposium on Simplicity in Algorithms (SOSA 2018)},
pages = {6:16:15},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {9783959770644},
ISSN = {21906807},
year = {2018},
volume = {61},
editor = {Raimund Seidel},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8307},
URN = {urn:nbn:de:0030drops83078},
doi = {10.4230/OASIcs.SOSA.2018.6},
annote = {Keywords: counting complexity, polynomial equations, finite field, derandomization, strong exponential time hypothesis}
}
Keywords: 

counting complexity, polynomial equations, finite field, derandomization, strong exponential time hypothesis 
Collection: 

1st Symposium on Simplicity in Algorithms (SOSA 2018) 
Issue Date: 

2018 
Date of publication: 

05.01.2018 