{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:12:40Z","timestamp":1763467960601},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642036842"},{"type":"electronic","value":"9783642036859"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03685-9_28","type":"book-chapter","created":{"date-parts":[[2009,8,21]],"date-time":"2009-08-21T02:39:51Z","timestamp":1250822391000},"page":"366-377","source":"Crossref","is-referenced-by-count":2,"title":["Random Low Degree Polynomials are Hard to Approximate"],"prefix":"10.1007","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","reference":[{"key":"28_CR1","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0012-365X(83)90253-4","volume":"46","author":"N. Alon","year":"1983","unstructured":"Alon, N.: On the density of sets of vectors. Discrete Math.\u00a046, 199\u2013202 (1983)","journal-title":"Discrete Math."},{"key":"28_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/978-3-540-85363-3_22","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"N. Alon","year":"2008","unstructured":"Alon, N., Ben-Eliezer, I., Krivelevich, M.: Small sample spaces cannot fool low degree polynomials. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 266\u2013275. Springer, Heidelberg (2008)"},{"key":"28_CR3","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Kopparty, S.: Affine dispersers from subspace polynomials. In: proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 65\u201374 (2009)","DOI":"10.1145\/1536414.1536426"},{"issue":"2","key":"28_CR4","doi-asserted-by":"publisher","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.: Multiparty protocols, pseudorandom generators for logspace and time-space trade-offs. J. of Computer and System Sciences\u00a045(2), 204\u2013232 (1992)","journal-title":"J. of Computer and System Sciences"},{"key":"28_CR5","volume-title":"Covering Codes","author":"G. Cohen","year":"1997","unstructured":"Cohen, G., Honkala, I., Litsyn, S., Lobstein, A.: Covering Codes. North Holland, Amsterdam (1997)"},{"issue":"1","key":"28_CR6","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0097-3165(83)90038-9","volume":"34","author":"P. Frankl","year":"1983","unstructured":"Frankl, P.: On the trace of finite sets. J. of Combinatorial Theory, Series\u00a0A\u00a034(1), 41\u201345 (1983)","journal-title":"J. of Combinatorial Theory, Series\u00a0A"},{"issue":"3","key":"28_CR7","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/s00039-001-0332-9","volume":"11","author":"W.T. Gowers","year":"2001","unstructured":"Gowers, W.T.: A new proof of Szemer\u00e9di\u2019s theorem. Geometric and Functional Analysis\u00a011(3), 465\u2013588 (2001)","journal-title":"Geometric and Functional Analysis"},{"key":"28_CR8","unstructured":"Green, B., Tao, T.: The distribution of polynomials over finite fields, with applications to the Gowers Norm (submitted) (2007)"},{"key":"28_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04650-0","volume-title":"Extremal Combinatorics with Applications in Computer Science","author":"S. Jukna","year":"2001","unstructured":"Jukna, S.: Extremal Combinatorics with Applications in Computer Science. Springer, Heidelberg (2001)"},{"key":"28_CR10","doi-asserted-by":"crossref","unstructured":"Gopalan, P., Klivans, A., Zuckerman, D.: List-decoding Reed\u2013Muller codes over small fields. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 265\u2013274 (2008)","DOI":"10.1145\/1374376.1374417"},{"key":"28_CR11","doi-asserted-by":"crossref","unstructured":"Kaufman, T., Lovett, S.: Average case to worst case reduction for polynomials. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 166\u2013175 (2008)","DOI":"10.1109\/FOCS.2008.17"},{"key":"28_CR12","unstructured":"Kaufman, T., Lovett, S.: List size vs.\u00a0decoding radius for Reed\u2013Muller codes (submitted)"},{"issue":"6","key":"28_CR13","doi-asserted-by":"publisher","first-page":"752","DOI":"10.1109\/TIT.1970.1054545","volume":"16","author":"T. Kasami","year":"1970","unstructured":"Kasami, T., Tokura, N.: On the weight structure of Reed\u2013Muller codes. IEEE Transactions on Information Theory\u00a016(6), 752\u2013759 (1970)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"4","key":"28_CR14","first-page":"380","volume":"30","author":"T. Kasami","year":"1976","unstructured":"Kasami, T., Tokura, N., Azumi, S.: On the weight enumeration of weights less than 2. 5d of Reed\u2013Muller codes\u00a030(4), 380\u2013395 (1976)","journal-title":"5d of Reed\u2013Muller codes"},{"issue":"4","key":"28_CR15","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1137\/S0895480103434634","volume":"18","author":"P. Keevash","year":"2005","unstructured":"Keevash, P., Sudakov, B.: Set systems with restricted cross-intersections and the minimum rank of inclusion matrices. SIAM J.\u00a0of Discrete Mathematics\u00a018(4), 713\u2013727 (2005)","journal-title":"SIAM J.\u00a0of Discrete Mathematics"},{"key":"28_CR16","volume-title":"The Theory of Error Correcting Codes","author":"J. MacWilliams","year":"1977","unstructured":"MacWilliams, J., Sloane, N.: The Theory of Error Correcting Codes. North Holland, Amsterdam (1977)"},{"issue":"22","key":"28_CR17","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Wigderson, A.: Hardness vs. randomness. J. of Computer and System Sciences\u00a049(22), 149\u2013167 (1994)","journal-title":"J. of Computer and System Sciences"},{"issue":"4","key":"28_CR18","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/BF01137685","volume":"41","author":"A. Razborov","year":"1987","unstructured":"Razborov, A.: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Math.\u00a0Notes\u00a041(4), 333\u2013338 (1987); Translated from Matematicheskie Zametki\u00a041(4), 598\u2013607 (1987)","journal-title":"Math.\u00a0Notes"},{"key":"28_CR19","doi-asserted-by":"crossref","unstructured":"Smolensky, R.: 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), pp. 77\u201382 (1987)","DOI":"10.1145\/28395.28404"},{"issue":"1","key":"28_CR20","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1145\/1515698.1515709","volume":"40","author":"E. Viola","year":"2009","unstructured":"Viola, E.: Correlation bounds for polynomials over {0,1}. SIGACT News\u00a040(1), 27\u201344 (2009)","journal-title":"SIGACT News"},{"key":"28_CR21","doi-asserted-by":"crossref","unstructured":"Viola, E., Wigderson, A.: Norms, XOR lemmas, and lower bounds for GF(2) polynomials and multiparty protocols. In: Proceedings of the 22nd IEEE Conference on Computational Complexity (CCC), pp. 141\u2013154 (2007)","DOI":"10.1109\/CCC.2007.15"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03685-9_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T16:15:37Z","timestamp":1558282537000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03685-9_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642036842","9783642036859"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03685-9_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}