{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T17:17:41Z","timestamp":1712423861640},"reference-count":69,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,4,21]],"date-time":"2015-04-21T00:00:00Z","timestamp":1429574400000},"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":[[2015,6]]},"DOI":"10.1007\/s00037-015-0100-0","type":"journal-article","created":{"date-parts":[[2015,4,20]],"date-time":"2015-04-20T09:07:36Z","timestamp":1429520856000},"page":"333-392","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Mining Circuit Lower Bound Proofs for Meta-Algorithms"],"prefix":"10.1007","volume":"24","author":[{"given":"Ruiwen","family":"Chen","sequence":"first","affiliation":[]},{"given":"Valentine","family":"Kabanets","sequence":"additional","affiliation":[]},{"given":"Antonina","family":"Kolokolova","sequence":"additional","affiliation":[]},{"given":"Ronen","family":"Shaltiel","sequence":"additional","affiliation":[]},{"given":"David","family":"Zuckerman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,4,21]]},"reference":[{"key":"100_CR1","doi-asserted-by":"crossref","unstructured":"M. Agrawal (2005). Proving lower bounds via pseudo-random generators. In Proceedings of the Twenty-Fifth Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 92\u2013105.","DOI":"10.1007\/11590156_6"},{"issue":"1","key":"100_CR2","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1137\/060664537","volume":"38","author":"E. Allender","year":"2008","unstructured":"Allender E., Hellerstein L., McCabe P., Pitassi T., Saks M.E. (2008) Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table. SIAM Journal on Computing 38(1): 63\u201384","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"100_CR3","doi-asserted-by":"crossref","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. (1992) Simple Constructions of Almost k\u2212wise Independent Random Variables. Random Structures and Algorithms 3(3): 289\u2013304","journal-title":"Random Structures and Algorithms"},{"issue":"1","key":"100_CR4","first-page":"70","volume":"42","author":"A.E. Andreev","year":"1987","unstructured":"Andreev A.E. (1987) On a method of obtaining more than quadratic effective lower bounds for the complexity of \u03c0-schemes. Vestnik Moskovskogo Universiteta. Matematika 42(1): 70\u201373 English translation in Moscow University Mathematics Bulletin.","journal-title":"Vestnik Moskovskogo Universiteta. Matematika"},{"key":"100_CR5","doi-asserted-by":"crossref","unstructured":"A.E. Andreev, J. L. Baskakov, A. E. F. Clementi & J. D. P. Rolim (1999). Small Pseudo-Random Sets Yield Hard Functions: New Tight Explict Lower Bounds for Branching Programs. In Proceedings of the Twenty-Sixth International Colloquium on Automata, Languages, and Programming, 179\u2013189.","DOI":"10.1007\/3-540-48523-6_15"},{"key":"100_CR6","doi-asserted-by":"crossref","unstructured":"S. Arora & B. Barak (2009). Complexity theory: a modern approach. Cambridge University Press, New York.","DOI":"10.1017\/CBO9780511804090"},{"issue":"6","key":"100_CR7","doi-asserted-by":"crossref","first-page":"2220","DOI":"10.1137\/070691954","volume":"38","author":"L. Bazzi","year":"2009","unstructured":"Bazzi L. (2009) Polylogarithmic Independence Can Fool DNF Formulas. SIAM Journal on Computing 38(6): 2220\u20132272","journal-title":"SIAM Journal on Computing"},{"key":"100_CR8","unstructured":"P. Beame (1994). A switching lemma primer. Technical report, Department of Computer Science and Engineering, University of Washington."},{"key":"100_CR9","unstructured":"P. Beame, R. Impagliazzo & S. Srinivasan (2012). Approximating AC 0 by Small Height Decision Trees and a Deterministic Algorithm for #AC 0 SAT. In Proceedings of the Twenty-Seventh Annual IEEE Conference on Computational Complexity, 117\u2013125."},{"key":"100_CR10","unstructured":"S.J. Berkowitz (1982). On some relationships between monotone and non-monotone circuit complexity. Technical report, University of Toronto."},{"key":"100_CR11","doi-asserted-by":"crossref","unstructured":"M. Blum & S. Micali (1984). How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal on Computing 13, 850\u2013864.","DOI":"10.1137\/0213053"},{"key":"100_CR12","unstructured":"R. B. Boppana & M. Sipser (1990). The complexity of finite functions. In Handbook of theoretical computer science (vol. A), J. van Leeuwen, editor, 757\u2013804. MIT Press, Cambridge, MA, USA."},{"issue":"28","key":"100_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1754399.1754401","volume":"57","author":"M. Braverman","year":"2010","unstructured":"M. Braverman (2010). Polylogarithmic independence fools AC 0 circuits. Journal of the Association for Computing Machinery 57, 28:1\u201328:10.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"100_CR14","doi-asserted-by":"crossref","unstructured":"C. Calabro, R. Impagliazzo & R. Paturi (2009). The Complexity of Satisfiability of Small Depth Circuits. In Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, 75\u201385.","DOI":"10.1007\/978-3-642-11269-0_6"},{"key":"100_CR15","doi-asserted-by":"crossref","unstructured":"R. Chen, V. Kabanets & N. Saurabh (2014). An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas. In Proceedings of the Thirty-Ninth International Symposium on Mathematical Foundations of Computer Science, 165\u2013176.","DOI":"10.1007\/978-3-662-44465-8_15"},{"key":"100_CR16","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal V. (1979) A greedy heuristic for the set covering problem. Mathematics of Operations Research 4: 233\u2013235","journal-title":"Mathematics of Operations Research"},{"key":"100_CR17","doi-asserted-by":"crossref","unstructured":"S.A. Cook (1971). The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"100_CR18","unstructured":"E. Dantsin & E.A. Hirsch (2009). Worst-Case Upper Bounds. In Handbook of Satisfiability, 403\u2013424. IOS Press."},{"key":"100_CR19","doi-asserted-by":"crossref","unstructured":"V. Feldman (2009). Hardness of approximate two-level logic minimization and PAC learning with membership queries. Journal of Computer and System Sciences 75(1), 13\u201326.","DOI":"10.1016\/j.jcss.2008.07.007"},{"key":"100_CR20","doi-asserted-by":"crossref","unstructured":"L. Fortnow & A.R. Klivans (2006). Efficient Learning Algorithms Yield Circuit Lower Bounds. In Proceedings of the Nineteenth Annual Conference on Learning Theory, 350\u2013363.","DOI":"10.1007\/11776420_27"},{"issue":"1","key":"100_CR21","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":"100_CR22","doi-asserted-by":"crossref","unstructured":"A. Gabizon & R. Shaltiel (2012). Invertible Zero-Error Dispersers and Defective Memory with Stuck-At Errors. In Proceedings of APPROX-RANDOM, volume 7408 of Lecture Notes in Computer Science, 553\u2013564. Springer-Verlag.","DOI":"10.1007\/978-3-642-32512-0_47"},{"key":"100_CR23","doi-asserted-by":"crossref","unstructured":"P. Gopalan & R. A. Servedio (2010). Learning and lower bounds for AC 0 with threshold gates. In Proceedings of APPROX-RANDOM, volume 6302 of Lecture Notes in Computer Science, 588\u2013601. Springer-Verlag.","DOI":"10.1007\/978-3-642-15369-3_44"},{"key":"100_CR24","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":"100_CR25","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad (1998). The shrinkage exponent of de Morgan formulae is 2. SIAM Journal on Computing 27, 48\u201364.","DOI":"10.1137\/S0097539794261556"},{"key":"100_CR26","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, R. Impagliazzo, L. Levin & M. Luby (1999). A pseudorandom generator from any one-way function. SIAM Journal on Computing 28, 1364\u20131396.","DOI":"10.1137\/S0097539793244708"},{"key":"100_CR27","unstructured":"J. Heintz & C.-P. Schnorr (1982). Testing polynomials which are easy to compute. L\u2019Enseignement Math\u00e9matique 30, 237\u2013254."},{"key":"100_CR28","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, V. Kabanets & A. Wigderson (2002). In search of an easy witness: Exponential time vs. probabilistic polynomial time. Journal of Computer and System Sciences 65(4), 672\u2013694.","DOI":"10.1016\/S0022-0000(02)00024-7"},{"key":"100_CR29","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, W. Matthews & R. Paturi (2012a). A satisfiability algorithm for AC 0. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 961\u2013972.","DOI":"10.1137\/1.9781611973099.77"},{"key":"100_CR30","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":"100_CR31","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"},{"key":"100_CR32","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson D.S. (1974) Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences 9: 256\u2013278","journal-title":"Journal of Computer and System Sciences"},{"key":"100_CR33","doi-asserted-by":"crossref","unstructured":"S. Jukna (2012). Boolean Function Complexity: Advances and Frontiers. Springer.","DOI":"10.1007\/978-3-642-24508-4"},{"issue":"2","key":"100_CR34","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1006\/jcss.2001.1763","volume":"63","author":"V. Kabanets","year":"2001","unstructured":"Kabanets V. (2001) Easiness Assumptions and Hardness Tests: Trading Time for Zero Error. Journal of Computer and System Sciences 63(2): 236\u2013252","journal-title":"Journal of Computer and System Sciences"},{"key":"100_CR35","doi-asserted-by":"crossref","unstructured":"V. Kabanets & J.-Y. Cai (2000). Circuit Minimization Problem. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 73\u201379.","DOI":"10.1145\/335305.335314"},{"key":"100_CR36","doi-asserted-by":"crossref","unstructured":"V. Kabanets & R. Impagliazzo (2004). Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity 13(1\u20132), 1\u201346.","DOI":"10.1007\/s00037-004-0182-6"},{"key":"100_CR37","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"},{"key":"100_CR38","doi-asserted-by":"crossref","unstructured":"G. Karakostas, J. Kinne & D. van Melkebeek (2012). On derandomization and average-case complexity of monotone functions. Theoretical Computer Science 434, 35\u201344.","DOI":"10.1016\/j.tcs.2012.02.017"},{"key":"100_CR39","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":"100_CR40","doi-asserted-by":"crossref","unstructured":"I. Komargodski, R. Raz & A. Tal (2013). Improved Average-Case Lower Bounds for DeMorgan Formula Size. In Proceedings of the Fifty-Fourth Annual IEEE Symposium on Foundations of Computer Science, 588\u2013597.","DOI":"10.1109\/FOCS.2013.69"},{"key":"100_CR41","first-page":"265","volume":"9","author":"L. Levin","year":"1973","unstructured":"Levin L. (1973) Universal sorting problems. Problems of Information Transmission 9: 265\u2013266","journal-title":"Problems of Information Transmission"},{"key":"100_CR42","doi-asserted-by":"crossref","unstructured":"N. Linial, Y. Mansour & N. Nisan (1993). Constant Depth Circuits, Fourier Transform and Learnability. Journal of the Association for Computing Machinery 40(3), 607\u2013620.","DOI":"10.1145\/174130.174138"},{"key":"100_CR43","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz L. (1975) On the ratio of optimal integral and fractional covers. Discrete Mathematics 13: 383\u2013390","journal-title":"Discrete Mathematics"},{"key":"100_CR44","unstructured":"O.B. Lupanov (1958). On the synthesis of switching circuits. Doklady Akademii Nauk SSSR 119(1), 23\u201326. English translation in Soviet Mathematics Doklady."},{"key":"100_CR45","unstructured":"W.J. Masek (1979). Some NP-complete set covering problems. Manuscript."},{"key":"100_CR46","unstructured":"E.I. Nechiporuk (1966). On a Boolean function. Doklady Akademii Nauk SSSR 169(4), 765\u2013766. English translation in Soviet Mathematics Doklady."},{"key":"100_CR47","doi-asserted-by":"crossref","unstructured":"N. Nisan & A. Wigderson (1994). Hardness vs. Randomness. Journal of Computer and System Sciences 49, 149\u2013167.","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"100_CR48","doi-asserted-by":"crossref","unstructured":"M. Paterson & U. Zwick (1993). Shrinkage of de Morgan Formulae under Restriction. Random Structures and Algorithms 4(2), 135\u2013150.","DOI":"10.1002\/rsa.3240040203"},{"key":"100_CR49","doi-asserted-by":"crossref","unstructured":"N. Pippenger (1977). The complexity of monotone boolean functions. Theory of Computing Systems 11, 289\u2013316. ISSN 1432-4350.","DOI":"10.1007\/BF01768483"},{"key":"100_CR50","doi-asserted-by":"crossref","unstructured":"A. Rao (2009). Extractors for Low-Weight Affine Sources. In Proceedings of the Twenty-Fourth Annual IEEE Conference on Computational Complexity, 95\u2013101.","DOI":"10.1109\/CCC.2009.36"},{"key":"100_CR51","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/BF01137685","volume":"41","author":"A.A. Razborov","year":"1987","unstructured":"Razborov A.A. (1987) Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes 41: 333\u2013338","journal-title":"Mathematical Notes"},{"key":"100_CR52","unstructured":"A.A. Razborov (1993). Bounded arithmetic and lower bounds in boolean complexity. In Feasible Mathematics II, 344\u2013386. Birkhauser."},{"key":"100_CR53","doi-asserted-by":"crossref","unstructured":"A.A. Razborov & S. Rudich (1997). Natural proofs. Journal of Computer and System Sciences 55, 24\u201335.","DOI":"10.1006\/jcss.1997.1494"},{"key":"100_CR54","unstructured":"N.P. Red\u2019kin (1979). On the realization of monotone Boolean functions by contact circuits.Problemy Kibernetiki 35, 87\u2013110. (in Russian)."},{"key":"100_CR55","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":"100_CR56","unstructured":"P. Savick\u00fd & S. Z\u00e1k (1996). A large lower bound for 1-branching programs. Electronic Colloquium on Computational Complexity TR96-036."},{"key":"100_CR57","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":"100_CR58","doi-asserted-by":"crossref","unstructured":"R. Smolensky (1987). Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, 77\u201382.","DOI":"10.1145\/28395.28404"},{"key":"100_CR59","unstructured":"B.A. Subbotovskaya (1961). Realizations of linear function by formulas using \u2228, &, \u2212. Doklady Akademii Nauk SSSR 136(3), 553\u2013555. English translation in Soviet Mathematics Doklady."},{"key":"100_CR60","doi-asserted-by":"crossref","unstructured":"M. Sudan, L. Trevisan & S. Vadhan (2001). Pseudorandom generators without the XOR lemma. Journal of Computer and System Sciences 62(2), 236\u2013266.","DOI":"10.1006\/jcss.2000.1730"},{"key":"100_CR61","doi-asserted-by":"crossref","unstructured":"M. Tulsiani & J. Wolf (2011). Quadratic Goldreich-Levin Theorems. In Proceedings of the Fifty-Second Annual IEEE Symposium on Foundations of Computer Science, 619\u2013628.","DOI":"10.1109\/FOCS.2011.59"},{"key":"100_CR62","unstructured":"I. Wegener (1987). The Complexity of Boolean Functions. J. Wiley, New York."},{"key":"100_CR63","doi-asserted-by":"crossref","unstructured":"R. Williams (2010). Improving exhaustive search implies superpolynomial lower bounds. In Proceedings of the Forty-Second Annual ACM Symposium on Theory of Computing, 231\u2013240.","DOI":"10.1145\/1806689.1806723"},{"key":"100_CR64","doi-asserted-by":"crossref","unstructured":"R. Williams (2011). Non-uniform ACC circuit lower bounds. In Proceedings of the Twenty-Sixth Annual IEEE Conference on Computational Complexity, 115\u2013125.","DOI":"10.1109\/CCC.2011.36"},{"key":"100_CR65","doi-asserted-by":"crossref","unstructured":"R. Williams (2013). Natural Proofs Versus Derandomization. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, 21\u201330.","DOI":"10.1145\/2488608.2488612"},{"key":"100_CR66","unstructured":"S.V. Yablonski (1959). On the impossibility of eliminating PEREBOR in solving some problems of circuit theory. Doklady Akademii Nauk SSSR 124(1), 44\u201347. English translation in Soviet Mathematics Doklady."},{"key":"100_CR67","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":"100_CR68","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":"100_CR69","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-015-0100-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-015-0100-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-015-0100-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T15:01:59Z","timestamp":1558537319000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-015-0100-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,21]]},"references-count":69,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,6]]}},"alternative-id":["100"],"URL":"https:\/\/doi.org\/10.1007\/s00037-015-0100-0","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,21]]}}}