{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:31:24Z","timestamp":1725517884293},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540853626"},{"type":"electronic","value":"9783540853633"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85363-3_22","type":"book-chapter","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T15:29:28Z","timestamp":1219850968000},"page":"266-275","source":"Crossref","is-referenced-by-count":4,"title":["Small Sample Spaces Cannot Fool Low Degree Polynomials"],"prefix":"10.1007","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ido","family":"Ben-Eliezer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Krivelevich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"22_CR1","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0012-365X(03)00227-9","volume":"273","author":"N. Alon","year":"2003","unstructured":"Alon, N.: Problems and results in extremal combinatorics, I. Discrete Math.\u00a0273, 31\u201353 (2003)","journal-title":"Discrete Math."},{"doi-asserted-by":"crossref","unstructured":"Alon, N.: Perturbed identity matrices have high rank: proof and applications. Combinatorics, Probability and Computing (to appear)","key":"22_CR2","DOI":"10.1017\/S0963548307008917"},{"doi-asserted-by":"crossref","unstructured":"Alon, N., Andoni, A., Kaufman, T., Matulef, K., Rubinfeld, R., Xie, N.: Testing k-wise and almost k-wise independence. In: Proceedings of the 39th Annual ACM Symposium, STOC 2007, pp. 496\u2013505 (2007)","key":"22_CR3","DOI":"10.1145\/1250790.1250863"},{"key":"22_CR4","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"N. Alon","year":"1992","unstructured":"Alon, N., Goldreich, O., H\u00e5stad, J., Peralta, R.: Simple constructions of almost k-wise independent random variables. Random Structures and Algorithms\u00a03, 289\u2013304 (1992)","journal-title":"Random Structures and Algorithms"},{"key":"22_CR5","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1002\/rsa.3240050203","volume":"5","author":"N. Alon","year":"1994","unstructured":"Alon, N., Roichman, Y.: Random Cayley graphs and expanders. Random Structures and Algorithms\u00a05, 271\u2013284 (1994)","journal-title":"Random Structures and Algorithms"},{"key":"22_CR6","doi-asserted-by":"crossref","DOI":"10.1002\/0471722154","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2000","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method, 2nd edn. Wiley, New York (2000)","edition":"2"},{"doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Sudan, M., Vadhan, S., Wigderson, A.: Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. In: Proceedings of the 35th Annual ACM Symposium, STOC 2003, pp. 612\u2013621 (2003)","key":"22_CR7","DOI":"10.1145\/780542.780631"},{"doi-asserted-by":"crossref","unstructured":"Bogdanov, A.: Pseudorandom generators for low degree polynomials. In: Proceedings of the 37th Annual ACM Symposium, STOC 2005, pp. 21\u201330 (2005)","key":"22_CR8","DOI":"10.1145\/1060590.1060594"},{"unstructured":"Bogdanov, A., Dvir, Z., Verbin, E., Yehudayoff, A.: Pseudorandomness for width 2 branching programs (manuscript, 2008)","key":"22_CR9"},{"doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Viola, E.: Pseudorandom bits for polynomials. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), pp. 41\u201351 (2007)","key":"22_CR10","DOI":"10.1109\/FOCS.2007.42"},{"key":"22_CR11","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S0304-3975(99)00185-1","volume":"235","author":"B. Codenotti","year":"2000","unstructured":"Codenotti, B., Pudl\u00e1k, P., Resta, G.: Some structural properties of low-rank matrices related to computational complexity. Theoret. Comput. Sci.\u00a0235, 89\u2013107 (2000)","journal-title":"Theoret. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Dvir, Z., Shpilka, A.: Noisy interpolating sets for low degree polynomials. In: Proceedings of the 23th IEEE Conference on Computational Complexity (CCC), pp. 140\u2013148 (2008)","key":"22_CR12","DOI":"10.1109\/CCC.2008.14"},{"doi-asserted-by":"crossref","unstructured":"Lovett, S.: Unconditional pseudorandom generators for low degree polynomials. In: Proceedings of the 40th Annual ACM Symposium, STOC 2008, pp. 557\u2013562 (2008)","key":"22_CR13","DOI":"10.1145\/1374376.1374455"},{"doi-asserted-by":"crossref","unstructured":"Lovett, S., Meshulam, R., Samorodnitsky, A.: Inverse conjecture for the Gowers norm is false. In: Proceedings of the 40th Annual ACM Symposium, STOC 2008, pp. 547\u2013556 (2008)","key":"22_CR14","DOI":"10.1145\/1374376.1374454"},{"doi-asserted-by":"crossref","unstructured":"Luby, M., Velickovic, B., Wigderson, A.: Deterministic approximate counting of depth-2 circuits. In: Proceedings of the 2nd ISTCS (Israeli Symposium on Theoretical Computer Science), pp. 18\u201324 (1993)","key":"22_CR15","DOI":"10.1109\/ISTCS.1993.253488"},{"issue":"3","key":"22_CR16","first-page":"478","volume":"49","author":"R. Motwani","year":"1994","unstructured":"Motwani, R., Naor, J., Naor, M.: The probabilistic method yields deterministic parallel algorithms. JCSS\u00a049(3), 478\u2013516 (1994)","journal-title":"JCSS"},{"doi-asserted-by":"crossref","unstructured":"Naor, J., Naor, M.: Small bias probability spaces: efficient constructions and applications. In: Proceedings of the 22th Annual ACM Symposium, STOC 1990, pp. 213\u2013223 (1990)","key":"22_CR17","DOI":"10.1145\/100216.100244"},{"doi-asserted-by":"crossref","unstructured":"Schechtman, G., Shraibman, A.: Lower bounds for local versions of dimension reductions (manuscript, 2007)","key":"22_CR18","DOI":"10.1007\/s00454-008-9068-8"},{"doi-asserted-by":"crossref","unstructured":"Shpilka, A.: Constructions of low-degree and error-correcting \u03b5-biased generators. In: Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC), Prague, Czech Republic, pp. 33\u201345 (2006)","key":"22_CR19","DOI":"10.1109\/CCC.2006.15"},{"doi-asserted-by":"crossref","unstructured":"Viola, E.: The sum of d small-bias generators fools polynomials of degree d. In: Proceedings of the 23th IEEE Conference on Computational Complexity (CCC), pp. 124\u2013127 (2008)","key":"22_CR20","DOI":"10.1109\/CCC.2008.16"}],"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-540-85363-3_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T21:24:17Z","timestamp":1606166657000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85363-3_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540853626","9783540853633"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85363-3_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}