{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T10:19:24Z","timestamp":1648549164706},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,11,10]],"date-time":"2011-11-10T00:00:00Z","timestamp":1320883200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2012,9]]},"DOI":"10.1007\/s00037-011-0025-1","type":"journal-article","created":{"date-parts":[[2011,11,9]],"date-time":"2011-11-09T08:57:50Z","timestamp":1320829070000},"page":"479-497","source":"Crossref","is-referenced-by-count":1,"title":["Low-Depth Witnesses are Easy to Find"],"prefix":"10.1007","volume":"21","author":[{"given":"Lu\u00eds","family":"Antunes","sequence":"first","affiliation":[]},{"given":"Lance","family":"Fortnow","sequence":"additional","affiliation":[]},{"given":"Alexandre","family":"Pinto","sequence":"additional","affiliation":[]},{"given":"Andr\u00e9","family":"Souto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,11,10]]},"reference":[{"key":"25_CR1","unstructured":"L. Antunes & L. Fortnow (2009). Worst-Case Running Times for Average-Case Algorithms. Proceedings of Annual IEEE Conference on Computational Complexity 298\u2013303."},{"issue":"3","key":"25_CR2","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1016\/j.tcs.2005.11.033","volume":"354","author":"L. Antunes","year":"2006","unstructured":"Antunes L., Fortnow L., van Melkebeek D., Vinodchandran N. (2006) Computational depth: concept and applications. Theoretical Computer Science 354(3): 391\u2013404 ISSN 0304-3975","journal-title":"Theoretical Computer Science"},{"key":"25_CR3","unstructured":"C. Bennett (1988). Logical depth and physical complexity. In A half-century survey on The Universal Turing Machine, 227\u2013257. Oxford University Press, Inc., New York, NY, USA. ISBN 0-19-853741-7."},{"issue":"4","key":"25_CR4","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1145\/321356.321363","volume":"13","author":"G. Chaitin","year":"1966","unstructured":"Chaitin G. (1966) On the Length of Programs for Computing Finite Binary Sequences. Journal of ACM 13(4): 547\u2013569 ISSN 0004-5411","journal-title":"Journal of ACM"},{"key":"25_CR5","unstructured":"R. Impagliazzo & A. Wigderson (1996). P = BPP unless E has sub-exponential circuits: Derandomizing the XOR Lemma (Preliminary Version). In Proceedings of the 29th ACM Symposium on Theory of Computing, 220\u2013229. ACM Press."},{"issue":"5","key":"25_CR6","doi-asserted-by":"crossref","first-page":"1501","DOI":"10.1137\/S0097539700389652","volume":"31","author":"A. Klivans","year":"2002","unstructured":"Klivans A., van Melkebeek D. (2002) Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. SIAM Journal on Computing 31(5): 1501\u20131526 ISSN 0097-5397","journal-title":"SIAM Journal on Computing"},{"key":"25_CR7","unstructured":"A. Kolmogorov (1950). Foundations of the Theory of Probability. Chelsea Publishing."},{"issue":"1","key":"25_CR8","first-page":"1","volume":"1","author":"A. Kolmogorov","year":"1965","unstructured":"Kolmogorov A. (1965) Three approaches to the quantitative definition of information. Problems of Information Transmission 1(1): 1\u20137","journal-title":"Problems of Information Transmission"},{"key":"25_CR9","first-page":"265","volume":"9","author":"L. Levin","year":"1973","unstructured":"Levin L. (1973) Universal Search Problems. Problems Information Transmission 9: 265\u2013266","journal-title":"Problems Information Transmission"},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"M. Li & P. Vit\u00e1nyi (2008). An Introduction to Kolmogorov Complexity and Its Applications. Springer Publishing Company, Incorporated. ISBN 0387339981, 9780387339986.","DOI":"10.1007\/978-0-387-49820-1"},{"key":"25_CR11","doi-asserted-by":"crossref","unstructured":"P. Miltersen (2001). Derandomizing complexity classes. Handbook of Randomized Computing.","DOI":"10.1007\/978-1-4615-0013-1_19"},{"key":"25_CR12","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":"Journal of Computer and System Sciences"},{"issue":"1","key":"25_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(64)90223-2","volume":"7","author":"R. Solomonoff","year":"1964","unstructured":"Solomonoff R. (1964) A formal theory of inductive inference, part I. Information and Control 7(1): 1\u201322","journal-title":"Information and Control"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0025-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-011-0025-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0025-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,19]],"date-time":"2019-06-19T05:02:06Z","timestamp":1560920526000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-011-0025-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11,10]]},"references-count":13,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,9]]}},"alternative-id":["25"],"URL":"https:\/\/doi.org\/10.1007\/s00037-011-0025-1","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,11,10]]}}}