{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T10:34:29Z","timestamp":1649154869195},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,11,29]],"date-time":"2016-11-29T00:00:00Z","timestamp":1480377600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,1]]},"DOI":"10.1007\/s00224-016-9730-0","type":"journal-article","created":{"date-parts":[[2016,11,28]],"date-time":"2016-11-28T23:32:58Z","timestamp":1480375978000},"page":"20-32","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Local Restrictions from the Furst-Saxe-Sipser Paper"],"prefix":"10.1007","volume":"60","author":[{"given":"Suguru","family":"Tamaki","sequence":"first","affiliation":[]},{"given":"Osamu","family":"Watanabe","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,11,29]]},"reference":[{"key":"9730_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, M.: The isomorphism conjecture for NP. In: Computability in Context: Computation and Logic in Real World, pp 19\u201348. World Scientific (2011)","DOI":"10.1142\/9781848162778_0002"},{"key":"9730_CR2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.jcss.2010.06.003","volume":"77","author":"M Agrawal","year":"2011","unstructured":"Agrawal, M.: The isomorphism conjecture for constant depth reductions. J. Comput. Syst. Sci. 77, 3\u201313 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"9730_CR3","doi-asserted-by":"crossref","unstructured":"Agrawal, M., Allender, E.: An isomorphism theorem for circuit complexity. In: Proceedings of 11th Conference on Computational Complexity, pp 2\u201311. IEEE (1996)","DOI":"10.1109\/CCC.1996.507663"},{"key":"9730_CR4","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1006\/jcss.1998.1583","volume":"57","author":"M Agrawal","year":"1998","unstructured":"Agrawal, M., Allender, E., Rudich, S.: Reductions in circuit complexity: An isomorphism theorem and a gap theorem. J. Comput. Syst. Sci. 57, 127\u2013143 (1998)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9730_CR5","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/s00037-001-8191-1","volume":"10","author":"M Agrawal","year":"2001","unstructured":"Agrawal, M., Allender, E., Impagliazzio, R., Pitassi, T., Rudich, S.: Reducing the complexity of reductions. Comput. Complex. 10(2), 117\u2013138 (2001)","journal-title":"Comput. Complex."},{"issue":"1","key":"9730_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M Ajtai","year":"1983","unstructured":"Ajtai, M.: \u03a3 1 1 ${{\\Sigma }_{1}^{1}}$ -formulae on finite structures. Ann. Pure Appl. Logic 24(1), 1\u201348 (1983)","journal-title":"Ann. Pure Appl. Logic"},{"key":"9730_CR7","unstructured":"Beame, P.: A Switching Lemma Primer, Department of Computer Science and Engineering, University of Washington, UW-CSE\u201395-07-01 (1994)"},{"key":"9730_CR8","unstructured":"Berman, L.: Polynomial Reducibilities and Complete Sets. PhD thesis, Cornell University (1977)"},{"key":"9730_CR9","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"1","author":"L Berman","year":"1977","unstructured":"Berman, L., Hartmanis, J.: On isomorphism and density of NP and other complete sets. SIAM J. Comput. 1, 305\u2013322 (1977)","journal-title":"SIAM J. Comput."},{"key":"9730_CR10","doi-asserted-by":"crossref","unstructured":"Boppana, R., Lagarias, J.: One-way functions and circuit complexity. In: Proceedings of Structure in Complexity Theory, Lecture Notes in Computer Science, vol. 223, pp 51\u201365 (1986)","DOI":"10.1007\/3-540-16486-3_89"},{"key":"9730_CR11","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R.: Analysis of Boolean Functions. Cambridge University Press (2014)","DOI":"10.1017\/CBO9781139814782"},{"issue":"1","key":"9730_CR12","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M Furst","year":"1984","unstructured":"Furst, M., Saxe, J., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory 17(1), 13\u201327 (1984)","journal-title":"Math. Syst. Theory"},{"key":"9730_CR13","volume-title":"Computational Limitations for Small Depth Circuits","author":"J H\u00e5stad","year":"1986","unstructured":"H\u00e5stad, J.: Computational Limitations for Small Depth Circuits. MIT Press, Cambridge (1986)"},{"key":"9730_CR14","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Almost optimal lower bounds for small depth circuits. In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pp 6\u201320 (1986)","DOI":"10.1145\/12130.12132"},{"key":"9730_CR15","doi-asserted-by":"crossref","unstructured":"Kahn, J., Kalai, G., Linial, N.: The influence of variables on Boolean functions. In: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pp 68\u201380 (1988)","DOI":"10.1109\/SFCS.1988.21923"},{"key":"9730_CR16","doi-asserted-by":"crossref","unstructured":"Kurtz, S., Mahaney, S., Royer, J.: The structure of complete degrees. In: Selman, A. (ed.) Complexity Theory Retrospective, pp 108\u2013146. Springer-Verlag (1990)","DOI":"10.1007\/978-1-4612-4478-3_7"},{"issue":"3","key":"9730_CR17","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.: Constant depth circuits, Fourier transform, and learnability. J. Assoc. Comput. Mach. 40(3), 607\u2013620 (1993)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"2","key":"9730_CR18","first-page":"107","volume":"6","author":"O Lupanov","year":"1961","unstructured":"Lupanov, O.: Implementing the algebra of logic functions in terms of constant-depth formulas in the basis +,\u2217,\u2212. Sov. Phys. Dokl. 6(2), 107\u2013108 (1961)","journal-title":"Sov. Phys. Dokl."},{"key":"9730_CR19","doi-asserted-by":"crossref","unstructured":"Rossman, B.: The average sensitivity of bounded-depth formulas. In: Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, pp 424\u2013430. IEEE (2015)","DOI":"10.1109\/FOCS.2015.33"},{"key":"9730_CR20","doi-asserted-by":"crossref","unstructured":"Rossman, B., Servedio, R., Tan, L.: An average-case depth hierarchy theorem for Boolean circuits. In: Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, pp 1030\u20131048. IEEE (2015)","DOI":"10.1109\/FOCS.2015.67"},{"issue":"4","key":"9730_CR21","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1145\/2852040.2852052","volume":"46","author":"B Rossman","year":"2015","unstructured":"Rossman, B., Servedio, R., Tan, L.: Complexity theory column 89: The polynomial hierarchy, random oracles, and Boolean circuits. SIGACT News 46(4), 50\u201368 (2015)","journal-title":"SIGACT News"},{"key":"9730_CR22","doi-asserted-by":"crossref","unstructured":"Santhanam, R., perebor, Fighting: New and improved algorithms for formula and QBF satisfiability. In: Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, pp 183\u2013192. IEEE (2010)","DOI":"10.1109\/FOCS.2010.25"},{"issue":"2","key":"9730_CR23","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s00037-013-0067-7","volume":"22","author":"K Seto","year":"2013","unstructured":"Seto, K., Tamaki, S.: A satisfiability algorithm and average-case hardness for formulas over the full binary basis. Comput. Complex. 22(2), 245\u2013274 (2013)","journal-title":"Comput. Complex."},{"key":"9730_CR24","first-page":"110","volume":"2","author":"B Subbotovskaya","year":"1961","unstructured":"Subbotovskaya, B.: Realizations of linear functions by formulas using +,\u2217,\u2212. Sov. Phys. Dokl. 2, 110\u2013112 (1961)","journal-title":"Sov. Phys. Dokl."},{"key":"9730_CR25","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0304-3975(85)90218-X","volume":"38","author":"O Watanabe","year":"1985","unstructured":"Watanabe, O.: On one-one polynomial time equivalence relations. Theor. Comput. Sci. 38, 157\u2013165 (1985)","journal-title":"Theor. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9730-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9730-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9730-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,25]],"date-time":"2017-06-25T00:42:12Z","timestamp":1498351332000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9730-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,29]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["9730"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9730-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,29]]}}}