{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T23:51:40Z","timestamp":1790812300623,"version":"4.1.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,5,16]],"date-time":"2014-05-16T00:00:00Z","timestamp":1400198400000},"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":[[2014,6]]},"DOI":"10.1007\/s00037-014-0087-y","type":"journal-article","created":{"date-parts":[[2014,5,15]],"date-time":"2014-05-15T07:13:36Z","timestamp":1400138016000},"page":"177-205","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["On Uniformity and Circuit Lower Bounds"],"prefix":"10.1007","volume":"23","author":[{"given":"Rahul","family":"Santhanam","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ryan","family":"Williams","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2014,5,16]]},"reference":[{"key":"87_CR1","doi-asserted-by":"crossref","unstructured":"Eric Allender (1999). The Permanent Requires Large Uniform Threshold Circuits. Chicago Journal of Theoretical Computer Science.","DOI":"10.4086\/cjtcs.1999.007"},{"issue":"3","key":"87_CR2","first-page":"14","volume":"57","author":"Eric Allender","year":"2010","unstructured":"Allender Eric, Kouck\u00fd Michal (2010) Amplifying lower bounds by means of self-reducibility. J. ACM 57(3): 14\u201311436","journal-title":"J. ACM"},{"key":"87_CR3","unstructured":"Sanjeev Arora & Boaz Barak (2009). Computational Complexity - A Modern Approach. Cambridge University Press."},{"key":"87_CR4","unstructured":"David Barrington, Neil Immerman & Howard Straubing (1990). On Uniformity within NC 1. Journal of Computer and System Sciences 41."},{"key":"87_CR5","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan & Salil Vadhan (2005). Short PCPs verifiable in polylogarithmic time. In Proceedings of Twentieth Annual IEEE Conference on Computational Complexity, 120\u2013134.","DOI":"10.1109\/CCC.2005.27"},{"key":"87_CR6","unstructured":"Eli Ben-Sasson & Emanuele Viola (2014). Short PCPs with projection queries. Electronic Colloquium on Computational Complexity (ECCC) 21, 17."},{"key":"87_CR7","doi-asserted-by":"crossref","unstructured":"Joshua Buresh-Oppenheim & Rahul Santhanam (2006). Making Hard Problems Harder. In Proceedings of 21st Annual IEEE Conference on Computational Complexity, 73\u201387.","DOI":"10.1109\/CCC.2006.26"},{"key":"87_CR8","unstructured":"Samuel R. Buss (1987). The Boolean formula value problem is in ALOGTIME. In STOC, 123\u2013131"},{"issue":"2","key":"87_CR9","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0022-0000(85)90011-X","volume":"30","author":"Patrick W. Dymond","year":"1985","unstructured":"Dymond Patrick W., Tompa Martin (1985) Speedups of deterministic machines by synchronous parallel machines. Journal of Computer and System Sciences 30(2): 149\u2013161","journal-title":"Journal of Computer and System Sciences"},{"key":"87_CR10","doi-asserted-by":"crossref","unstructured":"Lance Fortnow, Rahul Santhanam & Ryan Williams (2009). Fixed Polynomial Size Circuit Bounds. In Proceedings of 24th Annual IEEE Conference on Computational Complexity, 19\u201326.","DOI":"10.1109\/CCC.2009.21"},{"key":"87_CR11","doi-asserted-by":"crossref","unstructured":"Oded Goldreich & Avi Wigderson (2002). Derandomization that is Rarely Wrong from Short Advice that Is Typically Good. In Proceedings of the 6th International Workshop on Randomization and Approximation Techniques in Computer Science, 209\u2013223.","DOI":"10.1007\/3-540-45726-7_17"},{"key":"87_CR12","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"Juris Hartmanis","year":"1965","unstructured":"Hartmanis Juris, Stearns Richard (1965) On the Computational Complexity of Algorithms. Trans. Amer. Math. Soc. (AMS) 117: 285\u2013306","journal-title":"Trans. Amer. Math. Soc. (AMS)"},{"issue":"1","key":"87_CR13","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1137\/S0097539794261556","volume":"27","author":"Johan H\u00e5stad","year":"1998","unstructured":"H\u00e5stad Johan (1998) The Shrinkage Exponent of de Morgan Formulas is 2. SIAM Journal on Computing 27(1): 48\u201364","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"87_CR14","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1145\/321356.321362","volume":"13","author":"Frederick Hennie","year":"1966","unstructured":"Hennie Frederick, Stearns Richard (1966) Two-Tape Simulation of Multitape Turing Machines. Journal of the ACM 13(4): 533\u2013546","journal-title":"Journal of the ACM"},{"issue":"4","key":"87_CR15","doi-asserted-by":"crossref","first-page":"672","DOI":"10.1016\/S0022-0000(02)00024-7","volume":"65","author":"Russell Impagliazzo","year":"2002","unstructured":"Impagliazzo Russell, Kabanets Valentine, Wigderson Avi (2002) In search of an easy witness: Exponential time vs. probabilistic polynomial time. Journal of Computer and System Sciences 65(4): 672\u2013694","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"87_CR16","doi-asserted-by":"crossref","first-page":"672","DOI":"10.1006\/jcss.2001.1780","volume":"63","author":"Russell Impagliazzo","year":"2001","unstructured":"Impagliazzo Russell, Wigderson Avi (2001) Randomness vs time: derandomization under a uniform assumption. Journal of Computer and System Sciences 63(4): 672\u2013688","journal-title":"Journal of Computer and System Sciences"},{"key":"87_CR17","unstructured":"Hamidreza Jahanjou, Eric Miles & Emanuele Viola (2013). Local reductions. CoRR abs\/1311.3171."},{"issue":"1","key":"87_CR18","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/S0019-9958(82)90382-5","volume":"55","author":"Ravi Kannan","year":"1982","unstructured":"Kannan Ravi (1982) Circuit-Size Lower Bounds and Non-Reducibility to Sparse Sets. Information and Control 55(1): 40\u201356","journal-title":"Information and Control"},{"issue":"3\u20134","key":"87_CR19","first-page":"313","volume":"56","author":"Thilo Mie","year":"2009","unstructured":"Mie Thilo (2009) Short PCPPs verifiable in polylogarithmic time with O(1) queries. Annals of Mathematics and Artificial Intelligence 56(3\u20134): 313\u2013338","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"issue":"4","key":"87_CR20","first-page":"765","volume":"169","author":"Eduard Ne\u010diporuk","year":"1966","unstructured":"Ne\u010diporuk Eduard (1966) On a Boolean Function. Doklady of the Academy of the USSR 169(4): 765\u2013766","journal-title":"Doklady of the Academy of the USSR"},{"issue":"3","key":"87_CR21","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1016\/0022-0000(88)90030-X","volume":"36","author":"Ian Parberry","year":"1988","unstructured":"Parberry Ian, Schnitger Georg (1988) Parallel Computation with Threshold Functions. Journal of Computer and System Sciences 36(3): 278\u2013302","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"87_CR22","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"Walter Ruzzo","year":"1981","unstructured":"Ruzzo Walter (1981) On Uniform Circuit Complexity. Journal of Computer and System Sciences 22(3): 365\u2013383","journal-title":"Journal of Computer and System Sciences"},{"key":"87_CR23","unstructured":"Rahul Santhanam & Ryan Williams (2012). Uniform Circuits, Lower Bounds, and QBF Algorithms. Electronic Colloquium on Computational Complexity (ECCC) 19, 59."},{"key":"87_CR24","doi-asserted-by":"crossref","unstructured":"Luca Trevisan (2001). Extractors and pseudorandom generators. Journal of the ACM 48(4), 860\u2013879. http:\/\/doi.acm.org\/10.1145\/502090.502099 .","DOI":"10.1145\/502090.502099"},{"issue":"3","key":"87_CR25","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/s00037-004-0187-1","volume":"13","author":"Emanuele Viola","year":"2005","unstructured":"Viola Emanuele (2005) The Complexity of Constructing Pseudorandom Generators from Hard Functions. Computational Complexity 13(3): 147\u2013188","journal-title":"Computational Complexity"},{"key":"87_CR26","doi-asserted-by":"crossref","unstructured":"Ryan Williams (2010). Improving Exhaustive Search Implies Superpolynomial Lower Bounds. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, 231\u2013240.","DOI":"10.1145\/1806689.1806723"},{"key":"87_CR27","doi-asserted-by":"crossref","unstructured":"Ryan Williams (2011). Non-uniform ACC Circuit Lower Bounds. In Proceedings of 26th Annual IEEE Conference on Computational Complexity, 115\u2013125.","DOI":"10.1109\/CCC.2011.36"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-014-0087-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-014-0087-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-014-0087-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,10]],"date-time":"2019-08-10T13:30:22Z","timestamp":1565443822000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-014-0087-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,16]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["87"],"URL":"https:\/\/doi.org\/10.1007\/s00037-014-0087-y","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5,16]]}}}