{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:30:48Z","timestamp":1725474648562},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540499947"},{"type":"electronic","value":"9783540499954"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11944836_19","type":"book-chapter","created":{"date-parts":[[2006,11,27]],"date-time":"2006-11-27T23:48:02Z","timestamp":1164671282000},"page":"188-199","source":"Crossref","is-referenced-by-count":2,"title":["Some Results on Average-Case Hardness Within the Polynomial Hierarchy"],"prefix":"10.1007","author":[{"given":"A.","family":"Pavan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Santhanam","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N. V.","family":"Vinodchandran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M.: More on average case vs approximation complexity. In: Proceedings of 44th IEEE Symposium on Foundations of Computer Science, pp. 298\u2013307 (2003)","DOI":"10.1109\/SFCS.2003.1238204"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Ricci-Tersenghi, F.: On the solution-space geometry of random constraint satisfaction problems. In: Proceedings of Symposium on Theory of Computing (to appear, 2006)","DOI":"10.1145\/1132516.1132537"},{"key":"19_CR3","unstructured":"Atserias, A.: Non-uniform hardness for NP via black-box adversaries. In: Proceedings of Conference on Computational Complexity (to appear, 2006)"},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1006\/jcss.1996.0032","volume":"52","author":"N. Bshouty","year":"1996","unstructured":"Bshouty, N., Cleve, R., Kannan, S., Gavalda, R., Tamon, C.: Oracles and queries that are sufficient for exact learning. Journal of Computer and System Sciences\u00a052, 421\u2013433 (1996)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"19_CR5","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s00224-004-1194-y","volume":"38","author":"H. Buhrman","year":"2005","unstructured":"Buhrman, H., Fortnow, L., Pavan, A.: Some results on derandomization. Theory of Computing Systems\u00a038(2), 211\u2013227 (2005)","journal-title":"Theory of Computing Systems"},{"key":"19_CR6","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput.\u00a013, 850\u2013864 (1984)","journal-title":"SIAM J. Comput."},{"key":"19_CR7","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Trevisan, L.: On worst-case to average-case reductions for np problems. In: Proceedings of the 44th IEEE Conference on Foundations of Computer Science, pp. 308\u2013317 (2003)","DOI":"10.1109\/SFCS.2003.1238205"},{"key":"19_CR8","unstructured":"Cai, J.: $S_2^p$ \u2286 ZPPNP. In: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, pp. 620\u2013629 (2001)"},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"Cai, J., Watanabe, O.: On proving circuit lower bounds against the polynomial hierarchy: Positive and negative results. In: Proceedings of Ninth Annual International Conference on Combinatorics and Computing, pp. 202\u2013211 (2003)","DOI":"10.1007\/3-540-45071-8_22"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Feige, U.: Relations between average case complexity and approximation complexity. In: Proceedings of 35th Annual ACM Symposium on Theory of Computing, pp. 534\u2013543 (2002)","DOI":"10.1145\/509907.509985"},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Pavan, A., Sengupta, S.: Proving SAT does not have small circuits with an application to the two queries problem. In: Proceedings of the 18th IEEE Conference on Computational Complexity, pp. 347\u2013350 (2003)","DOI":"10.1109\/CCC.2003.1214433"},{"key":"19_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546891","volume-title":"Foundations of Cryptography","author":"O. Goldreich","year":"2001","unstructured":"Goldreich, O.: Foundations of Cryptography, vol.\u00a01. Cambridge University Press, Cambridge (2001)"},{"key":"19_CR13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721656","volume-title":"Foundations of Cryptography","author":"O. Goldreich","year":"2004","unstructured":"Goldreich, O.: Foundations of Cryptography, vol.\u00a02. Cambridge University Press, Cambridge (2004)"},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"Gutfreund, D., Shaltiel, R., Ta-Shma, A.: If NP languages are hard on the worst-case then it is easy to find their hard instances. In: IEEE Conference on Computational Complexity, pp. 243\u2013257 (2005)","DOI":"10.1109\/CCC.2005.11"},{"key":"19_CR15","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1016\/0022-0000(91)90007-R","volume":"42","author":"Y. Gurevich","year":"1991","unstructured":"Gurevich, Y.: Average case completeness. Journal of Computer and System Sciences\u00a042, 346\u2013398 (1991)","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR16","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1016\/S0022-0000(02)00024-7","volume":"65","author":"R. Impagliazzo","year":"2002","unstructured":"Impagliazzo, R., Kabanets, V., Wigderson, A.: In search of an easy witness: Exponential time vs Probabilistic polynomial time. Journal of Computer and System Sciences\u00a065, 672\u2013694 (2002)","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR17","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1109\/SCT.1995.514853","volume-title":"Proceedings of the 10th Annual Conference on Structure in Complexity Theory","author":"R. Impagliazzo","year":"1995","unstructured":"Impagliazzo, R.: A personal view of average-case complexity theory. In: Proceedings of the 10th Annual Conference on Structure in Complexity Theory, pp. 134\u2013147. IEEE Computer Society Press, Los Alamitos (1995)"},{"key":"19_CR18","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: Randomness vs. time: de-randomization under a uniform assumption. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pp. 734\u2013743 (1998)","DOI":"10.1109\/SFCS.1998.743524"},{"key":"19_CR19","doi-asserted-by":"crossref","unstructured":"Jackson, J., Servedio, R.: On learning random DNF formulas under the uniform distribution. In: Proceedings of 9th International Workshop on Randomness and Computation, pp. 342\u2013353 (2005)","DOI":"10.1007\/11538462_29"},{"issue":"2","key":"19_CR20","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1006\/jcss.2001.1763","volume":"63","author":"V. Kabanets","year":"2001","unstructured":"Kabanets, V.: Easiness assumptions and hardness tests: trading time for zero error. Journal of Computer and System Sciences\u00a063(2), 236\u2013252 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR21","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/S0019-9958(82)90382-5","volume":"55","author":"R. Kannan","year":"1982","unstructured":"Kannan, R.: Circuit-size lower bounds and non-reducibility to sparse sets. Information and Control\u00a055, 40\u201356 (1982)","journal-title":"Information and Control"},{"key":"19_CR22","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0020-0190(83)90044-3","volume":"17","author":"C. Lautemann","year":"1983","unstructured":"Lautemann, C.: BPP and the polynomial hierarchy. Information Processing Letters\u00a017, 215\u2013217 (1983)","journal-title":"Information Processing Letters"},{"key":"19_CR23","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L. Levin","year":"1986","unstructured":"Levin, L.: Average case complete problems. SIAM Journal of Computing\u00a015, 285\u2013286 (1986)","journal-title":"SIAM Journal of Computing"},{"key":"19_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/3-540-48686-0_21","volume-title":"Computing and Combinatorics","author":"P.B. Miltersen","year":"1999","unstructured":"Miltersen, P.B., Vinodchandran, N.V., Watanabe, O.: Super-polynomial versus half-exponential circuit size in the exponential hierarchy. In: Asano, T., Imai, H., Lee, D.T., Nakano, S.-i., Tokuyama, T. (eds.) COCOON 1999. LNCS, vol.\u00a01627, p. 210. Springer, Heidelberg (1999)"},{"key":"19_CR25","doi-asserted-by":"crossref","unstructured":"Sudan, M., Trevisan, L., Vadhan, S.: Pseudorandom generators without the XOR lemma. JCSS: Journal of Computer and System Sciences 62 (2001)","DOI":"10.1006\/jcss.2000.1730"},{"key":"19_CR26","doi-asserted-by":"crossref","unstructured":"Shaltiel, R., Umans, C.: Simple extractors for all min-entropies and a new pseudorandom generator. Journal of the ACM 52 (2005)","DOI":"10.1145\/1059513.1059516"},{"key":"19_CR27","doi-asserted-by":"crossref","unstructured":"Trevisan, L., Vadhan, S.: Pseudorandomness and average-case complexity via uniform reductions. In: Annual IEEE Conference on Computational Complexity, vol.\u00a017 (2002)","DOI":"10.1109\/CCC.2002.1004348"},{"key":"19_CR28","doi-asserted-by":"crossref","unstructured":"Umans, C.: Pseudo-random generators for all hardnesses. In: Symposium on Theory of Computing, pp. 627\u2013634 (2002)","DOI":"10.1145\/509907.509997"},{"key":"19_CR29","doi-asserted-by":"crossref","unstructured":"Viola, E.: On constructing parallel pseudorandom generators from one-way functions. In: Proceedings of the 20th IEEE Conference on Computational Complexity (2005)","DOI":"10.1109\/CCC.2005.16"},{"issue":"1","key":"19_CR30","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1137\/S0097539703438629","volume":"35","author":"D. Melkebeek van","year":"2005","unstructured":"van Melkebeek, D., Santhanam, R.: Holographic proofs and derandomization. SIAM Journal on Computing\u00a035(1), 59\u201390 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"19_CR31","doi-asserted-by":"crossref","unstructured":"Yao, A.: Theory and applications of trapdoor functions. In: Proc. 23rd IEEE Symposium on Foundations of Computer Science, pp. 80\u201391 (1982)","DOI":"10.1109\/SFCS.1982.45"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11944836_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:52:45Z","timestamp":1619495565000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11944836_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540499947","9783540499954"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/11944836_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}