{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:03:56Z","timestamp":1725563036802},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642153686"},{"type":"electronic","value":"9783642153693"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15369-3_38","type":"book-chapter","created":{"date-parts":[[2010,8,27]],"date-time":"2010-08-27T04:01:36Z","timestamp":1282881696000},"page":"504-517","source":"Crossref","is-referenced-by-count":20,"title":["Improved Pseudorandom Generators for Depth 2 Circuits"],"prefix":"10.1007","author":[{"given":"Anindya","family":"De","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Omid","family":"Etesami","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca","family":"Trevisan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Madhur","family":"Tulsiani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"38_CR1","first-page":"199","volume":"5","author":"M. Ajtai","year":"1989","unstructured":"Ajtai, M., Wigderson, A.: Deterministic simulation of probabilistic constand-depth circuits. Advances in Computing Research - Randomness and Computation\u00a05, 199\u2013223 (1989); Preliminary version in Proc. of FOCS 1985","journal-title":"Advances in Computing Research - Randomness and Computation"},{"issue":"3","key":"38_CR2","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(3), 289\u2013304 (1992)","journal-title":"Random Structures and Algorithms"},{"issue":"3","key":"38_CR3","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0020-0190(03)00359-4","volume":"88","author":"N. Alon","year":"2003","unstructured":"Alon, N., Goldreich, O., Mansour, Y.: Almost k-wise independence versus k-wise independence. Information Processing Letters\u00a088(3), 107\u2013110 (2003)","journal-title":"Information Processing Letters"},{"key":"38_CR4","unstructured":"Bazzi, L.: Minimum Distance of Error Correcting Codes versus Encoding Complexity, Symmetry, and Pseudorandomness. PhD thesis, MIT (2003)"},{"key":"38_CR5","doi-asserted-by":"crossref","unstructured":"Bazzi, L.: Polylogarithmic independence can fool DNF formulas. In: Proceedings of the 48th IEEE Symposium on Foundations of Computer Science, pp. 63\u201373 (2007)","DOI":"10.1109\/FOCS.2007.28"},{"key":"38_CR6","doi-asserted-by":"crossref","unstructured":"Braverman, M.: Poly-logarithmic independence fools AC0 circuits. In: Proceedings of the 24th IEEE Conference on Computational Complexity, pp. 3\u20138 (2009)","DOI":"10.1109\/CCC.2009.35"},{"key":"38_CR7","doi-asserted-by":"crossref","unstructured":"Even, G., Goldreich, O., Luby, M., Nisan, N., Velickovic, B.: Approximations of general independent distributions. In: Proceedings of the 24th ACM Symposium on Theory of Computing, pp. 10\u201316 (1992)","DOI":"10.1145\/129712.129714"},{"key":"38_CR8","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Almost optimal lower bounds for small depth circuits. In: Proceedings of the 18th ACM Symposium on Theory of Computing, pp. 6\u201320 (1986)","DOI":"10.1145\/12130.12132"},{"key":"38_CR9","unstructured":"Klivans, A., Lee, H., Wan, A.: Mansour\u2019s conjecture is true for random DNF formulas. Technical Report TR10-023, Electronic Colloquium on Computational Complexity (2010)"},{"issue":"3","key":"38_CR10","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"N. Linial","year":"1993","unstructured":"Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, fourier transform and learnability. Journal of the ACM\u00a040(3), 607\u2013620 (1993)","journal-title":"Journal of the ACM"},{"issue":"4","key":"38_CR11","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02128670","volume":"10","author":"N. Linial","year":"1990","unstructured":"Linial, N., Nisan, N.: Approximate inclusion-exclusion. Combinatorica\u00a010(4), 349\u2013365 (1990)","journal-title":"Combinatorica"},{"issue":"4\/5","key":"38_CR12","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/BF01940873","volume":"16","author":"M. Luby","year":"1996","unstructured":"Luby, M., Velickovic, B.: On deterministic approximation of DNF. Algorithmica\u00a016(4\/5), 415\u2013433 (1996)","journal-title":"Algorithmica"},{"key":"38_CR13","doi-asserted-by":"crossref","unstructured":"Luby, M., Velickovic, B., Wigderson, A.: Deterministic approximate counting of depth-2 circuits. In: Proceedings of the 2nd ISTCS, pp. 18\u201324 (1993)","DOI":"10.1109\/ISTCS.1993.253488"},{"key":"38_CR14","unstructured":"Mak, L.: Parallelism always helps. Manuscript (1993)"},{"issue":"3","key":"38_CR15","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1006\/jcss.1995.1043","volume":"50","author":"Y. Mansour","year":"1995","unstructured":"Mansour, Y.: An o(n loglogn ) learning algorithm for DNF under the uniform distribution. Journal of Computer and System Sciences\u00a050(3), 543\u2013550 (1995)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"38_CR16","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. SIAM Journal on Computing\u00a022(4), 838\u2013856 (1993)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"38_CR17","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/BF01375474","volume":"12","author":"N. Nisan","year":"1991","unstructured":"Nisan, N.: Pseudorandom bits for constant depth circuits. Combinatorica\u00a012(4), 63\u201370 (1991)","journal-title":"Combinatorica"},{"key":"38_CR18","unstructured":"O\u2019Donnell, R.: Lecture notes for analysis of boolean functions (2007), http:\/\/www.cs.cmu.edu\/~odonnell\/boolean-analysis"},{"issue":"1","key":"38_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1490270.1490273","volume":"1","author":"A. Razborov","year":"2009","unstructured":"Razborov, A.: A Simple Proof of Bazzi\u2019s Theorem. ACM Trans. Comput. Theory\u00a01(1), 1\u20135 (2009)","journal-title":"ACM Trans. Comput. Theory"},{"issue":"1","key":"38_CR20","doi-asserted-by":"publisher","first-page":"137","DOI":"10.4086\/toc.2008.v004a007","volume":"4","author":"E. Viola","year":"2008","unstructured":"Viola, E., Wigderson, A.: Norms, XOR lemmas, and lower bounds for polynomials and protocols. Theory of Computing\u00a04(1), 137\u2013168 (2008)","journal-title":"Theory of Computing"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15369-3_38.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:05:29Z","timestamp":1606187129000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15369-3_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153686","9783642153693"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15369-3_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}