{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:58:14Z","timestamp":1775282294632,"version":"3.50.1"},"reference-count":59,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,5,12]],"date-time":"2016-05-12T00:00:00Z","timestamp":1463011200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2017,3]]},"DOI":"10.1007\/s00037-016-0134-y","type":"journal-article","created":{"date-parts":[[2016,5,12]],"date-time":"2016-05-12T03:00:20Z","timestamp":1463022020000},"page":"275-321","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Fourier Concentration from Shrinkage"],"prefix":"10.1007","volume":"26","author":[{"given":"Russell","family":"Impagliazzo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valentine","family":"Kabanets","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,5,12]]},"reference":[{"key":"134_CR1","doi-asserted-by":"crossref","unstructured":"A. Ambainis, A.M. Childs, B. Reichardt, R. \u0160palek & S. Zhang (2007). Any And-Or formula of size $${n}$$ n can be evaluated in time $${n^{1\/2+o(1)}}$$ n 1 \/ 2 + o ( 1 ) on a quantum computer. In Proceedings of the Forty-Eighth Annual IEEE Symposium on Foundations of Computer Science, 363\u2013372.","DOI":"10.1109\/FOCS.2007.57"},{"key":"134_CR2","unstructured":"A.E. Andreev (1987). On a method of obtaining more than quadratic effective lower bounds for the complexity of $${\\pi}$$ \u03c0 -schemes. Vestnik Moskovskogo Universiteta. Matematika 42(1), 70\u201373. English translation in Moscow University Mathematics Bulletin."},{"key":"134_CR3","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"L. Babai","year":"1993","unstructured":"Babai L., Fortnow L., Nisan N., Wigderson A. (1993) BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity 3: 307\u2013318","journal-title":"Computational Complexity"},{"issue":"4","key":"134_CR4","doi-asserted-by":"crossref","first-page":"778","DOI":"10.1145\/502090.502097","volume":"48","author":"R. Beals","year":"2001","unstructured":"Beals R., Buhrman H., Cleve R., Mosca M., de Wolf R. (2001) Quantum lower bounds by polynomials. Journal of the Association for Computing Machinery 48(4): 778\u2013797","journal-title":"Journal of the Association for Computing Machinery"},{"key":"134_CR5","doi-asserted-by":"crossref","unstructured":"P. Beame, R. Impagliazzo & S. Srinivasan (2012). Approximating AC 0 by Small Height Decision Trees and a Deterministic Algorithm for #AC 0SAT. In Proceedings of the Twenty-Seventh Annual IEEE Conference on Computational Complexity, 117\u2013125.","DOI":"10.1109\/CCC.2012.40"},{"key":"134_CR6","doi-asserted-by":"crossref","unstructured":"A. Bernasconi, C. Damm & I. Shparlinski (2000). The average sensitivity of square-freeness. Computational Complexity 9(1), 39\u201351. ISSN 1016-3328. URL http:\/\/dx.doi.org\/10.1007\/PL00001600 .","DOI":"10.1007\/PL00001600"},{"key":"134_CR7","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"Blum M., Micali S. (1984) How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal on Computing 13: 850\u2013864","journal-title":"SIAM Journal on Computing"},{"key":"134_CR8","unstructured":"R. Boppana (1989). Amplification of probabilistic Boolean formulas. In Randomness and Computation, S. Micali, editor, volume 5 of Advances in Computer Research, 27\u201345. JAI Press, Greenwich, CT. (preliminary version in FOCS\u201985)."},{"issue":"5","key":"134_CR9","doi-asserted-by":"crossref","first-page":"28:1","DOI":"10.1145\/1754399.1754401","volume":"57","author":"M. Braverman","year":"2010","unstructured":"Braverman M. (2010) Polylogarithmic independence fools $${AC^0}$$ A C 0 circuits. Journal of the Association for Computing Machinery 57(5): 28:1\u201328:10","journal-title":"Journal of the Association for Computing Machinery"},{"key":"134_CR10","doi-asserted-by":"crossref","unstructured":"R. Chen, V. Kabanets, A. Kolokolova, R. Shaltiel & D. Zuckerman (2015a). Mining Circuit Lower Bound Proofs for Meta-Algorithms. Computational Complexity 24(2), 333\u2013392. URL http:\/\/dx.doi.org\/10.1007\/s00037-015-0100-0 .","DOI":"10.1007\/s00037-015-0100-0"},{"key":"134_CR11","doi-asserted-by":"crossref","unstructured":"R. Chen, V. Kabanets & N. Saurabh (2015b). An Improved Deterministic #SAT Algorithm for Small de Morgan Formulas. Algorithmica 1\u201320. ISSN 0178-4617. URL http:\/\/dx.doi.org\/10.1007\/s00453-015-0020-z .","DOI":"10.1007\/s00453-015-0020-z"},{"key":"134_CR12","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"Chernoff H. (1952) A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics 23: 493\u2013509","journal-title":"Annals of Mathematical Statistics"},{"key":"134_CR13","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1017\/S0963548300001358","volume":"3","author":"M. Dubiner","year":"1994","unstructured":"Dubiner M., Zwick U. (1994) How Do Read-Once Formulae Shrink? Combinatorics, Probability & Computing 3: 455\u2013469","journal-title":"Combinatorics, Probability & Computing"},{"key":"134_CR14","doi-asserted-by":"crossref","first-page":"169","DOI":"10.4086\/toc.2008.v004a008","volume":"4","author":"E. Fahri","year":"2008","unstructured":"Fahri E., Goldstone J., Gutmann S. (2008) A quantum algorithm for the hamiltonian NAND tree. Theory of Computing 4: 169\u2013190","journal-title":"Theory of Computing"},{"issue":"1","key":"134_CR15","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"Furst M., Saxe J.B., Sipser M. (1984) Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory 17(1): 13\u201327","journal-title":"Mathematical Systems Theory"},{"key":"134_CR16","unstructured":"A. Ganor, I. Komargodski, T. Lee & R. Raz (2012). On the Noise Stability of Small De Morgan Formulas. Electronic Colloquium on Computational Complexity TR12-174."},{"key":"134_CR17","unstructured":"P. Gopalan, R. Meka, O. Reingold, L. Trevisan & S. Vadhan (2012). Better pseudorandom generators via milder pseudorandom restrictions. In Proceedings of the Fifty-Third Annual IEEE Symposium on Foundations of Computer Science, 120\u2013129."},{"key":"134_CR18","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad (1986). Almost optimal lower bounds for small depth circuits. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, 6\u201320.","DOI":"10.1145\/12130.12132"},{"key":"134_CR19","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1137\/S0097539794261556","volume":"27","author":"J. H\u00e5stad","year":"1998","unstructured":"H\u00e5stad J. (1998) The Shrinkage Exponent Of De Morgan Formulae Is 2. SIAM Journal on Computing 27: 48\u201364","journal-title":"SIAM Journal on Computing"},{"key":"134_CR20","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad (2014). On the Correlation of Parity and Small-Depth Circuits. SIAM J. Comput. 43(5), 1699\u20131708. URL http:\/\/dx.doi.org\/10.1137\/120897432 .","DOI":"10.1137\/120897432"},{"key":"134_CR21","doi-asserted-by":"crossref","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad J., Impagliazzo R., Levin L., Luby M. (1999) A pseudorandom generator from any one-way function. SIAM Journal on Computing 28: 1364\u20131396","journal-title":"SIAM Journal on Computing"},{"issue":"1&2","key":"134_CR22","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0304-3975(94)00081-S","volume":"141","author":"J. H\u00e5stad","year":"1995","unstructured":"H\u00e5stad J., Razborov A.A., Yao A.C. (1995) On the Shrinkage Exponent for Read-Once Formulae. Theoretical Computer Science 141(1&2): 269\u2013282","journal-title":"Theoretical Computer Science"},{"issue":"301","key":"134_CR23","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"Hoeffding W. (1963) Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58(301): 13\u201330","journal-title":"Journal of the American Statistical Association"},{"key":"134_CR24","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo & V. Kabanets (2014). Fourier concentration from shrinkage. In Proceedings of the Twenty-Ninth IEEE Annual Conference on Computational Complexity, 321\u2013332.","DOI":"10.1109\/CCC.2014.39"},{"key":"134_CR25","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, W. Matthews & R. Paturi (2012a). A satisfiability algorithm for AC0. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 961\u2013972.","DOI":"10.1137\/1.9781611973099.77"},{"key":"134_CR26","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, R. Meka & D. Zuckerman (2012b). Pseudorandomness from shrinkage. In Proceedings of the Fifty-Third Annual IEEE Symposium on Foundations of Computer Science, 111\u2013119.","DOI":"10.1109\/FOCS.2012.78"},{"key":"134_CR27","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo & A. Wigderson (1997). P=BPP if E requires exponential circuits: Derandomizing the XOR Lemma. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, 220\u2013229.","DOI":"10.1145\/258533.258590"},{"issue":"1\u20132","key":"134_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","volume":"13","author":"V. Kabanets","year":"2004","unstructured":"Kabanets V., Impagliazzo R. (2004) Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity 13(1\u20132): 1\u201346","journal-title":"Computational Complexity"},{"key":"134_CR29","unstructured":"J. Kahn, G. Kalai & N. Linial (1988). The influence of variables on Boolean functions (extended abstract). In Proceedings of the Twenty-Ninth Annual IEEE Symposium on Foundations of Computer Science, 68\u201380."},{"key":"134_CR30","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/S0019-9958(82)90382-5","volume":"55","author":"R. Kannan","year":"1982","unstructured":"Kannan R. (1982) Circuit-size lower bounds and non-reducibility to sparse sets. Information and Control 55: 40\u201356","journal-title":"Information and Control"},{"issue":"3-4","key":"134_CR31","first-page":"191","volume":"28","author":"R.M. Karp","year":"1982","unstructured":"Karp R.M., Lipton R.J. (1982) Turing machines that take advice. L\u2019Enseignement Math\u00e9matique 28(3-4): 191\u2013209","journal-title":"L\u2019Enseignement Math\u00e9matique"},{"key":"134_CR32","unstructured":"V.M. Khrapchenko (1971). A method of determining lower bounds for the complexity of $${\\pi}$$ \u03c0 -schemes. Matematicheskie Zametki 10(1), 83\u201392. English translation in Mathematical Notes of the Academy of Sciences of the USSR."},{"key":"134_CR33","doi-asserted-by":"crossref","unstructured":"I. Komargodski & R. Raz (2013). Average-case lower bounds for formula size. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, 171\u2013180.","DOI":"10.1145\/2488608.2488630"},{"key":"134_CR34","doi-asserted-by":"crossref","unstructured":"I. Komargodski, R. Raz & A. Tal (2013). Improved Average-Case Lower Bounds for DeMorgan Formula Size. Electronic Colloquium on Computational Complexity 20(58).","DOI":"10.1109\/FOCS.2013.69"},{"key":"134_CR35","unstructured":"T. Lee (2009). A note on the sign degree of formulas. CoRR arXiv:0909.4607 ."},{"issue":"3","key":"134_CR36","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"N. Linial","year":"1993","unstructured":"Linial N., Mansour Y., Nisan N. (1993) Constant Depth Circuits, Fourier Transform and Learnability. Journal of the Association for Computing Machinery 40(3): 607\u2013620","journal-title":"Journal of the Association for Computing Machinery"},{"key":"134_CR37","doi-asserted-by":"crossref","unstructured":"Y. Mansour (1995). An $${O(n^{\\log\\log n})}$$ O ( n log log n ) Learning Algorithm for DNF under the Uniform Distribution. J. Comput. Syst. Sci. 50(3), 543\u2013550. URL http:\/\/dx.doi.org\/10.1006\/jcss.1995.1043 .","DOI":"10.1006\/jcss.1995.1043"},{"key":"134_CR38","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan N., Wigderson A. (1994) Hardness vs. Randomness. Journal of Computer and System Sciences 49: 149\u2013167","journal-title":"Randomness. Journal of Computer and System Sciences"},{"key":"134_CR39","doi-asserted-by":"crossref","unstructured":"R. O\u2019Donnell (2014). Analysis of Boolean Functions. Cambridge University Press. ISBN 978-1-10-703832-5.","DOI":"10.1017\/CBO9781139814782"},{"issue":"2","key":"134_CR40","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1002\/rsa.3240040203","volume":"4","author":"M. Paterson","year":"1993","unstructured":"Paterson M., Zwick U. (1993) Shrinkage of de Morgan Formulae under Restriction. Random Structures and Algorithms 4(2): 135\u2013150","journal-title":"Random Structures and Algorithms"},{"key":"134_CR41","doi-asserted-by":"crossref","unstructured":"B. Reichardt (2009). Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function. In Proceedings of the Fiftieth Annual IEEE Symposium on Foundations of Computer Science, 544\u2013551.","DOI":"10.1109\/FOCS.2009.55"},{"key":"134_CR42","doi-asserted-by":"crossref","unstructured":"B. Reichardt (2011). Reflections for quantum query algorithms. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201911, 560\u2013569.","DOI":"10.1137\/1.9781611973082.44"},{"key":"134_CR43","doi-asserted-by":"crossref","unstructured":"B. Reichardt & R. \u0160palek (2008). Span-program-based quantum algorithms for evaluating formulas. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, 103\u2013112.","DOI":"10.1145\/1374376.1374394"},{"key":"134_CR44","doi-asserted-by":"crossref","unstructured":"R. Santhanam (2010). Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability. In Proceedings of the Fifty-First Annual IEEE Symposium on Foundations of Computer Science, 183\u2013192.","DOI":"10.1109\/FOCS.2010.25"},{"key":"134_CR45","doi-asserted-by":"crossref","unstructured":"R.E. Schapire (1994). Learning probabilistic read-once formulas on product distributions. Machine Learning 14(1), 47\u201381. ISSN 0885-6125. URL http:\/\/dx.doi.org\/10.1007\/BF00993162 .","DOI":"10.1007\/BF00993162"},{"key":"134_CR46","doi-asserted-by":"crossref","unstructured":"K. Seto & S. Tamaki (2012). A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis. In Proceedings of the Twenty-Seventh Annual IEEE Conference on Computational Complexity, 107\u2013116.","DOI":"10.1109\/CCC.2012.29"},{"key":"134_CR47","unstructured":"B.A. Subbotovskaya (1961). Realizations of linear function by formulas using $${\\vee}$$ \u2228 , $${\\&}$$ & , $${^-}$$ - . Doklady Akademii Nauk SSSR 136(3), 553\u2013555. English translation in Soviet Mathematics Doklady."},{"key":"134_CR48","doi-asserted-by":"crossref","unstructured":"A. Tal (2014). Shrinkage of De Morgan Formulae by Spectral Techniques. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, 551\u2013560. URL http:\/\/dx.doi.org\/10.1109\/FOCS.2014.65 .","DOI":"10.1109\/FOCS.2014.65"},{"key":"134_CR49","unstructured":"A. Tal (2015). #SAT Algorithms from Shrinkage. Electronic Colloquium on Computational Complexity (ECCC) 22, 114. URL http:\/\/eccc.hpi-web.de\/report\/2015\/114 ."},{"key":"134_CR50","unstructured":"L. Trevisan & T. Xue (2013). A Derandomized Switching Lemma and an improved Derandomization of AC $${^0}$$ 0 . In Proceedings of the Twenty-Eighth Annual IEEE Conference on Computational Complexity, 242\u2013247."},{"issue":"2","key":"134_CR51","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1016\/S0022-0000(03)00046-1","volume":"67","author":"C. Umans","year":"2003","unstructured":"Umans C. (2003) Pseudo-random generators for all hardnesses. Journal of Computer and System Sciences 67(2): 419\u2013440","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"134_CR52","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/0196-6774(84)90016-6","volume":"5","author":"L.G. Valiant","year":"1984","unstructured":"Valiant L.G. (1984a) Short Monotone Formulae for the Majority Function. Journal of Algorithms 5(3): 363\u2013366","journal-title":"Journal of Algorithms"},{"issue":"11","key":"134_CR53","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"Valiant L.G. (1984b) A theory of the learnable. Communications of the ACM 27(11): 1134\u20131142","journal-title":"Communications of the ACM"},{"key":"134_CR54","doi-asserted-by":"crossref","unstructured":"R. Williams (2013). Improving Exhaustive Search Implies Superpolynomial Lower Bounds. SIAM J. Comput. 42(3), 1218\u20131244. URL http:\/\/dx.doi.org\/10.1137\/10080703X .","DOI":"10.1137\/10080703X"},{"key":"134_CR55","unstructured":"R. Williams (2014). Nonuniform ACC Circuit Lower Bounds. J. ACM 61(1), 2:1\u20132:32. URL http:\/\/doi.acm.org\/10.1145\/2559903 ."},{"key":"134_CR56","unstructured":"R. de Wolf (2008). A Brief Introduction to Fourier Analysis on the Boolean Cube. Number 1 in Graduate Surveys. Theory of Computing Library, 1\u201320. URL http:\/\/www.theoryofcomputing.org\/library.html ."},{"key":"134_CR57","doi-asserted-by":"crossref","unstructured":"A.C. Yao (1982). Theory and applications of trapdoor functions. In Proceedings of the Twenty-Third Annual IEEE Symposium on Foundations of Computer Science, 80\u201391.","DOI":"10.1109\/SFCS.1982.45"},{"key":"134_CR58","doi-asserted-by":"crossref","unstructured":"A.C. Yao (1985). Separating the polynomial-time hierarchy by oracles. In Proceedings of the Twenty-Sixth Annual IEEE Symposium on Foundations of Computer Science, 1\u201310.","DOI":"10.1109\/SFCS.1985.49"},{"key":"134_CR59","unstructured":"F. Zane (1998). Circuits, CNFs, and Satisfiability. Ph.D. thesis, UCSD."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0134-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-016-0134-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0134-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0134-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,7]],"date-time":"2019-09-07T11:17:14Z","timestamp":1567855034000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-016-0134-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,12]]},"references-count":59,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["134"],"URL":"https:\/\/doi.org\/10.1007\/s00037-016-0134-y","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,12]]}}}