×

Computation of best possible low degree expanders. (English) Zbl 1126.05093

Summary: We present an algorithm for computing a best possible bipartite cubic expander for a given number of vertices. Such graphs are needed in many applications and are also the basis for many results in theoretical computer science. Known construction methods for expander graphs yield expanders that have a fairly poor expansion compared to the best possible expansion. Our algorithm is based on a lemma which allows to calculate an upper bound for the expansion of cubic bipartite graphs.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)

Software:

GENREG
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blum, M.; Karp, R.; Vornberger, O.; Papadimitriou, C.; Yannakakis, M., The complexity of testing whether a graph is a superconcentrator, Inform. Process. Lett., 13, 164-167 (1981) · Zbl 0482.05059
[2] Gabber, O.; Galil, Z., Explicit constructions of linear-sized superconcentrators, J. Comput. System Sci., 22, 3, 407-420 (1981) · Zbl 0487.05045
[3] O. Goldreich, R. Impagliazzo, L. Levin, R. Venkatesan, D. Zuckerman. Security preserving amplification of hardness. FOCS, 1990, pp. 318-326.; O. Goldreich, R. Impagliazzo, L. Levin, R. Venkatesan, D. Zuckerman. Security preserving amplification of hardness. FOCS, 1990, pp. 318-326.
[4] R. Impagliazzo, A. Wigderson, \(P =\) If \(E\) requires exponential circuits: Derandomizing the XOR lemma, STOC, 1997, pp. 220-229.; R. Impagliazzo, A. Wigderson, \(P =\) If \(E\) requires exponential circuits: Derandomizing the XOR lemma, STOC, 1997, pp. 220-229. · Zbl 0962.68058
[5] I. Köthnig, Expansion 3-regulärer bipartiter Graphen, Studienarbeit, Lehrstuhl für Algorithmen und Komplexität, Institut für Informatik, Humboldt-Universität zu Berlin, 2002.; I. Köthnig, Expansion 3-regulärer bipartiter Graphen, Studienarbeit, Lehrstuhl für Algorithmen und Komplexität, Institut für Informatik, Humboldt-Universität zu Berlin, 2002.
[6] Lubotzky, A.; Phillips, R.; Sarnak, P., Ramanujan graphs, Combinatorica, 8, 261-277 (1988) · Zbl 0661.05035
[7] Margulis, G. A., Explicit constructions of expanders, Problemy Peredaci Informacii, 9, 4, 71-80 (1973) · Zbl 0312.22011
[8] Meringer, M., Fast generation of regular graphs and construction of cages, J. Graph theory, 30, 137-146 (1999) · Zbl 0918.05062
[9] B. Monien, R. Preis, Upper bounds on the bisection width of 3- and 4-regular graphs, in: 26th International Symposium on Mathematical Foundations of Computer Science (MFCS) 2001, Lecture Notes in Computer Science, vol. 2136, Springer, Berlin, 2001, pp. 524-536.; B. Monien, R. Preis, Upper bounds on the bisection width of 3- and 4-regular graphs, in: 26th International Symposium on Mathematical Foundations of Computer Science (MFCS) 2001, Lecture Notes in Computer Science, vol. 2136, Springer, Berlin, 2001, pp. 524-536. · Zbl 0999.68159
[10] Papadimitriou, C. H., Computational Complexity (1994), Addison Wesley · Zbl 0557.68033
[11] M. Pinsker, On the complexity of a concentrator, in: Seventh Annual Teletraffic Conference 318/1-318/4, Stockholm, 1973.; M. Pinsker, On the complexity of a concentrator, in: Seventh Annual Teletraffic Conference 318/1-318/4, Stockholm, 1973.
[12] Pippenger, N., Sorting and selecting in rounds, SIAM J. Comput., 16, 6, 1032-1038 (1987) · Zbl 0654.68068
[13] Pippenger, N.; Yao, A. C., Rearrangeable networks with limited depth, SIAM J. Algebraic Discrete Methods, 3, 411-417 (1982) · Zbl 0493.94017
[14] Reingold, O.; Vadhan, S.; Wigderson, A., Entropy waves, the zig-zag graph product, and new constant-degree expanders, Ann. Math., 155, 157-187 (2002) · Zbl 1008.05101
[15] Sipser, M., Expanders, randomness, or time versus space, J. Comput. System Sci., 36, 3, 379-383 (1988) · Zbl 0652.68050
[16] Sipser, M.; Spielman, D. A., Expander Codes, IEEE Trans. Inform. Theory, 42, 6, part1, 1710-1722 (1996), (Codes and complexity) · Zbl 0943.94543
[17] L.G. Valiant, Graph-theoretic arguments in low-level complexity, Lecture Notes in Computer Science, vol. 53, 1977, pp. 162-176.; L.G. Valiant, Graph-theoretic arguments in low-level complexity, Lecture Notes in Computer Science, vol. 53, 1977, pp. 162-176. · Zbl 0384.68046
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.