2012 | OriginalPaper | Chapter
Erdős-Rényi Sequences and Deterministic Construction of Expanding Cayley Graphs
Authors : Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar
Published in: LATIN 2012: Theoretical Informatics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.