{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:14:12Z","timestamp":1763468052936},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,3,30]],"date-time":"2012-03-30T00:00:00Z","timestamp":1333065600000},"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,6]]},"DOI":"10.1007\/s00037-012-0039-3","type":"journal-article","created":{"date-parts":[[2012,3,29]],"date-time":"2012-03-29T08:35:53Z","timestamp":1333010153000},"page":"245-266","source":"Crossref","is-referenced-by-count":13,"title":["Bounded-Depth Circuits Cannot Sample Good Codes"],"prefix":"10.1007","volume":"21","author":[{"given":"Shachar","family":"Lovett","sequence":"first","affiliation":[]},{"given":"Emanuele","family":"Viola","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,3,30]]},"reference":[{"issue":"6","key":"39_CR1","doi-asserted-by":"crossref","first-page":"1570","DOI":"10.1137\/S009753979935476","volume":"32","author":"Ambainis Andris","year":"2003","unstructured":"Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson (2003) The Quantum Communication Complexity of Sampling. SIAM J. Comput. 32(6): 1570\u20131585","journal-title":"SIAM J. Comput."},{"issue":"6","key":"39_CR2","doi-asserted-by":"crossref","first-page":"2220","DOI":"10.1137\/070691954","volume":"38","author":"Bazzi Louay M. J.","year":"2009","unstructured":"Louay M. J. Bazzi (2009) Polylogarithmic Independence Can Fool DNF Formulas. SIAM J. Comput. 38(6): 2220\u20132272","journal-title":"SIAM J. Comput."},{"issue":"5","key":"39_CR3","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/S0020-0190(97)00131-2","volume":"63","author":"Boppana Ravi","year":"1997","unstructured":"Ravi Boppana (1997) The average sensitivity of bounded-depth circuits. Information Processing Letters 63(5): 257\u2013261 ISSN 00200190","journal-title":"Information Processing Letters"},{"key":"39_CR4","doi-asserted-by":"crossref","unstructured":"Mark Braverman (2010). Polylogarithmic independence fools AC0 circuits. J. of the ACM 57(5).","DOI":"10.1145\/1754399.1754401"},{"key":"39_CR5","doi-asserted-by":"crossref","unstructured":"Anna G\u00e1l & Peter Bro Miltersen (2007). The cell probe complexity of succinct data structures. Theoret. Comput. Sci.379(3), 405\u2013417. ISSN 0304-3975.","DOI":"10.1016\/j.tcs.2007.02.047"},{"issue":"7","key":"39_CR6","doi-asserted-by":"crossref","first-page":"2761","DOI":"10.1137\/080722771","volume":"39","author":"Goldreich Oded","year":"2010","unstructured":"Oded Goldreich, Shafi Goldwasser, Asaf Nussboim (2010) On the Implementation of Huge Random Objects. SIAM J. Comput. 39(7): 2761\u20132822","journal-title":"SIAM J. Comput."},{"key":"39_CR7","doi-asserted-by":"crossref","unstructured":"Venkatesan Guruswami, Christopher Umans & Salil P. Vadhan (2009). Unbalanced expanders and randomness extractors from Parvaresh\u2013Vardy codes. J. of the ACM 56(4).","DOI":"10.1145\/1538902.1538904"},{"issue":"1","key":"39_CR8","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1137\/0112012","volume":"12","author":"L.H. Harper","year":"1964","unstructured":"Harper L.H. (1964) Optimal Assignments of Numbers to Vertices. SIAM Journal on Applied Mathematics 12(1): 131\u2013135","journal-title":"SIAM Journal on Applied Mathematics"},{"issue":"2","key":"39_CR9","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0012-365X(76)90058-3","volume":"14","author":"Hart Sergiu","year":"1976","unstructured":"Sergiu Hart (1976) A note on the edges of the n-cube. Discrete Mathematics 14(2): 157\u2013163","journal-title":"Discrete Mathematics"},{"key":"39_CR10","unstructured":"Johan H\u00e5stad (1987). Computational limitations of small-depth circuits. MIT Press. ISBN 0262081679."},{"issue":"2\u20133","key":"39_CR11","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"Jerrum Marc R.","year":"1986","unstructured":"Marc R. Jerrum, Leslie G. Valiant, Vijay V. Vazirani (1986) Random Generation of Combinatorial Structures from a Uniform Distribution. Theoretical Computer Science 43(2\u20133): 169\u2013188","journal-title":"Theoretical Computer Science"},{"key":"39_CR12","doi-asserted-by":"crossref","unstructured":"Nathan Linial, Yishay Mansour & Noam Nisan (1993). Constant depth circuits, Fourier transform, and learnability. J. of the ACM 40(3), 607\u2013620. ISSN 0004-5411.","DOI":"10.1145\/174130.174138"},{"key":"39_CR13","doi-asserted-by":"crossref","unstructured":"Shachar Lovett & Emanuele Viola (2011). Bounded-depth circuits cannot sample good codes. In IEEE Conf. on Computational Complexity (CCC).","DOI":"10.1109\/CCC.2011.11"},{"key":"39_CR14","unstructured":"Peter Bro Miltersen (1999). Cell probe complexity - a survey. Invited talk\/paper at Advances in Data Structures (Pre-conference workshop of FSTTCS\u201999)."},{"key":"39_CR15","doi-asserted-by":"crossref","unstructured":"Noam Nisan (1991). Pseudorandom bits for constant depth circuits. Combinatorica 11(1), 63\u201370. ISSN 0209-9683.","DOI":"10.1007\/BF01375474"},{"key":"39_CR16","unstructured":"Ryan O\u2019Donnell (2007). Analysis of Boolean Functions. Lecture notes. Available at http:\/\/www.cs.cmu.edu\/~odonnell\/boolean-analysis ."},{"key":"39_CR17","doi-asserted-by":"crossref","unstructured":"Alexander A. Razborov (2009). A Simple Proof of Bazzi\u2019s Theorem. ACM Transactions on Computation Theory (TOCT) 1(1).","DOI":"10.1145\/1490270.1490273"},{"issue":"3-4","key":"39_CR18","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/s00037-004-0187-1","volume":"13","author":"Viola Emanuele","year":"2004","unstructured":"Emanuele Viola (2004) The Complexity of Constructing Pseudorandom Generators from Hard Functions. Computational Complexity 13(3-4): 147\u2013188","journal-title":"Computational Complexity"},{"key":"39_CR19","doi-asserted-by":"crossref","unstructured":"Emanuele Viola (2010). The complexity of distributions. SIAM J. on Computing To appear.","DOI":"10.1109\/FOCS.2010.27"},{"key":"39_CR20","doi-asserted-by":"crossref","unstructured":"Emanuele Viola (2011). Extractors for circuit sources. In IEEE Symp. on Foundations of Computer Science (FOCS).","DOI":"10.1109\/FOCS.2011.20"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0039-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-012-0039-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0039-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,26]],"date-time":"2019-06-26T06:34:20Z","timestamp":1561530860000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-012-0039-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3,30]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["39"],"URL":"https:\/\/doi.org\/10.1007\/s00037-012-0039-3","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3,30]]}}}