{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T11:53:15Z","timestamp":1676980395332},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,11,18]],"date-time":"2011-11-18T00:00:00Z","timestamp":1321574400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2012,10]]},"DOI":"10.1007\/s00224-011-9368-x","type":"journal-article","created":{"date-parts":[[2011,11,17]],"date-time":"2011-11-17T11:34:23Z","timestamp":1321529663000},"page":"297-312","source":"Crossref","is-referenced-by-count":3,"title":["The Complexity of Explicit Constructions"],"prefix":"10.1007","volume":"51","author":[{"given":"Rahul","family":"Santhanam","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,11,18]]},"reference":[{"key":"9368_CR1","unstructured":"Agrawal, M., Kayal, N., Saxena, N.: PRIMES is in P. Report, Department of Computer Science and Engineering, Indian Institute of Technology, Kanpur (2002)"},{"key":"9368_CR2","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley, New York (1992), with an appendix on open problems by Paul Erd\u00f6s"},{"key":"9368_CR3","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Complexity Theory: A Modern Approach","author":"S. Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Complexity Theory: A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"key":"9368_CR4","first-page":"671","volume-title":"Proceedings of 38th Symposium on Theory of Computing","author":"B. Barak","year":"2006","unstructured":"Barak, B., Rao, A., Shaltiel, R., Wigderson, A.: 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction. In: Proceedings of 38th Symposium on Theory of Computing, pp.\u00a0671\u2013680 (2006)"},{"key":"9368_CR5","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"Blum, M., Micali, S.: How to generate cryptographically strong sequence of pseudo-random bits. SIAM J. Comput. 13, 850\u2013864 (1984)","journal-title":"SIAM J. Comput."},{"issue":"4\u20135","key":"9368_CR6","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1016\/0020-0190(81)90050-8","volume":"13","author":"M. Blum","year":"1981","unstructured":"Blum, M., Karp, R., Vornberger, O., Papadimitriou, C., Yannakakis, M.: The complexity of testing whether a graph is a superconcentrator. Inf. Process. Lett. 13(4\u20135), 164\u2013167 (1981)","journal-title":"Inf. Process. Lett."},{"key":"9368_CR7","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/BF02579457","volume":"1","author":"P. Frankl","year":"1981","unstructured":"Frankl, P., Wilson, R.: Intersection theorems with geometric consequences. Combinatorica 1, 357\u2013368 (1981)","journal-title":"Combinatorica"},{"key":"9368_CR8","first-page":"96","volume-title":"Proceedings of 24th International Conference on the Theory and Application of Cryptographic Techniques (CRYPTO \u201995)","author":"D. Harnik","year":"2005","unstructured":"Harnik, D., Kilian, J., Naor, M., Reingold, O., Rosen, A.: Robust combiners for oblivious transfer and other cryptographic primitives. In: Proceedings of 24th International Conference on the Theory and Application of Cryptographic Techniques (CRYPTO \u201995), pp.\u00a096\u2013113 (2005)"},{"key":"9368_CR9","first-page":"220","volume-title":"Proceedings of the 29th Annual ACM Symposium on the Theory of Computing","author":"R. Impagliazzo","year":"1997","unstructured":"Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, pp.\u00a0220\u2013229 (1997)"},{"issue":"4","key":"9368_CR10","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1002\/rsa.3240030402","volume":"3","author":"M. Jerrum","year":"1992","unstructured":"Jerrum, M.: Large cliques elude the metropolis process. Random Struct. Algorithms 3(4), 347\u2013359 (1992)","journal-title":"Random Struct. Algorithms"},{"key":"9368_CR11","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1145\/335305.335314","volume-title":"Proceedings of the Thirty Second Annual ACM Symposium on Theory of Computing","author":"V. Kabanets","year":"2000","unstructured":"Kabanets, V., Cai, J.-Y.: Circuit minimization problem. In: Proceedings of the Thirty Second Annual ACM Symposium on Theory of Computing, Portland, Oregon, May 21\u201323, 2000, pp.\u00a073\u201379. ACM Press, New York (2000)"},{"issue":"5","key":"9368_CR12","doi-asserted-by":"crossref","first-page":"1501","DOI":"10.1137\/S0097539700389652","volume":"31","author":"A. Klivans","year":"2002","unstructured":"Klivans, A., van Melkebeek, D.: Graph nonisomorphism has subexponential size proofs unless the polynomial hierarchy collapses. SIAM J. Comput. 31(5), 1501\u20131526 (2002)","journal-title":"SIAM J. Comput."},{"issue":"2\u20133","key":"9368_CR13","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0166-218X(94)00103-K","volume":"57","author":"L. Kucera","year":"1995","unstructured":"Kucera, L.: Expected complexity of graph partitioning problems. Discrete Appl. Math. 57(2\u20133), 193\u2013212 (1995)","journal-title":"Discrete Appl. Math."},{"key":"9368_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-3860-5","volume-title":"Introduction to Kolmogorov Complexity and Its Applications","author":"M. Li","year":"1993","unstructured":"Li, M., Vitanyi, P.: Introduction to Kolmogorov Complexity and Its Applications. Springer, Berlin (1993)"},{"issue":"1\u20132","key":"9368_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/0400000011","volume":"4","author":"S. Lokam","year":"2009","unstructured":"Lokam, S.: Complexity lower bounds using linear algebra. Found. Trends Theor. Comput. Sci. 4(1\u20132), 1\u2013155 (2009)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"2","key":"9368_CR16","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.: Hardness vs randomness. J. Comput. Syst. Sci. 49(2), 149\u2013167 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9368_CR17","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"A. Razborov","year":"1997","unstructured":"Razborov, A., Rudich, S.: Natural proofs. J. Comput. Syst. Sci. 55(1), 24\u201335 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20133","key":"9368_CR18","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0012-365X(93)E0117-M","volume":"136","author":"J. Spencer","year":"1994","unstructured":"Spencer, J.: From Erdos to algorithms. Discrete Math. 136(1\u20133), 295\u2013307 (1994)","journal-title":"Discrete Math."},{"key":"9368_CR19","unstructured":"Trevisan, L.: Pseudorandomness and combinatorial constructions. Electron. Colloq. Comput. Complex. 13(13) (2006)"},{"key":"9368_CR20","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1145\/1324215.1324225","volume":"38","author":"S. Vadhan","year":"2007","unstructured":"Vadhan, S.: The unified theory of pseudorandomness. ACM SIGAST News 38, 39\u201354 (2007)","journal-title":"ACM SIGAST News"},{"key":"9368_CR21","series-title":"LNCS","first-page":"162","volume-title":"Proceedings of the 6th Symposium on Mathematical Foundations of Computer Science","author":"L.G. Valiant","year":"1977","unstructured":"Valiant, L.G.: Graph-theoretic arguments in low-level complexity. In: Gruska, J. (ed.) Proceedings of the 6th Symposium on Mathematical Foundations of Computer Science, Tatransk\u00e1 Lomnica, Czechoslovakia, September 1977. LNCS, vol.\u00a053, pp.\u00a0162\u2013176. Springer, Berlin (1977)"},{"key":"9368_CR22","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1145\/22145.22196","volume-title":"Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing","author":"L. Valiant","year":"1985","unstructured":"Valiant, L., Vazirani, V.: NP is as easy as detecting unique solutions. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pp.\u00a0458\u2013463 (1985)"},{"key":"9368_CR23","first-page":"80","volume-title":"Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science","author":"A. Yao","year":"1982","unstructured":"Yao, A.: Theory and application of trapdoor functions. In: Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, pp.\u00a080\u201391 (1982)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9368-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-011-9368-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9368-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:54:23Z","timestamp":1558684463000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-011-9368-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11,18]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["9368"],"URL":"https:\/\/doi.org\/10.1007\/s00224-011-9368-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,11,18]]}}}