{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T06:10:02Z","timestamp":1737094202717,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540430025"},{"type":"electronic","value":"9783540452942"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45294-x_26","type":"book-chapter","created":{"date-parts":[[2007,6,12]],"date-time":"2007-06-12T02:45:12Z","timestamp":1181616312000},"page":"305-316","source":"Crossref","is-referenced-by-count":0,"title":["On Polynomial Representations of Boolean Functions Related to Some Number Theoretic Problems"],"prefix":"10.1007","author":[{"given":"Erion","family":"Plaku","sequence":"first","affiliation":[]},{"given":"Igor E.","family":"Shparlinski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,11,26]]},"reference":[{"key":"26_CR1","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1006\/jcss.2000.1725","volume":"62","author":"E. Allender","year":"2001","unstructured":"E. Allender, M. Saks and I. E. Shparlinski, \u2018A lower bound for primality\u2019, J. of Comp. and Syst. Sci., 62 (2001), 356\u2013366.","journal-title":"J. of Comp. and Syst. Sci."},{"key":"26_CR2","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/BF01263424","volume":"4","author":"D. Barrington","year":"1994","unstructured":"D. Barrington, R. Beigel, and S. Rudich, \u2018Representing Boolean functions as polynomials modulo composite integers\u2019, Comp. Compl., 4, (1994), 367\u2013382.","journal-title":"Comp. Compl."},{"key":"26_CR3","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/PL00001597","volume":"7","author":"D. Barrington","year":"1998","unstructured":"D. Barrington and G. Tardos, \u2018A lower bound on the MOD 6 degree of the OR function\u2019 Comp. Compl., 7 (1998), 99\u2013108.","journal-title":"Comp. Compl."},{"key":"26_CR4","doi-asserted-by":"crossref","unstructured":"A. Bernasconi, C. Damm and I. E. Shparlinski, \u2018On the average sensitivity of testing square-free numbers\u2019, Proc. 5th Intern. Computing and Combinatorics Conf., Tokyo, 1999, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1999, v.1627, 291\u2013299.","DOI":"10.1007\/3-540-48686-0_29"},{"key":"26_CR5","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/PL00001600","volume":"9","author":"A. Bernasconi","year":"2000","unstructured":"A. Bernasconi, C. Damm and I. E. Shparlinski, \u2018The average sensitivity of squarefreeness\u2019, Comp. Compl. 9 (2000), 39\u201351.","journal-title":"Comp. Compl."},{"key":"26_CR6","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1006\/inco.2000.3017","volume":"168","author":"A. Bernasconi","year":"2001","unstructured":"A. Bernasconi, C. Damm and I. E. Shparlinski, \u2018Circuit and decision tree complexity of some number theoretic problems\u2019, Inform. and Comp., 168 (2001), 113\u2013124.","journal-title":"Inform. and Comp."},{"key":"26_CR7","series-title":"Lect. Notes in Comp. Sci.","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/3-540-49116-3_4","volume-title":"Circuit complexity of testing square-free numbers","author":"A. Bernasconi","year":"1999","unstructured":"A. Bernasconi and I. E. Shparlinski, \u2018Circuit complexity of testing square-free numbers\u2019, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1563 (1999), 47\u201356."},{"key":"26_CR8","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1137\/0403015","volume":"3","author":"J. Bruck","year":"1990","unstructured":"J. Bruck, \u2018Harmonic analysis of polynomial threshold functions\u2019, SIAM J. Discr. Math., 3 (1990), 168\u2013177.","journal-title":"SIAM J. Discr. Math."},{"key":"26_CR9","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/0221003","volume":"21","author":"J. Bruck","year":"1992","unstructured":"J. Bruck and R. Smolensky, \u2018Polynomial threshold functions, AC 0 functions, and spectral norms\u2019, SIAM J. Comp., 21 (1992), 33\u201342.","journal-title":"SIAM J. Comp."},{"key":"26_CR10","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/BF01272076","volume":"2","author":"N. H. Bshouty","year":"1992","unstructured":"N. H. Bshouty, Y. Mansour, B. Schieber and P. Tiwari, \u2018Fast exponentiation using the truncation operations\u2019, Comp. Compl., 2 (1992), 244\u2013255.","journal-title":"Comp. Compl."},{"key":"26_CR11","volume-title":"Algebraic complexity theory","author":"P. B\u00fcrgisser","year":"1996","unstructured":"P. B\u00fcrgisser, M. Clausen and M. A. Shokrollahi, Algebraic complexity theory, Springer-Verlag, Berlin, 1996."},{"key":"26_CR12","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/s001450010002","volume":"13","author":"D. Coppersmith","year":"2000","unstructured":"D. Coppersmith and I. E. Shparlinski, \u2018On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping\u2019, J. Cryptology, 13 (2000), 339\u2013360.","journal-title":"J. Cryptology"},{"key":"26_CR13","volume-title":"Graduate Texts in Mathematics","author":"H. Davenport","year":"2000","unstructured":"H. Davenport, Multiplicative number theory, Graduate Texts in Mathematics, 74. Springer-Verlag, New York, 2000."},{"key":"26_CR14","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/BF01305949","volume":"14","author":"C. Gotsman","year":"1994","unstructured":"C. Gotsman and N. Linial, \u2018Spectral properties of threshold functions\u2019, Combinatorica, 14 (1994), 35\u201350.","journal-title":"Combinatorica"},{"key":"26_CR15","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/PL00001599","volume":"9","author":"F. Green","year":"2000","unstructured":"F. Green, \u2018A complex-number Fourier technique for lower bounds on the mod-m degree\u2019, Comp. Compl., 9 (2000), 16\u201338.","journal-title":"Comp. Compl."},{"key":"26_CR16","unstructured":"D. Grigoriev, \u2018Lower bounds in the algebraic computational complexity\u2019, Zapiski Nauchn. Semin. Leningr. Otdel. Matem. Inst. Acad. Sci. USSR, 118 (1982), 25\u201382 (in Russian)."},{"key":"26_CR17","first-page":"204","volume":"332","author":"D. R. Heath-Brown","year":"1982","unstructured":"D. R. Heath-Brown, \u2018The least square-free number in an arithmetic progression\u2019, J. Reine Angew. Math., 332 (1982), 204\u2013220.","journal-title":"J. Reine Angew. Math."},{"key":"26_CR18","unstructured":"A. G. Khovanski, Fewnomials, Amer. Math. Soc., Providence, RI, 1997."},{"key":"26_CR19","doi-asserted-by":"crossref","unstructured":"M. Krause and Pudl\u00e1k, \u2018On computing Boolean functions by sparse real polynomials\u2019, Proc. 36th IEEE Symp. on Foundations of Comp. Sci., 1995, 682\u2013691.","DOI":"10.1109\/SFCS.1995.492670"},{"key":"26_CR20","unstructured":"F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes, North-Holland, Amsterdam, 1977."},{"key":"26_CR21","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1145\/103516.103522","volume":"38","author":"Y. Mansour","year":"1991","unstructured":"Y. Mansour, B. Schieber and P. Tiwari, \u2018A lower bound for integer greatest common divisor computations\u2019, J. Assoc. Comp. Mach., 38 (1991), 453\u2013471.","journal-title":"J. Assoc. Comp. Mach."},{"key":"26_CR22","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1137\/0220020","volume":"20","author":"Y. Mansour","year":"1991","unstructured":"Y. Mansour, B. Schieber and P. Tiwari, \u2018Lower bounds for computation with the floor operations\u2019, SIAM J. Comp., 20 (1991), 315\u2013327.","journal-title":"SIAM J. Comp."},{"key":"26_CR23","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0020-0190(91)90227-9","volume":"38","author":"J. Meid\u00e2nis","year":"1991","unstructured":"J. Meid\u00e2nis, \u2018Lower bounds for arithmetic problems\u2019, Inform. Proc. Letters, 38 (1991), 83\u201387.","journal-title":"Inform. Proc. Letters"},{"key":"26_CR24","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01263419","volume":"4","author":"N. Nisan","year":"1994","unstructured":"N. Nisan and M. Szegedy, \u2018On the degree of Boolean functions as real polynomials\u2019, Comp. Compl., 4 (1994), 301\u2013313.","journal-title":"Comp. Compl."},{"key":"26_CR25","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1137\/0220005","volume":"20","author":"I. Parberry","year":"1991","unstructured":"I. Parberry and P. Yuan Yan, \u2018Improved upper and lower time bounds for parallel random access machines without simultaneous writes\u2019, SIAM J. Comp., 20 (1991), 88\u201399.","journal-title":"SIAM J. Comp."},{"key":"26_CR26","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1216\/RMJ-1984-14-4-851","volume":"14","author":"J.-J. Risler","year":"1984","unstructured":"J.-J. Risler, \u2018Khovansky\u2019s theorem and complexity theory\u2019, Rocky Mountain J. Math., 14 (1984), 851\u2013853.","journal-title":"Rocky Mountain J. Math."},{"key":"26_CR27","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1137\/0214014","volume":"14","author":"J.-J. Risler","year":"1985","unstructured":"J.-J. Risler, \u2018Additive complexity of real polynomials\u2019, SIAM J. Comp., 14 (1985), 178\u2013183.","journal-title":"SIAM J. Comp."},{"key":"26_CR28","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-1-4615-2696-4_1","volume-title":"Theoretical advances in neural computing and learning","author":"V. Roychowdhry","year":"1994","unstructured":"V. Roychowdhry, K.-Y. Siu and A. Orlitsky, \u2018Neural models and spectral methods\u2019, Theoretical advances in neural computing and learning, Kluwer Acad. Publ., Dordrecht, 1994, 3\u201336."},{"key":"26_CR29","doi-asserted-by":"crossref","unstructured":"I. E. Shparlinski, Number theoretic methods in cryptography: Complexity lower bounds, Birkh\u00e4user, 1999.","DOI":"10.1007\/978-3-0348-8664-2"},{"issue":"1","key":"26_CR30","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1137\/S0895480193255505","volume":"9","author":"S.-C. Tsai","year":"1996","unstructured":"S.-C. Tsai, \u2018Lower bounds on representing Boolean functions as polynomials in \u2124\u2124 m\u2019, SIAM J. Discr. Math., 9(1) (1996), 55\u201362.","journal-title":"SIAM J. Discr. Math."},{"key":"26_CR31","volume-title":"The complexity of Boolean functions","author":"I. Wegener","year":"1987","unstructured":"I. Wegener, The complexity of Boolean functions, Wiley-Teubner Series in Comp. Sci., Stuttgart, 1987."},{"key":"26_CR32","unstructured":"A. Woods, \u2018Subset sum \u201ccubes\u201d and the complexity of prime testing\u2018, Preprint, 2001, 1\u201317. Available from http:\/\/www.maths.uwa.edu.au\/~woods\/alan_research.html ."}],"container-title":["Lecture Notes in Computer Science","FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45294-X_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T05:54:25Z","timestamp":1737093265000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45294-X_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540430025","9783540452942"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/3-540-45294-x_26","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}