{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:14:40Z","timestamp":1725664480471},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_26","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:04:28Z","timestamp":1330290268000},"page":"307-318","source":"Crossref","is-referenced-by-count":8,"title":["On the existence of hard sparse sets under weak reductions"],"prefix":"10.1007","author":[{"given":"Jin -Yi","family":"Cai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashish V.","family":"Naik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Sivakumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"N. Alon, O. Goldreich, J. Hastad, and R. Peralta. Simple constructions of almost k-wise independent random variables. In Proc. 31st FOCS, pages 544\u2013553, 1990.","DOI":"10.1109\/FSCS.1990.89575"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"V. Arvind, J. K\u00f6bler, and M. Mundhenk. On bounded truth-table, conjunctive, and randomized reductions to sparse sets. In Proc. 12th FST & TCS, Lecture Notes in Computer Science, Springer-Verlag, 1992.","DOI":"10.1007\/3-540-56287-7_101"},{"key":"26_CR3","unstructured":"L. Berman. Polynomial Reducibilities and Complete Sets. PhD thesis, Cornell University, 1977."},{"key":"26_CR4","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"L. Berman and H. Hartmanis. On isomorphisms and density of NP and other complete sets. SIAM Journal on Computing, 6:305\u2013322, 1977.","journal-title":"SIAM Journal on Computing"},{"key":"26_CR5","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/S0019-9958(82)90766-5","volume":"52","author":"A. Borodin","year":"1982","unstructured":"A. Borodin, J. von zur Gathen, and J. Hopcroft. Fast parallel matrix and GCD computations. Information and Control, 52:241\u2013256, 1982.","journal-title":"Information and Control"},{"key":"26_CR6","doi-asserted-by":"crossref","unstructured":"S. Buss. The Boolean formula value problem is in ALOGTIME. In Proc. 19th STOC, pages 123\u2013131, 1987.","DOI":"10.1145\/28395.28409"},{"key":"26_CR7","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1137\/0221046","volume":"21","author":"S. Buss","year":"1992","unstructured":"S. Buss, S. Cook, A. Gupta, and V. Ramachandran. An optimal parallel algorithm for formula evaluation. SIAM Journal on Computing, 21:755\u2013780, 1992.","journal-title":"SIAM Journal on Computing"},{"key":"26_CR8","unstructured":"J. Cai and D. Sivakumar. The resolution of a Hartmanis conjecture. In Proc. 36th FOCS, pages 362\u2013373, 1995."},{"key":"26_CR9","unstructured":"J. Cai and D. Sivakumar. Resolution of Hartmanis' Conjecture for NL-hard sparse sets. Submitted, 1995."},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"A.L. Chistov. Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic. In Proc. 5th FCT, Lecture Notes in Computer Science, pages 63\u201369. Springer-Verlag, 1985.","DOI":"10.1007\/BFb0028792"},{"key":"26_CR11","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. Cook","year":"1985","unstructured":"S. Cook. A taxonomy of problems with fast parallel algorithms. Information and Control, 64:2\u201322, 1985.","journal-title":"Information and Control"},{"key":"26_CR12","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0208034","volume":"8","author":"S. Fortune","year":"1979","unstructured":"S. Fortune. A note on sparse complete sets. SIAM Journal on Computing, 8:431\u2013433, 1979.","journal-title":"SIAM Journal on Computing"},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"O. Goldreich, L. Levin. A hard-core predicate for all one-way functions. In Proc. 21st STOC, pages 25\u201332, 1989.","DOI":"10.1145\/73007.73010"},{"issue":"3","key":"26_CR14","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0304-3975(78)90018-X","volume":"7","author":"J. Hartmanis","year":"1978","unstructured":"J. Hartmanis. On log-tape isomorphisms of complete sets. Theoretical Computer Science, 7(3):273\u2013286, 1978.","journal-title":"Theoretical Computer Science"},{"key":"26_CR15","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/BF01206639","volume":"4","author":"L. Hemachandra","year":"1994","unstructured":"L. Hemachandra, M. Ogiwara, and S. Toda. Space-efficient recognition of sparse self-reducible languages. Computational Complexity, 4:262\u2013296, 1994.","journal-title":"Computational Complexity"},{"key":"26_CR16","doi-asserted-by":"crossref","unstructured":"L. Hemachandra, M. Ogiwara, and O. Watanabe. How hard are sparse sets. In Proc. 7th Structures, pages 222\u2013238, 1992.","DOI":"10.1109\/SCT.1992.215396"},{"key":"26_CR17","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0019-9958(86)80020-1","volume":"71","author":"M. Karpinski","year":"1986","unstructured":"M. Karpinski and R. Verbeek. On the Power of Two-Way Random Generators and the Impossibility of Deterministic Poly-Space Simulation. Information and Control, Vol. 71, pages 131\u2013142, 1986.","journal-title":"Information and Control"},{"key":"26_CR18","doi-asserted-by":"crossref","unstructured":"R. Karp and R. Lipton. Some connections between nonuniform and uniform complexity classes. In Proc. 12th ACM Symp. on Theory of Computing, pages 302\u2013309, 1980.","DOI":"10.1145\/800141.804678"},{"issue":"1","key":"26_CR19","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"R. Ladner","year":"1975","unstructured":"R. Ladner. The circuit value problem is log space complete for P. SIGACT News, 7(1):18\u201320, 1975.","journal-title":"SIGACT News"},{"key":"26_CR20","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R. Ladner","year":"1975","unstructured":"R. Ladner, N. Lynch, and A. Selman. A comparison of polynomial time reducibilities. Theoretical Computer Science, 1:103\u2013123, 1975.","journal-title":"Theoretical Computer Science"},{"key":"26_CR21","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(82)90002-2","volume":"25","author":"S. Mahaney","year":"1982","unstructured":"S. Mahaney. Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis. Journal of Computer and System Sciences, 25:130\u2013143, 1982.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"26_CR22","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BF02579205","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"K. Mulmuley. A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Combinatorica, 7(1):101\u2013104, 1987.","journal-title":"Combinatorica"},{"key":"26_CR23","doi-asserted-by":"crossref","unstructured":"J. Naor and M. Naor. Small-bias probability spaces: efficient constructions and applications. In Proc. 22nd STOC, pages 213\u2013223, 1990.","DOI":"10.1145\/100216.100244"},{"key":"26_CR24","doi-asserted-by":"crossref","unstructured":"M. Ogihara. Sparse hard sets for P yield space-efficient algorithms. In Proc. 36th FOCS, pages 354\u2013361, 1995.","DOI":"10.1109\/SFCS.1995.492491"},{"key":"26_CR25","doi-asserted-by":"crossref","unstructured":"M. Ogiwara and A. Lozano. On one-query self-reducible sets. In Proc. 6th Structures, pages 139\u2013151, 1991.","DOI":"10.1109\/SCT.1991.160254"},{"issue":"3","key":"26_CR26","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1137\/0220030","volume":"20","author":"M. Ogiwara","year":"1991","unstructured":"M. Ogiwara and O. Watanabe. On polynomial-time bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal on Computing, 20(3):471\u2013483, 1991.","journal-title":"SIAM Journal on Computing"},{"key":"26_CR27","doi-asserted-by":"crossref","unstructured":"D. Ranjan and P. Rohatgi. On randomized reductions to sparse sets. In Proc. 7th Structures, pages 239\u2013242, 1992.","DOI":"10.1109\/SCT.1992.215397"},{"key":"26_CR28","doi-asserted-by":"crossref","unstructured":"L. Valiant and V. Vazirani. NP is as easy as detecting unique solutions. In Proceedings of 17th ACM Symposium Theory of Computing, pages 458\u2013463, 1985.","DOI":"10.1145\/22145.22196"},{"key":"26_CR29","doi-asserted-by":"crossref","unstructured":"J.H. van Lint. Introduction to Coding Theory. Springer-Verlag, 1991.","DOI":"10.1007\/978-3-662-00174-5"},{"key":"26_CR30","unstructured":"D. van Melkebeek. On Truth-table Hard Sparse sets for P. University of Chicago Technical Report 95-06. 1995."},{"issue":"3","key":"26_CR31","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/141914.141921","volume":"23","author":"P. Young","year":"1992","unstructured":"P. Young. How reductions to sparse sets collapse the polynomial-time hierarchy: A primer (Part I). SIGACT News, 23(3):107\u2013117, 1992.","journal-title":"SIGACT News"},{"issue":"4","key":"26_CR32","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1145\/148080.148084","volume":"23","author":"P. Young","year":"1992","unstructured":"P. Young. How reductions to sparse sets collapse the polynomial-time hierarchy: A primer (Part II). SIGACT News, 23(4):83\u201394, 1992.","journal-title":"SIGACT News"}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:02:34Z","timestamp":1605646954000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}