Ramanujan bigraphs and applications

Annual Symposium on Foundations of Computer Science, pp. 2088–2096

Abstract

In their seminal paper, Lubotzky, Phillips and Sarnak (LPS) defined the notion of regular Ramanujan graphs and gave a strongly-explicit construction of infinite families of ($p+1$)regular Ramanujan Cayley graphs, for infinitely many primes p. In this paper we extend the work of LPS and its successors to bigraphs (biregular bipartite graphs): we investigate the combinatorial properties of various generalizations of the notion of Ramanujan graphs, define a notion of Cayley bigraphs, and give strongly-explicit constructions of infinite families of ($p^{3}+1, p+1$)-regular Ramanujan Cayley bigraphs, for infinitely many primes p. In addition, we present a pseudorandomness characterization of Ramanujan bigraphs, and a more general notion of biexpanders. We also show that the graphs we construct exhibit the cutoff phenomenon with bounded window size for the mixing time of non-backtracking random walks, and present some other applications, such as optimal unitary gates in quantum computation.

Authors 4

1. Shai Evra

   Hebrew University of Jerusalem

   Affiliation as printed

   Einstein Institute of Mathematics The Hebrew University of Jerusalem,Jerusalem,Israel

2. Brooke Feigon

   The Graduate Center, CUNY · City College of New York · City University of New York

   Affiliation as printed

   CUNY Graduate Center,Department of Mathematics The City College of New York,New York,USA

3. Kathrin Maurischat Aachen Lehrstuhl für Algebra und Darstellungstheorie

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University Aachen,Lehrstuhl für Algebra und Darstellungstheorie,Germany

4. Ori Parzanchevski

   Hebrew University of Jerusalem

   Affiliation as printed

   Einstein Institute of Mathematics The Hebrew University of Jerusalem,Jerusalem,Israel