×

Construction of expanders and superconcentrators using Kolmogorov complexity. (English) Zbl 0953.68065

Summary: We show the existence of various versions of expander graphs using Kolmogorov complexity. This method seems superior to the usual probabilistic construction. It turns out that the best known bounds on the size of expanders and superconcentrators can be attained based on this method. In the case of (acyclic) superconcentrators we attain a density of about 34 edges/vertices. Furthermore, related graph properties are reviewed, like magnification, edge-magnification, and isolation, and we develop bounds based on the Kolmogorov approach.

MSC:

68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] and An O(n log n) sorting network, Proc 15th Annual ACM Symp on Theory of Computing, 1983, pp. 1-9.
[2] Alon, Combinatorica 6 pp 83– (1986) · Zbl 0661.05053 · doi:10.1007/BF02579166
[3] Alon, J Alg 8 pp 337– (1987) · Zbl 0641.68102 · doi:10.1016/0196-6774(87)90014-9
[4] and Eigenvalues, expanders and superconcentrators, Proc 25th IEEE Symp on Foundations of Computer Science, 1984, pp. 320-322.
[5] Bassalygo, Prob Inform Transmission 17 pp 206– (1981)
[6] and Simplified and improved resolution lower bounds, Proc 37th IEEE Symp on Foundations of Computer Science, 1996, pp. 274-282.
[7] and Graph theory with applications, Macmillan, New York, 1976.
[8] Chung, Bell Syst Tech J 58 pp 850– (1979) · doi:10.1002/j.1538-7305.1979.tb02972.x
[9] ? 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. · Zbl 0753.05060 · doi:10.1090/psapm/044/1141922
[10] Chvátal, J Assoc Comput Mach 35 pp 759– (1988) · Zbl 0712.03008 · doi:10.1145/48014.48016
[11] Gabber, J Comput Syst Sci 22 pp 407– (1981) · Zbl 0487.05045 · doi:10.1016/0022-0000(81)90040-4
[12] Expander graphs, Ph.D. thesis, MIT, 1993.
[13] and An introduction to Kolmogorov complexity and its applications, 2nd ed., Springer-Verlag, Berlin, 1997. · Zbl 0866.68051 · doi:10.1007/978-1-4757-2606-0
[14] Lubotzky, Combinatorica 8 pp 261– (1988) · Zbl 0661.05035 · doi:10.1007/BF02126799
[15] Margulis, Probl Inform Transmission 9 pp 71– (1973)
[16] Explicit construction of natural bounded concentrators, Proc 32nd IEEE Symp on Foundations of Computer Science, 1991, pp. 392-397.
[17] and Randomized algorithms, Cambridge University Press, Cambridge, UK, 1995. · doi:10.1017/CBO9780511814075
[18] Paul, Math Syst Theory 10 pp 239– (1977) · Zbl 0366.90150 · doi:10.1007/BF01683275
[19] On the complexity of a concentrator, 7th Intl Teletraffic Conf, 1973, 318/1-318/4.
[20] Pippenger, SIAM J Comput 6 pp 298– (1977) · Zbl 0361.05035 · doi:10.1137/0206022
[21] Pippenger, SIAM J Comput 7 pp 510– (1978) · Zbl 0385.05036 · doi:10.1137/0207040
[22] Santha, Inform Computat 74 pp 241– (1987) · Zbl 0629.68047 · doi:10.1016/0890-5401(87)90023-X
[23] 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. · Zbl 0976.03063
[24] 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. · Zbl 0543.68049
[25] Sipser, J Comput Syst Sci 36 pp 379– (1988) · Zbl 0652.68050 · doi:10.1016/0022-0000(88)90035-9
[26] and Expander codes. Proc 35th IEEE Symp Foundations of Computer Science, 1994, pp. 566-576.
[27] Linear-time encodable and decodable error-correcting codes, Proc 27th Annual ACM Symp on Theory of Computing, 1995. · Zbl 1058.94525
[28] Thompson, IEEE Trans Comput 27 pp 1119– (1978) · Zbl 0385.94034 · doi:10.1109/TC.1978.1675014
[29] Urquhart, J ACM 34 pp 23– (1987) · Zbl 0639.68093 · doi:10.1145/7531.8928
[30] On nonlinear lower bounds in computational complexity, Proc 7th Annual ACM Symp on Theory of Computing, 1975, pp. 45-53.
[31] Codes and cryptography, Oxford University Press, London, 1988. · Zbl 0678.94003
[32] and Expanders that beat the eigenvalue bound: explicit construction and application, Proc 25th Annual ACM Symp on Theory of Computing, 1993, pp. 245-251. · Zbl 1310.68168
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.