×

Counting solutions to polynomial systems via reductions. (English) Zbl 1433.68161

Seidel, Raimund (ed.), 1st symposium on simplicity in algorithms. SOSA 2018, January 7–10, 2018, New Orleans, LA, USA. Co-located with the 29th ACM-SIAM symposium on discrete algorithms (SODA 2018). Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. OASIcs – OpenAccess Ser. Inform. 61, Article 6, 15 p. (2018).
Summary: 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)/\epsilon^2\) time algorithm for approximately counting the fraction of solutions to a system of \(s\) quadratic \(n\)-variate polynomials over \(\mathbb 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/\epsilon^2)\) time, so our algorithm behaves as a full derandomization of uniform sampling. The approximate-counting algorithm yields efficient approximate counting for other well-known problems, such as 2-SAT, NAE-3SAT, and 3-coloring. 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 NP-hard for degree-three polynomials over \(\mathbb F_2\); however, all known reductions increased the number of variables by a considerable amount. We give a subexponential-time reduction from counting solutions to \(k\)-CNF formulas to counting solutions to a degree-\(k^{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 constant-degree polynomials (even over \(\mathbb F_2\)) requires essentially \(2^n\) time. Similar results hold for counting orthogonal pairs of vectors over \(\mathbb F_p\).
For the entire collection see [Zbl 1387.68030].

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
11T06 Polynomials over finite fields
13P15 Solving polynomial systems; resultants
68Q25 Analysis of algorithms and problem complexity
68W20 Randomized algorithms
Full Text: DOI

References:

[1] Miklós Ajtai and Avi Wigderson. Deterministic simulation of probabilistic constant depth circuits. Advances in Computing Research, 5:199-222, 1989.
[2] Noga Alon and Jehoshua Bruck.Explicit constructions of depth-2 majority circuits for comparison and addition. SIAM J. Discrete Math., 7(1):1-8, 1994. doi:10.1137/ S0895480191218496. · Zbl 0802.68068
[3] Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta. Simple construction of almost k-wise independent random variables. Random Struct. Algorithms, 3(3):289-304, 1992. doi:10.1002/rsa.3240030308. · Zbl 0755.60002
[4] Yossi Azar, Rajeev Motwani, and Joseph Naor. Approximating probability distributions using small sample spaces. Combinatorica, 18(2):151-171, 1998. doi:10.1007/PL00009813. · Zbl 0917.60014
[5] :14
[6] Andrej Bogdanov and Emanuele Viola. Pseudorandom bits for polynomials. SIAM J. Comput., 39(6):2464-2486, 2010. doi:10.1137/070712109. · Zbl 1211.68215
[7] :15
[8] Andrej Bogdanov and Emanuele Viola. Pseudorandom bits for polynomials. SIAM J. Comput., 39(6):2464-2486, 2010. doi:10.1137/070712109. · Zbl 1211.68215
[9] Mark Braverman. Polylogarithmic independence fools AC 0 circuits. J. ACM, 57(5):28:1- 28:10, 2010. doi:10.1145/1754399.1754401. · Zbl 1327.68108
[10] Jehoshua Bruck and Roman Smolensky. Polynomial threshold functions, acˆ0 functions, and spectral norms. SIAM J. Comput., 21(1):33-42, 1992. doi:10.1137/0221003. · Zbl 0743.68063
[11] Jin-yi Cai, Xi Chen, Richard J. Lipton, and Pinyan Lu.On tractable exponential sums. In Der-Tsai Lee, Danny Z. Chen, and Shi Ying, editors, Frontiers in Algorithmics, 4th International Workshop, FAW 2010, Wuhan, China, August 11-13, 2010. Proceed- ings, volume 6213 of Lecture Notes in Computer Science, pages 148-159. Springer, 2010. doi:10.1007/978-3-642-14553-7_16. · Zbl 1288.68104
[12] Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. A duality between clause width and clause density for SAT. In 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 July 2006, Prague, Czech Republic, pages 252-260. IEEE Computer Society, 2006. doi:10.1109/CCC.2006.6.
[13] Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. The complexity of satisfiability of small depth circuits. In Jianer Chen and Fedor V. Fomin, editors, Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Den- mark, September 10-11, 2009, Revised Selected Papers, volume 5917 of Lecture Notes in Computer Science, pages 75-85. Springer, 2009. doi:10.1007/978-3-642-11269-0_6. · Zbl 1273.68159
[14] Timothy M. Chan and Ryan Williams. Deterministic apsp, orthogonal vectors, and more: Quickly derandomizing razborov-smolensky. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1246-1255. SIAM, 2016. doi:10.1137/ 1.9781611974331.ch87. · Zbl 1410.68286
[15] Radu Curticapean. Parity separation: A scientifically proven method for permanent weight loss. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 47:1-47:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. doi:10.4230/LIPIcs.ICALP.2016.47. · Zbl 1388.68221
[16] Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlen. Exponential time complexity of the permanent and the tutte polynomial. ACM Trans. Algorithms, 10(4):21:1-21:32, 2014. doi:10.1145/2635812. · Zbl 1398.68191
[17] Holger Dell and John Lapinskas. Fine-grained reductions from approximate counting to decision. CoRR, abs/1707.04609, 2017. arXiv:1707.04609. · Zbl 1427.68117
[18] Andrej Ehrenfeucht and Marek Karpinski. The computational complexity of (xor, and)counting problems. Technical Report TR-90-031, International Computer Science Institute, Berkeley, 1990. URL: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-033. pdf.
[19] Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, and Boban Velickovic. Approximations of general independent distributions.In S. Rao Kosaraju, Mike Fellows, Avi Wigderson, and John A. Ellis, editors, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages 10-16. ACM, 1992. doi:10.1145/129712.129714. · Zbl 0959.68553
[20] Oded Goldreich. In a world of p=bpp. In Oded Goldreich, editor, Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman, volume 6650 of Lecture Notes in Computer Science, pages 191-232. Springer, 2011. doi:10.1007/978-3-642-22670-0_20. · Zbl 1220.68005
[21] Parikshit Gopalan, Adam R. Klivans, Raghu Meka, Daniel Stefankovic, Santosh Vempala, and Eric Vigoda. An FPTAS for #knapsack and related counting problems. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 817-826. IEEE Computer Society, 2011. doi:10.1109/FOCS.2011.32. · Zbl 1292.68167
[22] Parikshit Gopalan, Raghu Meka, and Omer Reingold. DNF sparsification and a faster deterministic counting algorithm. Computational Complexity, 22(2):275-310, 2013. doi: 10.1007/s00037-013-0068-6. · Zbl 1286.68230
[23] Ben Gum and Richard J. Lipton. Cheaper by the dozen: Batched algorithms. In Vipin Kumar and Robert L. Grossman, editors, Proceedings of the First SIAM International Conference on Data Mining, SDM 2001, Chicago, IL, USA, April 5-7, 2001, pages 1-11. SIAM, 2001. doi:10.1137/1.9781611972719.23.
[24] Edward A. Hirsch. A fast deterministic algorithm for formulas that have many satisfying assignments. Logic Journal of the IGPL, 6(1):59-71, 1998. doi:10.1093/jigpal/6.1.59. · Zbl 0897.03043
[25] Christian Hoffmann. Exponential time complexity of weighted counting of independent sets. In Venkatesh Raman and Saket Saurabh, editors, Parameterized and Exact Compu- tation - 5th International Symposium, IPEC 2010, Chennai, India, December 13-15, 2010. Proceedings, volume 6478 of Lecture Notes in Computer Science, pages 180-191. Springer, 2010. doi:10.1007/978-3-642-17493-3_18. · Zbl 1309.68094
[26] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. doi:10.1006/jcss. 2001.1774. · Zbl 1006.68052
[27] Nathan Linial and Noam Nisan.Approximate inclusion-exclusion.Combinatorica, 10(4):349-365, 1990. doi:10.1007/BF02128670. · Zbl 0738.05009
[28] Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, R. Ryan Williams, and Huacheng Yu. Beating brute force for systems of polynomial equations over finite fields. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2190- 2202. SIAM, 2017. doi:10.1137/1.9781611974782.143. · Zbl 1433.11135
[29] Michael Luby and Boban Velickovic. On deterministic approximation of DNF. Algorithmica, 16(4/5):415-433, 1996. doi:10.1007/BF01940873. · Zbl 0857.68054
[30] Michael Luby, Boban Velickovic, and Avi Wigderson. Deterministic approximate counting of depth-2 circuits. In Second Israel Symposium on Theory of Computing Systems, ISTCS 1993, Natanya, Israel, June 7-9, 1993, Proceedings, pages 18-24. IEEE Computer Society, 1993. doi:10.1109/ISTCS.1993.253488. · Zbl 0850.68165
[31] Noam Nisan. Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63-70, 1991. doi:10.1007/BF01375474. · Zbl 0732.68056
[32] Michael O. Rabin. Probabilistic algorithms in finite fields. SIAM J. Comput., 9(2):273-280, 1980. doi:10.1137/0209024. · Zbl 0461.12012
[33] Luca Trevisan.A note on approximate counting for k-dnf.In Klaus Jansen, Sanjeev Khanna, José D. P. Rolim, and Dana Ron, editors, Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques, 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004, and 8th International Workshop on Randomization and Computation, RANDOM 2004, Cam- bridge, MA, USA, August 22-24, 2004, Proceedings, volume 3122 of Lecture Notes in Com- puter Science, pages 417-426. Springer, 2004. doi:10.1007/978-3-540-27821-4_37. · Zbl 1106.68427
[34] Emanuele Viola. The sum of D small-bias generators fools polynomials of degree D. Com- putational Complexity, 18(2):209-217, 2009. doi:10.1007/s00037-009-0273-5. · Zbl 1217.68157
[35] Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357-365, 2005. doi:10.1016/j.tcs.2005.09.023. · Zbl 1081.68095
[36] Ryan Williams and Huacheng Yu. Finding orthogonal vectors in discrete structures. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1867-1877. SIAM, 2014. doi:10.1137/1.9781611973402.135. · Zbl 1422.68276
[37] Virginia Vassilevska Williams, Joshua R. Wang, Richard Ryan Williams, and Huacheng Yu. Finding four-node subgraphs in triangle time. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1671-1680. SIAM, 2015. doi:10.1137/1. 9781611973730.111. · Zbl 1371.05292
[38] Alan R. Woods. Unsatisfiable systems of equations, over a finite field. In 39th Annual Symposium on Foundations of Computer Science, FOCS ’98, November 8-11, 1998, Palo Alto, California, USA, pages 202-211. IEEE Computer Society, 1998. doi:10.1109/SFCS. 1998.743444.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.