This research involves constructions of combinatorial objects called Ramanujan graphs that are special types of expander graphs that have a vast number of applications to several areas of computer science and communication science and to many other areas of research (e.g., reliable communication networks, sorting networks, super-concentrators, construction of highly efficient error-correcting "expander codes"). This investigation connects expander graphs to codes, sequences and exponential sums, three fundamental areas of communication science that are already deeply connected, and that already have many important applications in: the correction of errors in transmission and storage of data (e.g. to CD's), fault-tolerant systems, secure data communication, and cryptography.
The investigators have recently introduced notions of projective coset graphs of codes and have constructed Ramanujan graphs and other good expander graphs from codes, sequences and related exponential sums that appear as eigenvalues of these graphs. Research thus far has shown that good codes and sequences lead to good expander graphs in general, and Ramanujan graphs in particular. Also, some exponential sums that appear in the construction of Ramanujan graphs and good expander graphs lead to very good codes and sequences. The investigation involves: i) a vast extension and generalization of the work done so far; ii) construction of Ramanujan graphs and other good expander graphs from algebraic geometric codes, codes over Galois rings, and other classes of codes; iii) practical and feasible applications of these graphs to the research areas mentioned above; and iv) discovery of new areas of applications. In addition, the investigators analyze the highly practical research work of the last fifty years in coding theory, sequence design and related exponential sums for efficient implementation of the proposed schemes.
