{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T07:34:08Z","timestamp":1648798448733},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,6,9]],"date-time":"2016-06-09T00:00:00Z","timestamp":1465430400000},"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":["comput. complex."],"published-print":{"date-parts":[[2017,3]]},"DOI":"10.1007\/s00037-016-0135-x","type":"journal-article","created":{"date-parts":[[2016,6,9]],"date-time":"2016-06-09T08:29:26Z","timestamp":1465460966000},"page":"119-145","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Value of Help Bits in Randomized and Average-Case Complexity"],"prefix":"10.1007","volume":"26","author":[{"given":"Salman","family":"Beigi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Omid","family":"Etesami","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amin","family":"Gohari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,6,9]]},"reference":[{"key":"135_CR1","doi-asserted-by":"crossref","unstructured":"Manindra Agrawal & Vikraman Arvind (1994). Polynomial time truth-table reductions to P-selective sets. In Proceedings of 9th Annual IEEE Conference on Computational Complexity, 24\u201330. IEEE.","DOI":"10.1109\/SCT.1994.315821"},{"issue":"1","key":"135_CR2","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/S0890-5401(03)00091-9","volume":"186","author":"Amihood Amir","year":"2003","unstructured":"Amir Amihood, Beigel Richard, Gasarch William (2003) Some connections between bounded query classes and non-uniform complexity. Information and Computation 186(1): 104\u2013139","journal-title":"Information and Computation"},{"key":"135_CR3","doi-asserted-by":"crossref","unstructured":"Amihood Amir, Richard Beigel & William I Gasarch (1990). Some connections between bounded query classes and nonuniform complexity. In Proceedings of 5th Annual IEEE Conference on Computational Complexity, 232\u2013243. IEEE.","DOI":"10.1109\/SCT.1990.113971"},{"key":"135_CR4","unstructured":"Richard Beigel (1987). Query-limited reducibilities. Ph.D. thesis, Stanford University."},{"key":"135_CR5","unstructured":"Richard Beigel, Lance Fortnow & A Pavan (2002). Membership comparable and p-selective sets. Technical report, 2002-006N, NEC Research Institute."},{"key":"135_CR6","doi-asserted-by":"crossref","unstructured":"Richard Beigel & Tirza Hirst (1998). One help-bit doesn\u2019t help. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, 124\u2013130. ACM.","DOI":"10.1145\/276698.276720"},{"issue":"2","key":"135_CR7","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1006\/inco.1995.1115","volume":"120","author":"Richard Beigel","year":"1995","unstructured":"Beigel Richard, Kummer Martin, Stephan Frank (1995) Approximable sets. Information and Computation 120(2): 304\u2013314","journal-title":"Information and Computation"},{"issue":"2","key":"135_CR8","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0020-0190(90)90101-3","volume":"36","author":"Jin-yi Cai","year":"1990","unstructured":"Cai Jin-yi (1990) Lower bounds for constant-depth circuits in the presence of help bits. Information Processing Letters 36(2): 79\u201383","journal-title":"Information Processing Letters"},{"key":"135_CR9","doi-asserted-by":"crossref","unstructured":"Jin-Yi Cai & Lane A Hemachandra (1988). Enumerative counting is hard. In Proceedings of 3rd Annual IEEE Conference on Computational Complexity, 194\u2013203. IEEE.","DOI":"10.1109\/SCT.1988.5279"},{"key":"135_CR10","unstructured":"William Gasarch (1985). The complexity of optimization functions. Technical report, 1652, Department of Computer Science, University of Maryland."},{"issue":"6","key":"135_CR11","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1007\/BF01204168","volume":"28","author":"I. Gasarch William","year":"1995","unstructured":"Gasarch William I., Krentel Mark W., Rappoport Kevin J. (1995) OptP as the normal behavior of NP-complete problems. Mathematical Systems Theory 28(6): 487\u2013514","journal-title":"Mathematical Systems Theory"},{"key":"135_CR12","doi-asserted-by":"crossref","unstructured":"Oded Goldreich, Noam Nisan & Avi Wigderson (2011). On Yaos XOR-lemma. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 273\u2013301. Springer.","DOI":"10.1007\/978-3-642-22670-0_23"},{"issue":"4","key":"135_CR13","doi-asserted-by":"crossref","first-page":"903","DOI":"10.1137\/S0097539705447281","volume":"35","author":"Alexander Healy","year":"2006","unstructured":"Healy Alexander, Vadhan Salil, Viola Emanuele (2006) Using nondeterminism to amplify hardness. SIAM Journal on Computing 35(4): 903\u2013931","journal-title":"SIAM Journal on Computing"},{"key":"135_CR14","doi-asserted-by":"crossref","unstructured":"Maren Hinrichs & Gerd Wechsung (1997). Time bounded frequency computations. In Proceedings of Twelfth Annual IEEE Conference on Computational Complexity, 185\u2013192. IEEE.","DOI":"10.1109\/CCC.1997.612314"},{"key":"135_CR15","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo (1995). Hard-core distributions for somewhat hard problems. In Proceedings of 36th IEEE Annual Symposium on Foundations of Computer Science, 538\u2013545. IEEE.","DOI":"10.1109\/SFCS.1995.492584"},{"key":"135_CR16","unstructured":"Johannes K\u00f6bler (1995). On the structure of low sets. In Proceedings of 10th Annual IEEE Conference on Computational Complexity, 246\u2013261. IEEE."},{"key":"135_CR17","doi-asserted-by":"crossref","unstructured":"Mark W Krentel (1988). The complexity of optimization problems. Journal of computer and system sciences 36(3), 490\u2013509.","DOI":"10.1016\/0022-0000(88)90039-6"},{"key":"135_CR18","unstructured":"Florence Jessie MacWilliams & Neil James Alexander Sloane (1977). The theory of error correcting codes, volume 16. Elsevier."},{"issue":"3","key":"135_CR19","doi-asserted-by":"crossref","first-page":"1035","DOI":"10.1137\/S0097539795282444","volume":"28","author":"Noam Nisan","year":"1998","unstructured":"Nisan Noam, Rudich Steven, Saks Michael (1998) Products and help bits in decision trees. SIAM Journal on Computing 28(3): 1035\u20131050","journal-title":"SIAM Journal on Computing"},{"key":"135_CR20","doi-asserted-by":"crossref","unstructured":"Ryan O\u2019Donnell (2002). Hardness amplification within NP. In Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, 751\u2013760. ACM.","DOI":"10.1145\/509907.510015"},{"issue":"5","key":"135_CR21","doi-asserted-by":"crossref","first-page":"1068","DOI":"10.1137\/S0097539793258131","volume":"24","author":"Mitsunori Ogihara","year":"1995","unstructured":"Ogihara Mitsunori (1995) Polynomial-time membership comparable sets. SIAM Journal on Computing 24(5): 1068\u20131081","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"135_CR22","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1016\/j.jcss.2004.03.003","volume":"69","author":"Mitsunori Ogihara","year":"2004","unstructured":"Ogihara Mitsunori, Tantau Till (2004) On the reducibility of sets inside NP to sets with low information content. Journal of Computer and System Sciences 69(4): 499\u2013524","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"135_CR23","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/j.1538-7305.1949.tb03624.x","volume":"28","author":"Claude Shannon","year":"1949","unstructured":"Shannon Claude et\u00a0al (1949) The synthesis of two-terminal switching circuits. Bell System Technical Journal 28(1): 59\u201398","journal-title":"Bell System Technical Journal"},{"key":"135_CR24","doi-asserted-by":"crossref","unstructured":"D Sivakumar (1998). On membership comparable sets. In Proceedings of Thirteenth Annual IEEE Conference on Computational Complexity, 2\u20137. IEEE.","DOI":"10.1109\/CCC.1998.694584"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0135-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-016-0135-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0135-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0135-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,9]],"date-time":"2019-09-09T08:49:21Z","timestamp":1568018961000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-016-0135-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,9]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["135"],"URL":"https:\/\/doi.org\/10.1007\/s00037-016-0135-x","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,9]]}}}