Talk abstract:

New Constructions of Ramanujan Graphs and Good Expander Graphs from Codes, Exponential Sums and Sequences

Heeralal Janwa
Department of Mathematics and Computer Science
University of Puerto Rico
hjanwa@rrpac.upr.clu.edu

Joint work with O. Moreno, Director of Gauss Research Laboratory, Department of Mathematics and Computer Science, University of Puerto Rico.

Expander graphs are basic building blocks in the design of networks (sorting, pebbling, non-blocking, linear-sized tolerant, switching,...- networks) (e.g. construction of the famous AKS O(n log n) optimal sequential sorting network and c . logn optimal parallel sorting network) and superconcentrators. Recently they have found applications in constructing linear time encodable and decodable codes and in some other coding theoretic components in the near future high performance computer architecture. Such graphs have vast number of applications to other areas of computer and communication sciences and to many other disciplines.

We have recently introduced projective coset graphs of linear codes whose eigenvalues and expansion coefficients are expressed in terms of exponential sums that naturally occur in coding theory and in the design of sequences and building efficient cryptosystems (three fundamental areas of paramount importance in Computer and Communication Sciences). These projective coset graphs have helped us construct Ramanujan graphs and other good expander graphs that have highly desirable properties for practical applications.

Back to Codes, Systems and Graphical Models