{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T05:22:54Z","timestamp":1772083374253,"version":"3.50.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,8,4]],"date-time":"2011-08-04T00:00:00Z","timestamp":1312416000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2012,3]]},"DOI":"10.1007\/s00037-011-0020-6","type":"journal-article","created":{"date-parts":[[2011,8,3]],"date-time":"2011-08-03T19:16:00Z","timestamp":1312398960000},"page":"63-81","source":"Crossref","is-referenced-by-count":7,"title":["Random low-degree polynomials are hard to approximate"],"prefix":"10.1007","volume":"21","author":[{"given":"Ido","family":"Ben-Eliezer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rani","family":"Hod","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shachar","family":"Lovett","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,8,4]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0012-365X(83)90253-4","volume":"46","author":"N. Alon","year":"1983","unstructured":"Alon N. (1983) On the density of sets of vectors. Discrete Mathematics 46: 199\u2013202","journal-title":"Discrete Mathematics"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"N. Alon, I. Ben-Eliezer & M. Krivelevich (2008). Small sample spaces cannot fool low degree polynomials. In Proceedings of the 12th International Workshop on Randomization and Computation (RANDOM), 266\u2013275.","DOI":"10.1007\/978-3-540-85363-3_22"},{"issue":"2","key":"20_CR3","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1016\/0022-0000(92)90047-M","volume":"45","author":"L. Babai","year":"1992","unstructured":"Babai L., Nisan N., Szegedy M. (1992) Multiparty protocols, pseudorandom generators for logspace and time-space trade-offs. Journal of Computer and System Sciences 45(2): 204\u2013232","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson & S. Kopparty (2009). Affine dispersers from subspace polynomials. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), 65\u201374.","DOI":"10.1145\/1536414.1536426"},{"key":"20_CR5","unstructured":"G. Cohen, I. Honkala, S. Litsyn & A. Lobstein (1997). Covering Codes. North\u2013Holland."},{"issue":"1","key":"20_CR6","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0097-3165(83)90038-9","volume":"34","author":"P. Frankl","year":"1983","unstructured":"Frankl P. (1983) On the trace of finite sets. Journal of Combinatorial Theory, Series A 34(1): 41\u201345","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"P. Gopalan, A.R. Klivans & D. Zuckerman (2008). List-decoding Reed\u2013Muller codes over small fields. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), 265\u2013274.","DOI":"10.1145\/1374376.1374417"},{"issue":"3","key":"20_CR8","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/s00039-001-0332-9","volume":"11","author":"W.T. Gowers","year":"2001","unstructured":"Gowers W.T. (2001) A new proof of Szemer\u00e9di\u2019s theorem. Geometric and Functional Analysis 11(3): 465\u2013588","journal-title":"Geometric and Functional Analysis"},{"key":"20_CR9","unstructured":"B. Green & T. Tao (2007). The distribution of polynomials over finite fields, with applications to the Gowers Norm. Submitted."},{"key":"20_CR10","unstructured":"S. Jukna (2001). Extremal Combinatorics with Applications in Computer Science. Springer\u2013Verlag."},{"issue":"6","key":"20_CR11","doi-asserted-by":"crossref","first-page":"752","DOI":"10.1109\/TIT.1970.1054545","volume":"16","author":"T. Kasami","year":"1970","unstructured":"Kasami T., Tokura N. (1970) On the weight structure of Reed\u2013Muller codes. IEEE Transactions on Information Theory 16(6): 752\u2013759","journal-title":"On the weight structure of Reed\u2013Muller codes. IEEE Transactions on Information Theory"},{"issue":"4","key":"20_CR12","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1016\/S0019-9958(76)90355-7","volume":"30","author":"T. Kasami","year":"1976","unstructured":"Kasami T., Tokura N., Azumi S. (1976) On the weight enumeration of weights less than 2.5d of Reed\u2013Muller codes. Information and Control 30(4): 380\u2013395","journal-title":"Information and Control"},{"key":"20_CR13","unstructured":"T. Kaufman & S. Lovett (2008). Average case to worst case reduction for polynomials. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 166\u2013175."},{"key":"20_CR14","unstructured":"T. Kaufman & S. Lovett (2010). Weight distribution and list-decoding size of Reed\u2013Muller codes. In Proceedings of the 1st Symposium on Innovations in Computer Science (ICS)."},{"issue":"4","key":"20_CR15","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1137\/S0895480103434634","volume":"18","author":"P. Keevash","year":"2005","unstructured":"Keevash P., Sudakov B. (2005) Set systems with restricted cross-intersections and the minimum rank of inclusion matrices. SIAM Journal of Discrete Mathematics 18(4): 713\u2013727","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"20_CR16","unstructured":"J. MacWilliams & N.J. Sloane (1977). The Theory of Error Correcting Codes. North\u2013Holland."},{"issue":"22","key":"20_CR17","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan N., Wigderson A. (1994) Hardness vs. randomness. Journal of Computer and System Sciences 49(22): 149\u2013167","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"A. Razborov (1987). Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes 41(4), 333\u2013338. Translated from Matematicheskie Zametki 41(4), 598\u2013607.","DOI":"10.1007\/BF01137685"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"R. Smolensky (1987). Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In proceedings of the 19th Annual ACM Symposium on the Theory of Computation (STOC), 77\u201382.","DOI":"10.1145\/28395.28404"},{"issue":"1","key":"20_CR20","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1145\/1515698.1515709","volume":"40","author":"E. Viola","year":"2008","unstructured":"Viola E. (2008) Correlation bounds for polynomials over {0,1}. SIGACT News 40(1): 27\u201344","journal-title":"SIGACT News"},{"key":"20_CR21","unstructured":"E. Viola & A. Wigderson (2007). Norms, XOR lemmas, and lower bounds for GF(2) polynomials and multiparty protocols. In Proceedings of the 22nd IEEE Conference on Computational Complexity (CCC), 141\u2013154."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0020-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-011-0020-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0020-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T18:19:43Z","timestamp":1560449983000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-011-0020-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,8,4]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,3]]}},"alternative-id":["20"],"URL":"https:\/\/doi.org\/10.1007\/s00037-011-0020-6","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,8,4]]}}}