{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T18:40:30Z","timestamp":1737484830208,"version":"3.33.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2007,10,17]],"date-time":"2007-10-17T00:00:00Z","timestamp":1192579200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2008,4]]},"DOI":"10.1007\/s00453-007-9097-3","type":"journal-article","created":{"date-parts":[[2007,10,16]],"date-time":"2007-10-16T14:36:46Z","timestamp":1192545406000},"page":"479-496","source":"Crossref","is-referenced-by-count":3,"title":["Algorithms for Modular Counting of Roots of Multivariate Polynomials"],"prefix":"10.1007","volume":"50","author":[{"given":"Parikshit","family":"Gopalan","sequence":"first","affiliation":[]},{"given":"Venkatesan","family":"Guruswami","sequence":"additional","affiliation":[]},{"given":"Richard J.","family":"Lipton","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,10,17]]},"reference":[{"key":"9097_CR1","series-title":"LNCS","first-page":"1","volume-title":"Proceedings of the 1996 Algorithmic Number Theory Symposium","author":"L. Adleman","year":"1996","unstructured":"Adleman, L., Huang, M.-D.: Counting rational points on curves and Abelian varieties over finite fields. In: Proceedings of the 1996 Algorithmic Number Theory Symposium. LNCS, vol. 1122, pp. 1\u201316. Springer, Berlin (1996)"},{"key":"9097_CR2","volume-title":"Algebra","author":"M. Artin","year":"1991","unstructured":"Artin, M.: Algebra. Prentice Hall, New York (1991)"},{"key":"9097_CR3","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1007\/BF01263423","volume":"4","author":"R. Beigel","year":"1994","unstructured":"Beigel, R., Tarui, J.: On ACC. Comput. Complex. 4, 350\u2013366 (1994)","journal-title":"Comput. Complex."},{"key":"9097_CR4","unstructured":"Ehrenfeucht, A., Karpinski, M.: The computational complexity of (xor, and)-counting problems. Tech. Report 8543-CS, ICSI, Berkeley (1990)"},{"key":"9097_CR5","doi-asserted-by":"crossref","unstructured":"Grigoriev, D., Karpinski, M.: An approximation algorithm for the number of zeroes of arbitrary polynomials over GF[q]. In: Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS\u201991), pp. 662\u2013669 (1991)","DOI":"10.1109\/SFCS.1991.185433"},{"key":"9097_CR6","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Vardy, A.: Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. In: Proceedings of the ACM-SIAM symposium on Discrete Algorithms (SODA\u201905), pp. 470\u2013478 (2005)","DOI":"10.1109\/TIT.2005.850102"},{"key":"9097_CR7","unstructured":"Huang, M.-D., Ierardi, D.: Counting rational points on curves over finite fields. In: Proceedings of the 34th IEEE Symposium on Foundations of Computer Science (FOCS\u201993), pp. 616\u2013625 (1993)"},{"key":"9097_CR8","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/s000370050029","volume":"8","author":"M.-D. Huang","year":"1999","unstructured":"Huang, M.-D., Wong, Y.: Solvability of systems of polynomial congruences modulo a large prime. J. Comput. Complex. 8, 227\u2013257 (1999)","journal-title":"J. Comput. Complex."},{"key":"9097_CR9","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1006\/jagm.1993.1014","volume":"14","author":"M. Karpinski","year":"1993","unstructured":"Karpinski, M., Luby, M.: Approximating the number of zeroes of a GF[2] polynomial. J. Algorithms 14, 280\u2013287 (1993)","journal-title":"J. Algorithms"},{"key":"9097_CR10","doi-asserted-by":"crossref","unstructured":"Kedlaya, K.: Computing Zeta functions via p-adic cohomology. In: Algorithmic Number Theory Symposium (ANTS), pp. 1\u201317 (2004)","DOI":"10.1007\/978-3-540-24847-7_1"},{"issue":"2\u20133","key":"9097_CR11","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/j.jco.2003.08.009","volume":"20","author":"A. Lauder","year":"2004","unstructured":"Lauder, A., Wan, D.: Computing zeta functions of Artin-Schreier curves over finite fields ii. J. Complex. 20(2\u20133), 331\u2013349 (2004)","journal-title":"J. Complex."},{"key":"9097_CR12","unstructured":"Lauder, A., Wan, D.: Counting points on varieties over finite fields of small characteristic. In: Buhler, J.P., Stevenhagen, P. (eds.) Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography (Mathematical Sciences Research Institute Publications). Cambridge University Press (2007, to appear)"},{"key":"9097_CR13","volume-title":"Finite Fields, Encylopedia of Mathematics and Its Applications","author":"R. Lidl","year":"1997","unstructured":"Lidl, R., Niederreiter, H.: Finite Fields, Encylopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge (1997)"},{"key":"9097_CR14","doi-asserted-by":"crossref","unstructured":"Luby, M., Velickovi\u0107, B., Wigderson, A.: Deterministic approximate counting of depth-2 circuits. In: Israel Symposium on Theory of Computing Systems, pp. 18\u201324 (1993)","DOI":"10.1109\/ISTCS.1993.253488"},{"key":"9097_CR15","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511752490","volume-title":"Diophantine Equations Over Function Fields","author":"R.C. Mason","year":"1984","unstructured":"Mason, R.C.: Diophantine Equations Over Function Fields. Cambridge University Press, Cambridge (1984)"},{"issue":"1","key":"9097_CR16","doi-asserted-by":"crossref","first-page":"241","DOI":"10.2307\/2375042","volume":"117","author":"O. Moreno","year":"1995","unstructured":"Moreno, O., Moreno, C.J.: Improvements of the Chevalley-Warning and the Ax-Katz theorems. Am. J. Math. 117(1), 241\u2013244 (1995)","journal-title":"Am. J. Math."},{"key":"9097_CR17","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison\u2013Wesley, Reading (1994)"},{"key":"9097_CR18","doi-asserted-by":"crossref","first-page":"745","DOI":"10.1090\/S0025-5718-1990-1035941-X","volume":"55","author":"J. Pila","year":"1990","unstructured":"Pila, J.: Frobenius maps of Abelian varieties and finding roots of unity in finite fields. Math. Comput. 55, 745\u2013763 (1990)","journal-title":"Math. Comput."},{"key":"9097_CR19","doi-asserted-by":"crossref","first-page":"219","DOI":"10.5802\/jtnb.142","volume":"7","author":"R. Schoof","year":"1995","unstructured":"Schoof, R.: Counting points on elliptic curves over finite fields. J. Th\u2019eor. Nr. Bord. 7, 219\u2013254 (1995)","journal-title":"J. Th\u2019eor. Nr. Bord."},{"issue":"5","key":"9097_CR20","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S. Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20(5), 865\u2013877 (1991)","journal-title":"SIAM J. Comput."},{"key":"9097_CR21","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 189\u2013201 (1979)","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"9097_CR22","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Completeness for parity problems. In: Proc. 11th International Computing and Combinatorics Conference (COCOON\u201905), pp. 1\u20138 (2005)","DOI":"10.1007\/11533719_1"},{"key":"9097_CR23","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Accidental algorithms. In: Proc. 47th IEEE Symposium on Foundations of Computer Science (FOCS\u201906), pp. 509\u2013517 (2006)","DOI":"10.1109\/FOCS.2006.7"},{"key":"9097_CR24","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L.G. Valiant","year":"1986","unstructured":"Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solutions. Theor. Comput. Sci. 47, 85\u201393 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"9097_CR25","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1007\/BF01202042","volume":"6","author":"J. Gathen von zur","year":"1996","unstructured":"von zur Gathen, J., Karpinski, M., Shparlinski, I.: Counting curves and their projections. Comput. Complex. 6, 64\u201399 (1996)","journal-title":"Comput. Complex."},{"key":"9097_CR26","first-page":"45","volume":"123","author":"D. Wan","year":"1995","unstructured":"Wan, D.: A Chevalley-Warning approach to p-adic estimate of character sums. Proc. Am. Math. Soc. 123, 45\u201354 (1995)","journal-title":"Proc. Am. Math. Soc."},{"key":"9097_CR27","first-page":"135","volume":"225","author":"D. Wan","year":"1999","unstructured":"Wan, D.: Computing Zeta functions over finite fields. Contemp. Math. 225, 135\u2013141 (1999)","journal-title":"Contemp. Math."},{"key":"9097_CR28","doi-asserted-by":"crossref","unstructured":"Wan, D.: Modular counting of rational points on sparse equations over finite fields. Found. Comput. Math. (2006, to appear)","DOI":"10.1007\/s10208-007-0245-y"},{"key":"9097_CR29","unstructured":"Wan, D.: Personal communication (April 2006)"},{"key":"9097_CR30","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: On ACC and threshold circuits. In: 31st IEEE Symposium on Foundations of Computer Science (FOCS\u201990), pp. 619\u2013627 (1990)","DOI":"10.1109\/FSCS.1990.89583"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9097-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9097-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9097-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T18:02:15Z","timestamp":1737482535000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9097-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,17]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,4]]}},"alternative-id":["9097"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9097-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2007,10,17]]}}}