{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T08:39:36Z","timestamp":1648543176323},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,5,12]],"date-time":"2011-05-12T00:00:00Z","timestamp":1305158400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2012,4]]},"DOI":"10.1007\/s00224-011-9332-9","type":"journal-article","created":{"date-parts":[[2011,5,11]],"date-time":"2011-05-11T09:57:12Z","timestamp":1305107832000},"page":"516-536","source":"Crossref","is-referenced-by-count":0,"title":["On the Correlation Between Parity and Modular Polynomials"],"prefix":"10.1007","volume":"50","author":[{"given":"Anna","family":"G\u00e1l","sequence":"first","affiliation":[]},{"given":"Vladimir","family":"Trifonov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,5,12]]},"reference":[{"key":"9332_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"Ajtai, M.: $\\Sigma^{1}_{1}$ -formulae on finite structures. Ann. Pure Appl. Log. 24, 1\u201348 (1983)","journal-title":"Ann. Pure Appl. Log."},{"key":"9332_CR2","doi-asserted-by":"crossref","first-page":"580","DOI":"10.1109\/SFCS.1989.63538","volume-title":"Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science","author":"E. Allender","year":"1989","unstructured":"Allender, E.: A note on the power of threshold circuits. In: Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pp. 580\u2013584 (1989)"},{"key":"9332_CR3","first-page":"184","volume-title":"Proceedings of the 16th Annual IEEE Conference on Computational Complexity","author":"N. Alon","year":"2001","unstructured":"Alon, N., Beigel, R.: Lower bounds for approximations by low degree polynomials over\u00a0\u2124 m . In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, pp. 184\u2013187 (2001)"},{"key":"9332_CR4","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D. Barrington","year":"1989","unstructured":"Barrington, D.: Bounded-width polynomial size branching programs recognize exactly those languages in\u00a0NC 1. J. Comput. Syst. Sci. 38, 150\u2013164 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"9332_CR5","first-page":"580","volume-title":"Proceedings of the 30th Symposium on Foundations of Computer Science","author":"R. Beigel","year":"1989","unstructured":"Beigel, R., Maciel, A.: Upper and lower bounds for some depth-3 circuit classes. In: Proceedings of the 30th Symposium on Foundations of Computer Science, pp. 580\u2013584 (1989)"},{"key":"9332_CR6","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1016\/j.crma.2005.03.008","volume":"340","author":"J. Bourgain","year":"2005","unstructured":"Bourgain, J.: Estimation of certain exponential sums arising in complexity theory. C. R. Acad. Sci. Paris Ser. I 340, 627\u2013631 (2005)","journal-title":"C. R. Acad. Sci. Paris Ser. I"},{"key":"9332_CR7","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/BF01201278","volume":"29","author":"J.-Y. Cai","year":"1996","unstructured":"Cai, J.-Y., Green, F., Thierauf, T.: On the correlation of symmetric functions. Math. Syst. Theory 29, 245\u2013258 (1996)","journal-title":"Math. Syst. Theory"},{"key":"9332_CR8","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"Furst, M., Saxe, J., Sipser, M.: Parity, circuits, and the polynomial hierarchy. Math. Syst. Theory 17, 13\u201327 (1984)","journal-title":"Math. Syst. Theory"},{"key":"9332_CR9","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1007\/s002240000126","volume":"32","author":"F. Green","year":"1999","unstructured":"Green, F.: Exponential sums and circuits with single threshold gate and mod-gates. Theory Comput. Syst. 32, 453\u2013466 (1999)","journal-title":"Theory Comput. Syst."},{"key":"9332_CR10","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1109\/CCC.2002.1004341","volume-title":"Proceedings of the 17th Annual IEEE Conference on Computational Complexity","author":"F. Green","year":"2002","unstructured":"Green, F.: The correlation between parity and quadratic polynomials mod\u00a03. In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, pp. 65\u201372 (2002)"},{"key":"9332_CR11","doi-asserted-by":"crossref","unstructured":"Green, F., Roy, A., Straubing, H.: Bounds on an exponential sum arising in boolean circuit complexity. C.\u00a0R. Acad. Sci. Paris Ser. I 340 (2005)","DOI":"10.1016\/j.crma.2005.07.011"},{"key":"9332_CR12","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/0020-0190(94)00221-J","volume":"53","author":"M. Goldmann","year":"1995","unstructured":"Goldmann, M.: A note on the power of majority gates and modular gates. Inf. Process. Lett. 53, 321\u2013327 (1995)","journal-title":"Inf. Process. Lett."},{"key":"9332_CR13","first-page":"68","volume-title":"Proceedings of the 26th ACM Symposium on the Theory of Computing","author":"V. Grolmusz","year":"1994","unstructured":"Grolmusz, V.: A weight-size tradeoff for circuits with mod m gates. In: Proceedings of the 26th ACM Symposium on the Theory of Computing, pp. 68\u201374 (1994)"},{"issue":"4","key":"9332_CR14","doi-asserted-by":"crossref","first-page":"1209","DOI":"10.1137\/S0097539798340850","volume":"29","author":"V. Grolmusz","year":"2000","unstructured":"Grolmusz, V., Tardos, G.: Lower bounds for MOD p \u2013MOD m circuits. SIAM J. Comput. 29(4), 1209\u20131222 (2000)","journal-title":"SIAM J. Comput."},{"key":"9332_CR15","first-page":"99","volume-title":"Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science","author":"A. Hajnal","year":"1987","unstructured":"Hajnal, A., Maass, W., Pudl\u00e1k, P., Szegedy, M., Tur\u00e1n, G.: Threshold circuits of bounded depth. In: Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, pp. 99\u2013110 (1987)"},{"key":"9332_CR16","first-page":"334","volume-title":"Proceedings of MFCS","author":"K. Hansen","year":"2004","unstructured":"Hansen, K., Miltersen, P.: Some meet-in-the-middle circuit lower bounds. In: Proceedings of MFCS, pp. 334\u2013345 (2004)"},{"key":"9332_CR17","volume-title":"Computational Limitations of Small-Depth Circuits","author":"J. H\u00e5stad","year":"1986","unstructured":"H\u00e5stad, J.: Computational Limitations of Small-Depth Circuits. MIT Press, Cambridge (1986)"},{"issue":"2","key":"9332_CR18","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF01272517","volume":"1","author":"J. H\u00e5stad","year":"1991","unstructured":"H\u00e5stad, J., Goldmann, M.: On the power of small depth threshold circuits. Comput. Complex. 1(2), 113\u2013129 (1991)","journal-title":"Comput. Complex."},{"key":"9332_CR19","first-page":"48","volume-title":"Proceedings of the 26th ACM Symposium on the Theory of Computing","author":"M. Krause","year":"1994","unstructured":"Krause, M., Pudl\u00e1k, P.: On the computational power of depth 2 circuits with threshold and modulo gates. In: Proceedings of the 26th ACM Symposium on the Theory of Computing, pp. 48\u201357 (1994)"},{"key":"9332_CR20","volume-title":"Introduction to Finite Fields and Their Applications","author":"R. Lidl","year":"1986","unstructured":"Lidl, R., Niederreiter, H.: Introduction to Finite Fields and Their Applications, Cambridge University Press, Cambridge (1986)"},{"key":"9332_CR21","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0020-0190(93)90041-7","volume":"45","author":"A. Razborov","year":"1993","unstructured":"Razborov, A., Wigderson, A.: n \u03a9(log\u2009n) Lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom. Inf. Process. Lett. 45, 303\u2013307 (1993)","journal-title":"Inf. Process. Lett."},{"key":"9332_CR22","first-page":"77","volume-title":"Proceedings of the 19th Annual ACM Symposium on Theory of Computing","author":"R. Smolensky","year":"1987","unstructured":"Smolensky, R.: Algebraic methods in the theory of lower bounds for boolean circuit complexity. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pp.\u00a077\u201382 (1987)"},{"key":"9332_CR23","doi-asserted-by":"crossref","DOI":"10.1090\/coll\/023","volume-title":"Orthogonal Polynomials","author":"G. Szeg\u00f6","year":"1939","unstructured":"Szeg\u00f6, G.: Orthogonal Polynomials. Am. Math. Soc., Providence (1939)"},{"key":"9332_CR24","first-page":"1","volume-title":"Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science","author":"A. Yao","year":"1985","unstructured":"Yao, A.: Separating the polynomial hierarchy by oracles. In: Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science, pp. 1\u201310 (1985)"},{"key":"9332_CR25","first-page":"619","volume-title":"Proceedings of the 31th Annual IEEE Symposium on Foundations of Computer Science","author":"A. Yao","year":"1990","unstructured":"Yao, A.: On ACC and threshold circuits. In: Proceedings of the 31th Annual IEEE Symposium on Foundations of Computer Science, pp. 619\u2013627 (1990)"},{"key":"9332_CR26","first-page":"37","volume":"10","author":"S. Zabek","year":"1956","unstructured":"Zabek, S.: Sur la p\u00e9riodicit\u00e9 modulo m des suites de nombres ${n\\choose k}$ . Ann. Univ. Mariae Curie-Skl\u0304odowska A 10, 37\u201347 (1956)","journal-title":"Ann. Univ. Mariae Curie-Skl\u0304odowska A"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9332-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-011-9332-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9332-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T18:06:16Z","timestamp":1560189976000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-011-9332-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5,12]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["9332"],"URL":"https:\/\/doi.org\/10.1007\/s00224-011-9332-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5,12]]}}}