Smaller explicit superconcentrators

By N. Alon, M. Capalbo. ACM-SIAM Symposium on Discrete Algorithms, 2003

413 citations recorded by the source corpus.

Subfields: Discrete Mathematics and Combinatorics, Geometry and Topology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/779adee51d5764d5b6367f09b014d87c7738308f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

In Geometry and Topology

In Statistical and Nonlinear Physics

Citations in the corpus

Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence (2015, methodology): “In order to form an expander graph, we used the Gabber-Galil construction (Gabber and Galil, 1981).”
Undirected ST-connectivity in log-space (2005, background): “Various explicit families of constant-degree expanders, some with optimal tradeoff between degree and expansion, were given in literature (cf. [Mar73, GG81, JM87, AM85, AGM87, LPS88, Mar88, Mor94, RVW01]).”
Random walks in peer-to-peer networks (2004, background): “Consider a constant degree “expander” graph H imposed on these 2 nodes (there are known deterministic constructions of such expander graphs [7] [7].”
Symmetric groups and expander graphs (2005, methodology): “The relative Kazhdan constant of the pair (SL2(Z)⋉ Z (2),Z(2)) was estimated by Burger [6], see also [9], to be:”
Large Networks and Graph Limits (2012, background): “This is not easy to prove; for a proof based on Fourier analysis, see Gabber and Galil [1981].”
Foundations of Cryptography: Volume 1, Basic Tools (2001, neutral): “Explicit constructions of expander graphs have been published [85, 154], as has the specific construction mentioned at the end of Section 2.”
ENTROPY WAVES, THE ZIG-ZAG GRAPH PRODUCT, AND NEW CONSTANT-DEGREE (2004, methodology): “rs in computer science often require explicit families of constant-degree expanders. The ﬁrst such construction was given by Margulis [Mar73], with improvements and simpliﬁcations by Gabber and Galil [GG81], Jimboand Maruoka [JM87], Alon andMilman [AM85], and Alon, Galil, and Milman [AGM87]. Explici”