{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:25:18Z","timestamp":1775053518014,"version":"3.50.1"},"reference-count":32,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T00:00:00Z","timestamp":1441065600000},"content-version":"tdm","delay-in-days":5722,"URL":"http:\/\/doi.wiley.com\/10.1002\/tdm_license_1.1"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct. Alg."],"published-print":{"date-parts":[[2000,8]]},"DOI":"10.1002\/1098-2418(200008)17:1<64::aid-rsa5>3.0.co;2-3","type":"journal-article","created":{"date-parts":[[2002,9,10]],"date-time":"2002-09-10T18:19:05Z","timestamp":1031681945000},"page":"64-77","source":"Crossref","is-referenced-by-count":5,"title":["Construction of expanders and superconcentrators using Kolmogorov complexity"],"prefix":"10.1002","volume":"17","author":[{"given":"Uwe","family":"Sch\ufffdning","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2000]]},"reference":[{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB1","author":"Ajtai","year":"1983","unstructured":"and An O(n log n) sorting network, Proc 15th Annual ACM Symp on Theory of Computing, 1983, pp. 1-9."},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB2","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02579166","volume":"6","author":"Alon","year":"1986","journal-title":"Combinatorica"},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB3","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0196-6774(87)90014-9","volume":"8","author":"Alon","year":"1987","journal-title":"J Alg"},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB4","author":"Alon","year":"1984","unstructured":"and Eigenvalues, expanders and superconcentrators, Proc 25th IEEE Symp on Foundations of Computer Science, 1984, pp. 320-322."},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB5","first-page":"206","volume":"17","author":"Bassalygo","year":"1981","journal-title":"Prob Inform Transmission"},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB6","author":"Beame","year":"1996","unstructured":"and Simplified and improved resolution lower bounds, Proc 37th IEEE Symp on Foundations of Computer Science, 1996, pp. 274-282."},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB7","series-title":"Graph theory","author":"Bondy","year":"1976","unstructured":"and Graph theory with applications, Macmillan, New York, 1976."},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB8","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1002\/j.1538-7305.1979.tb02972.x","volume":"58","author":"Chung","year":"1979","journal-title":"Bell Syst Tech J"},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB9","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1090\/psapm\/044\/1141922","volume-title":"Probabilistic Combinatorics and Applications","volume":"44","author":"Chung","year":"1991","unstructured":"? Constructing random-like graphs,? Probabilistic Combinatorics and Applications, Proceedings of Symposia in Applied Mathematics, Vol. 44, (Editor), American Math. Society, Providence, RI, 1991, pp. 21-25."},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB10","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1145\/48014.48016","volume":"35","author":"Chv\u00e1tal","year":"1988","journal-title":"J Assoc Comput Mach"},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB11","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","volume":"22","author":"Gabber","year":"1981","journal-title":"J Comput Syst Sci"},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB12","author":"Kahale","year":"1993","unstructured":"Expander graphs, Ph.D. thesis, MIT, 1993."},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB13","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"An introduction to Kolmogorov complexity and its applications","author":"Li","year":"1997","unstructured":"and An introduction to Kolmogorov complexity and its applications, 2nd ed., Springer-Verlag, Berlin, 1997."},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB14","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"Lubotzky","year":"1988","journal-title":"Combinatorica"},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB15","first-page":"71","volume":"9","author":"Margulis","year":"1973","journal-title":"Probl Inform Transmission"},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB16","author":"Morgenstern","year":"1991","unstructured":"Explicit construction of natural bounded concentrators, Proc 32nd IEEE Symp on Foundations of Computer Science, 1991, pp. 392-397."},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB17","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized algorithms","author":"Motwani","year":"1995","unstructured":"and Randomized algorithms, Cambridge University Press, Cambridge, UK, 1995."},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB18","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BF01683275","volume":"10","author":"Paul","year":"1977","journal-title":"Math Syst Theory"},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB19","author":"Pinsker","year":"1973","unstructured":"On the complexity of a concentrator, 7th Intl Teletraffic Conf, 1973, 318\/1-318\/4."},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB20","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1137\/0206022","volume":"6","author":"Pippenger","year":"1977","journal-title":"SIAM J Comput"},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB21","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1137\/0207040","volume":"7","author":"Pippenger","year":"1978","journal-title":"SIAM J Comput"},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB22","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0890-5401(87)90023-X","volume":"74","author":"Santha","year":"1987","journal-title":"Inform Computat"},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB23","series-title":"Lecture Notes","first-page":"110","volume-title":"Proc Mathematical Foundations of Computer Science","volume":"1295","author":"Sch\u00f6ning","year":"1997","unstructured":"Resolution proofs, exponential lower bounds, and Kolmogorov complexity, Proc Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 1295, Springer, Berlin, 1997, pp. 110-116."},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB24","series-title":"Lecture Notes","first-page":"121","volume-title":"Proc Symp Theoretical Aspects of Computer Science","volume":"166","author":"Shamir","year":"1984","unstructured":"From expanders to better superconcentrators without cascading, Proc Symp Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 166, Springer-Verlag, Berlin, 1984, pp. 121-128."},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB25","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/0022-0000(88)90035-9","volume":"36","author":"Sipser","year":"1988","journal-title":"J Comput Syst Sci"},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB26","author":"Sipser","year":"1994","unstructured":"and Expander codes. Proc 35th IEEE Symp Foundations of Computer Science, 1994, pp. 566-576."},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB27","author":"Spielman","year":"1995","unstructured":"Linear-time encodable and decodable error-correcting codes, Proc 27th Annual ACM Symp on Theory of Computing, 1995."},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB28","doi-asserted-by":"crossref","first-page":"1119","DOI":"10.1109\/TC.1978.1675014","volume":"27","author":"Thompson","year":"1978","journal-title":"IEEE Trans Comput"},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB29","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/7531.8928","volume":"34","author":"Urquhart","year":"1987","journal-title":"J ACM"},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB30","author":"Valiant","year":"1975","unstructured":"On nonlinear lower bounds in computational complexity, Proc 7th Annual ACM Symp on Theory of Computing, 1975, pp. 45-53."},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB31","volume-title":"Codes and cryptography","author":"Welsh","year":"1988","unstructured":"Codes and cryptography, Oxford University Press, London, 1988."},{"key":"10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3-BIB32","author":"Wigderson","year":"1993","unstructured":"and Expanders that beat the eigenvalue bound: explicit construction and application, Proc 25th Annual ACM Symp on Theory of Computing, 1993, pp. 245-251."}],"container-title":["Random Structures and Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2F1098-2418(200008)17:1%3C64::AID-RSA5%3E3.0.CO;2-3","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full\/10.1002\/1098-2418(200008)17:1%3C64::AID-RSA5%3E3.0.CO;2-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,1]],"date-time":"2021-07-01T03:04:12Z","timestamp":1625108652000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/1098-2418(200008)17:1<64::AID-RSA5>3.0.CO;2-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2000,8]]}},"URL":"https:\/\/doi.org\/10.1002\/1098-2418(200008)17:1<64::aid-rsa5>3.0.co;2-3","relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000]]}}}