{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T20:59:55Z","timestamp":1766350795065},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424703"},{"type":"electronic","value":"9783540446668"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44666-4_28","type":"book-chapter","created":{"date-parts":[[2007,5,3]],"date-time":"2007-05-03T12:58:07Z","timestamp":1178197087000},"page":"249-260","source":"Crossref","is-referenced-by-count":7,"title":["On the Derandomization of Constant Depth Circuits"],"prefix":"10.1007","author":[{"given":"Adam R.","family":"Klivans","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,17]]},"reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai. \u22111 1-Formulae on Finite Structures. Annals of Pure and Applied Logic, Vol. 24, 1983.","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"28_CR2","doi-asserted-by":"crossref","unstructured":"M. Ajtai. Approximate Counting with Uniform Constant-Depth Circuits. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 13, 1993.","DOI":"10.1090\/dimacs\/013\/01"},{"key":"28_CR3","doi-asserted-by":"crossref","unstructured":"M. Ajtai and M. Ben-Or. A Theorem on Probabilistic Constant Depth Computations. In ACM Symposium on Theory of Computing (STOC), 1984.","DOI":"10.1145\/800057.808715"},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"J. Aspnes, R. Beigel, M. Furst, and S. Rudich. The Expressive Power of Voting Polynomials. Combinatorica, 14(2), 1994.","DOI":"10.1007\/BF01215346"},{"key":"28_CR5","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"L. Babai","year":"1993","unstructured":"L. Babai, L. Fortnow, N. Nisan, and A. Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity, 3:307\u2013318, 1993.","journal-title":"Computational Complexity"},{"key":"28_CR6","unstructured":"P. Beame. A Switching Lemma Primer. Technical Report UW-CSE-95-07-01, Department of Computer Science and Engineering, University of Washington, November 1994."},{"key":"28_CR7","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1007\/BF01263420","volume":"4","author":"R. Beigel","year":"1994","unstructured":"R. Beigel When do Extra Majority Gates Help? Polylog(n) Majority Gates are Equivalent to One. Computational Complexity, 4, 314\u2013324, 1994.","journal-title":"Computational Complexity"},{"key":"28_CR8","doi-asserted-by":"crossref","unstructured":"R. Beigel, N. Reingold, and D. Spielman. The Perceptron Strikes Back. In Proceedings of the 6th Annual Conference on Structure in Complexity Theory (SCTC\u2019 91), June 1991.","DOI":"10.1109\/SCT.1991.160270"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"M. Furst, J. Saxe, and M. Sipser. Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory, 17(1), 1984.","DOI":"10.1007\/BF01744431"},{"key":"28_CR10","unstructured":"J. H\u00e5stad. Computational Limitations of Small Depth Circuits. MIT-PRESS, 1986."},{"key":"28_CR11","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo. Hard-core distributions for somewhat hard problems. In Proceedings of the 36th IEEE Symposium on Foundations of Computer Science, pages 538\u2013545. IEEE, 1995.","DOI":"10.1109\/SFCS.1995.492584"},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, R. Shaltiel, and A. Wigderson. Near Optimal Conversion of Hardness into Pseudorandomness. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science, pages 538\u2013545. IEEE, 1999.","DOI":"10.1109\/SFFCS.1999.814590"},{"key":"28_CR13","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and A. Wigderson. P=BPP unless E has sub-exponential circuits: Derandomizing the XOR lemma. In Proceedings of the 29th ACM Symposium on the Theory of Computing, pages 220\u2013229. ACM, 1997.","DOI":"10.1145\/258533.258590"},{"key":"28_CR14","doi-asserted-by":"crossref","unstructured":"A. Klivans and D. van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial hierarchy collapses. In Proceedings of the 31st ACM Symposium on the Theory of Computing, pages 659\u2013667. ACM, 1999.","DOI":"10.1145\/301250.301428"},{"key":"28_CR15","doi-asserted-by":"crossref","unstructured":"A. Klivans and R. Servedio. Boosting and Hard-Core Sets. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS), 1999.","DOI":"10.1109\/SFFCS.1999.814638"},{"key":"28_CR16","doi-asserted-by":"crossref","unstructured":"N. Linial, Y. Mansour, and N. Nisan. Constant Depth Circuits, Fourier Transforms, and Learnability. Journal of the ACM, 40(3), July 1993.","DOI":"10.1145\/174130.174138"},{"key":"28_CR17","doi-asserted-by":"crossref","unstructured":"M. Luby, B. Velickovic, and A. Wigderson. Deterministic Approximate Counting of Depth-2 Circuits. In Proceedings of the Second Israeli Symposium on Theory of Computing and Systems, 1993.","DOI":"10.1109\/ISTCS.1993.253488"},{"key":"28_CR18","doi-asserted-by":"crossref","unstructured":"N. Nisan. Pseudorandom Bits for Constant Depth Circuits. Combinatorica, 11, 1991.","DOI":"10.1007\/BF01375474"},{"key":"28_CR19","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"N. Nisan and A. Wigderson. Hardness vs. Randomness. Journal of Computer and System Sciences, 49:149\u2013167, 1994.","journal-title":"Journal of Computer and System Sciences"},{"key":"28_CR20","unstructured":"C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994."},{"key":"28_CR21","doi-asserted-by":"crossref","unstructured":"A. Razborov. Lower Bounds on the Size of Bounded Depth Circuits over a Complete Basis with Logical Addition. MATHNAUSSR: Mathematical Notes of the Academ of Sciences of the USSR, 41, 1987.","DOI":"10.1007\/BF01137685"},{"key":"28_CR22","doi-asserted-by":"crossref","unstructured":"R. Servedio. Smooth Boosting and Learning with Malicious Noise. To Appear, 2001.","DOI":"10.1007\/3-540-44581-1_31"},{"key":"28_CR23","doi-asserted-by":"crossref","unstructured":"R. Smolensky. Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, May 1987.","DOI":"10.1145\/28395.28404"},{"key":"28_CR24","doi-asserted-by":"crossref","unstructured":"L. Stockmeyer. The Complexity of Approximate Counting. In ACM Symposium on Theory of Computing (STOC), 1983.","DOI":"10.1145\/800061.808740"},{"key":"28_CR25","doi-asserted-by":"crossref","unstructured":"M. Sudan, L. Trevisan, and S. Vadhan. Pseudorandom generators without the XOR lemma. Technical Report TR-98-074, Electronic Colloquium on Computational Complexity, 2000. Revision 2.","DOI":"10.1145\/301250.301397"},{"key":"28_CR26","doi-asserted-by":"crossref","unstructured":"L. Trevisan. Construction of extractors using pseudo-random generators. In Proceedings of the 31st ACM Symposium on the Theory of Computing, pages 141\u2013148. ACM, 1999.","DOI":"10.1145\/301250.301289"},{"key":"28_CR27","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L. Valiant","year":"1986","unstructured":"L. Valiant and V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science, 47:85\u201393, 1986.","journal-title":"Theoretical Computer Science"}],"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\/3-540-44666-4_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T13:54:25Z","timestamp":1683813265000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44666-4_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424703","9783540446668"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-44666-4_28","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}