Abstract
An N-superconcentrator is a directed graph with N input vertices and N output vertices and some intermediate vertices, such that for k=1, 2, ..., N, between any set of k input vertices and any set of k output vertices, there are k vertex disjoint paths. In a depth-twoN-superconcentrator each edge either connects an input vertex to an intermediate vertex or an intermediate vertex to an output vertex. We consider tradeoffs between the number of edges incident on the input vertices and the number of edges incident on the output vertices in a depth-two N-superconcentrator. For an N-superconcentrator G, let a(G) be the average degree of the input vertices and b(G) be the average degree of the output vertices. Assume that b(G) ≥ a(G). We show that there is a constant k 1 > 0 such that
\(a(G)log (\frac{2b(G)}{a(G)}) log b(G) \geq k_1 \cdot log^2 N\).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Pudlák, P.: Superconcentrators of depth 2 and 3; odd levels help (rarely). J. Comput. System Sci. 48, 194–202 (1994)
Dolev, D., Dwork, C., Pippenger, N., Wigderson, A.: Superconcentrators, generalizers and generalized connectors with limited depth. In: Proc. 15th Annual ACM Symposium on Theory of Computing, New York, pp. 42–51 (1983)
Frandsen, G.S., Hansen, J.P., Miltersen, P.B.: Lower bounds for dynamic algebraic problems. Information and Computation 171(2), 333–349 (2002)
Meshulum, R.: A geometric construction of a superconcentrator of depth 2. Theoret. Comput. Sci. 32, 215–219 (1984)
Paul, W.J., Tarjan, R.E., Celoni, J.R.: Space bounds for a game on graphs. In: Proc. 8th Annual ACM Symposium on Theory of Computing, Hershey, PA, May 1976, pp. 149–160 (1976)
Pippenger, N.: Superconcentrators. SIAM J. Comput. 6, 298–304 (1977)
Pippenger, N.: Superconcentrators of depth 2. J. Comput. System Sci. 24, 82–90 (1982)
Pudlák, P.: Communication in bounded depth circuits. Combinatorica 14, 203–216 (1994)
Radhakrishnan, J., Ta-Shma, A.: Bounds for dispersers, extractors and depth-two superconcentrators. SIAM J. Disc. Math. 32, 1570–1585 (2000)
Reif, J.H., Tate, S.R.: On dynamic algorithms for algebraic problems. Journal of Algorithms 22, 347–371 (1997)
Valiant, L.G.: On nonlinear lower bounds in computational complexity. In: Proc. 7th Annual ACM Symposium on Theory of Computing, Albuquerque, NM, May 1975, pp. 45–53 (1975)
Valiant, L.G.: Graph-theoretic properties in computational complexity. J. Comput. System Sci. 13, 278–285 (1976)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dutta, C., Radhakrishnan, J. (2006). Tradeoffs in Depth-Two Superconcentrators. In: Durand, B., Thomas, W. (eds) STACS 2006. STACS 2006. Lecture Notes in Computer Science, vol 3884. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11672142_30
Download citation
DOI: https://doi.org/10.1007/11672142_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32301-3
Online ISBN: 978-3-540-32288-7
eBook Packages: Computer ScienceComputer Science (R0)