{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:59:24Z","timestamp":1775282364674,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,1,8]],"date-time":"2014-01-08T00:00:00Z","timestamp":1389139200000},"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":[[2014,9]]},"DOI":"10.1007\/s00037-013-0076-6","type":"journal-article","created":{"date-parts":[[2014,1,7]],"date-time":"2014-01-07T03:33:45Z","timestamp":1389065625000},"page":"479-508","source":"Crossref","is-referenced-by-count":7,"title":["Randomness Buys Depth for Approximate Counting"],"prefix":"10.1007","volume":"23","author":[{"given":"Emanuele","family":"Viola","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,1,8]]},"reference":[{"key":"76_CR1","doi-asserted-by":"crossref","unstructured":"Scott Aaronson (2010). BQP and the polynomial hierarchy. In 42nd ACM Symp. on the Theory of Computing (STOC), 141\u2013150. ACM.","DOI":"10.1145\/1806689.1806711"},{"key":"76_CR2","doi-asserted-by":"crossref","unstructured":"Leonard Adleman (1978). Two theorems on random polynomial time. In 19th IEEE Symp. on Foundations of Computer Science (FOCS), 75\u201383.","DOI":"10.1109\/SFCS.1978.37"},{"key":"76_CR3","doi-asserted-by":"crossref","unstructured":"Manindra Agrawal (2001). Hard Sets and Pseudo-random Generators for Constant Depth Circuits. In 21st Foundations of Software Technology and Theoretical Computer Science, 58\u201369. Springer-Verlag.","DOI":"10.1007\/3-540-45294-X_6"},{"key":"76_CR4","unstructured":"Mikl\u00f3s Ajtai (1983). $${\\Sigma^{1}{[1]}}$$ \u03a3 1 [ 1 ] -formulae on finite structures. Ann. Pure Appl. Logic 24(1), 1\u201348."},{"key":"76_CR5","unstructured":"Mikl\u00f3s Ajtai (1993). Approximate counting with uniform constant-depth circuits. In Advances in computational complexity theory, 1\u201320. Amer. Math. Soc., Providence, RI."},{"key":"76_CR6","unstructured":"Mikl\u00f3s Ajtai & Michael Ben-Or (1984). A Theorem on Probabilistic Constant Depth Computation. In 16th ACM Symp. on the Theory of Computing (STOC), 471\u2013474."},{"key":"76_CR7","unstructured":"Mikl\u00f3s Ajtai, J\u00e1nos Koml\u00f3s & Endre Szemer\u00e9di (1987). Deterministic simulation in LOGSPACE. In 19th ACM Symp. on the Theory of Computing (STOC), 132\u2013140."},{"key":"76_CR8","doi-asserted-by":"crossref","unstructured":"Noga Alon, Uriel Feige, Avi Wigderson & David Zuckerman (1995). Derandomized Graph Products. Computational Complexity 5(1), 60\u201375.","DOI":"10.1007\/BF01277956"},{"key":"76_CR9","doi-asserted-by":"crossref","unstructured":"Kazuyuki Amano (2009). Bounds on the Size of Small Depth Circuits for Approximating Majority. In 36th Coll. on Automata, Languages and Programming (ICALP), 59\u201370. Springer.","DOI":"10.1007\/978-3-642-02927-1_7"},{"key":"76_CR10","doi-asserted-by":"crossref","unstructured":"Roy Armoni, Michael E. Saks, Avi Wigderson & Shiyu Zhou (1996). Discrepancy Sets and Pseudorandom Generators for Combinatorial Rectangles. In 37th IEEE Symp. on Foundations of Computer Science (FOCS), 412\u2013421.","DOI":"10.1109\/SFCS.1996.548500"},{"key":"76_CR11","unstructured":"Paul Beame (1994). A switching lemma primer. Technical Report UW-CSE-95-07-01, Department of Computer Science and Engineering, University of Washington. Available from http:\/\/www.cs.washington.edu\/homes\/beame\/ ."},{"key":"76_CR12","unstructured":"Joshua Brody & Elad Verbin (2010). The Coin Problem, and Pseudorandomness for Branching Programs. In 51th IEEE Symp. on Foundations of Computer Science (FOCS)."},{"key":"76_CR13","unstructured":"Shiva Chaudhuri & Jaikumar Radhakrishnan (1996). Deterministic Restrictions in Circuit Complexity. In 28th ACM Symp. on the Theory of Computing (STOC), 30\u201336."},{"key":"76_CR14","doi-asserted-by":"crossref","unstructured":"Guy Even, Oded Goldreich, Michael Luby, Noam Nisan & Boban Velickovic (1998). Efficient approximation of product distributions. Random Struct. Algorithms 13(1), 1\u201316.","DOI":"10.1002\/(SICI)1098-2418(199808)13:1<1::AID-RSA1>3.0.CO;2-W"},{"key":"76_CR15","doi-asserted-by":"crossref","unstructured":"Shimon Even, Alan L. Selman & Yacov Yacobi (1984). The complexity of promise problems with applications to public-key cryptography. Inform. and Control 61(2), 159\u2013173.","DOI":"10.1016\/S0019-9958(84)80056-X"},{"key":"76_CR16","unstructured":"Oded Goldreich (2010). Pseudorandom Generators: A Primer, volume 55 of University Lecture Series. AMS."},{"key":"76_CR17","unstructured":"Shafi Goldwasser & Michael Sipser (1986). Private Coins versus Public Coins in Interactive Proof Systems. In 18th ACM Symposium on Theory of Computing (STOC), 59\u201368."},{"key":"76_CR18","unstructured":"Johan H\u00c5stad (1987). Computational limitations of small-depth circuits. MIT Press."},{"key":"76_CR19","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo, Noam Nisan & Avi Wigderson (1994). Pseudorandomness for Network Algorithms. In 26th ACM Symp. on the Theory of Computing (STOC), 356\u2013364.","DOI":"10.1145\/195058.195190"},{"key":"76_CR20","unstructured":"Russell Impagliazzo & Avi Wigderson (1997). P =\u00a0 BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. In 29th ACM Symp. on the Theory of Computing (STOC), 220\u2013229. ACM."},{"key":"76_CR21","doi-asserted-by":"crossref","unstructured":"Nabil Kahale (1995). Eigenvalues and expansion of regular graphs. J. of the ACM 42(5), 1091\u20131106.","DOI":"10.1145\/210118.210136"},{"key":"76_CR22","doi-asserted-by":"crossref","unstructured":"Clemens Lautemann (1983). BPP and the polynomial hierarchy. Information Processing Letters 17(4), 215\u2013217.","DOI":"10.1016\/0020-0190(83)90044-3"},{"key":"76_CR23","doi-asserted-by":"crossref","unstructured":"Chi-Jen Lu (2002). Improved pseudorandom generators for combinatorial rectangles. Combinatorica 22(3), 417\u2013433.","DOI":"10.1007\/s004930200021"},{"key":"76_CR24","doi-asserted-by":"crossref","unstructured":"Noam Nisan (1992). Pseudorandom Generators for Space-bounded Computation. Combinatorica 12(4), 449\u2013461.","DOI":"10.1007\/BF01305237"},{"key":"76_CR25","doi-asserted-by":"crossref","unstructured":"Noam Nisan & David Zuckerman (1996). Randomness is Linear in Space. J. of Computer and System Sciences 52(1), 43\u201352.","DOI":"10.1006\/jcss.1996.0004"},{"key":"76_CR26","doi-asserted-by":"crossref","unstructured":"Prabhakar Ragde & Avi Wigderson (1991). Linear-Size Constant-Depth Polylog-Treshold Circuits. Inf. Process. Lett. 39(3), 143\u2013146.","DOI":"10.1016\/0020-0190(91)90110-4"},{"key":"76_CR27","unstructured":"Alexander Razborov (2002-2003). Pseudorandom Generators Hard for k-DNF Resolution and Polynomial Calculus Resolution. Manuscript. Available from http:\/\/www.mi.ras.ru\/~razborov\/ ."},{"issue":"7","key":"76_CR28","doi-asserted-by":"crossref","first-page":"3122","DOI":"10.1137\/080735096","volume":"39","author":"Ronen. Shaltiel","year":"2010","unstructured":"Shaltiel Ronen., Viola Emanuele (2010) Hardness amplification proofs require majority. SIAM J. on Computing 39(7): 3122\u20133154","journal-title":"SIAM J. on Computing"},{"key":"76_CR29","doi-asserted-by":"crossref","unstructured":"Michael Sipser (1983). A Complexity Theoretic Approach to Randomness. In 15th ACM Symposium on Theory of Computing, 330\u2013335. Boston, Massachusetts.","DOI":"10.1145\/800061.808762"},{"key":"76_CR30","doi-asserted-by":"crossref","unstructured":"Larry Stockmeyer (1983). The Complexity of Approximate Counting. In 15th Symposium on Theory of Computing (STOC), 118\u2013126. ACM.","DOI":"10.1145\/800061.808740"},{"key":"76_CR31","doi-asserted-by":"crossref","unstructured":"Larry Stockmeyer (1985). On Approximation Algorithms for #P. SIAM J. on Computing 14(4), 849\u2013861.","DOI":"10.1137\/0214060"},{"issue":"3-4","key":"76_CR32","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/s00037-004-0187-1","volume":"13","author":"Emanuele Viola","year":"2004","unstructured":"Viola Emanuele (2004) The Complexity of Constructing Pseudorandom Generators from Hard Functions. Computational Complexity 13(3-4): 147\u2013188","journal-title":"Computational Complexity"},{"issue":"3","key":"76_CR33","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/s00037-009-0267-3","volume":"18","author":"Emanuele Viola","year":"2009","unstructured":"Viola Emanuele (2009) On approximate majority and probabilistic time. Computational Complexity 18(3): 337\u2013375","journal-title":"Computational Complexity"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-013-0076-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-013-0076-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-013-0076-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,5]],"date-time":"2019-08-05T18:53:50Z","timestamp":1565031230000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-013-0076-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1,8]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,9]]}},"alternative-id":["76"],"URL":"https:\/\/doi.org\/10.1007\/s00037-013-0076-6","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1,8]]}}}