2012 | OriginalPaper | Buchkapitel
Erdős-Rényi Sequences and Deterministic Construction of Expanding Cayley Graphs
verfasst von : Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar
Erschienen in: LATIN 2012: Theoretical Informatics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Given a finite group
G
by its multiplication table, we give a deterministic polynomial-time construction of a directed
O
(log|
G
|) degree Cayley expander for
G
. Our construction exploits the connection between rapid mixing random walks and spectral expansion. Our main group-theoretic tool is Erdős-Rényi sequences. We give a similar construction of
O
(log|
G
|) degree undirected Cayley expanders for
G
, which is an alternative proof of Wigderson and Xiao’s derandomization [WX08] of the Alon-Roichman randomized construction.