站内直航

Title: Expander graphs and linear codes

Time: 2015.7.30 9:30

Place: 3224

Abstract:

Expander graphs are highly connected sparse finite graphs. They play an important role in several areas of mathematics, including number theory (e.g. sieves for primes in group orbits), representation theory and geometric embeddings, as well as in computer sciences and digital signal processing, including communications network designs, pseudorandom number generators, compressive sensing, algorithm designs, among others. In this talk, we present a survey of expander graphs (including Ramanujan graphs), their connections to constructions of expander codes (or LDPC codes) that can be decoded by fast algorithms. In particular, we show that expander codes from bipartite graphs with an arbitrary vertex expansion can be decoded in linear time, improving previous work of Sipser and Spielman (1996), Feldman et. al. (2007), and Viderman (2013). This is joint work with Michael Dowling.

Short bio:

Shuhong Gao received his BS (1983) and MS (1986) from Department of Mathematics, Sichuan University, China, and PhD (1993) from Department of Combinatorics and Optimization, University of Waterloo, Canada.  From 1993 to 1995, he was an NSERC Postdoctoral Fellow in Department of Computer Science, University of Toronto, Canada. He joined Clemson University in USA in 1995 as an assistant professor in Mathematical Sciences, and was promoted to associate professor in 2000 (with early tenure) and to full professor in 2002.  Professor Gao has published over 60 papers in the areas of combinatorial design theory, finite fields, coding theory, cryptography, symbolic computation, and computational algebraic geometry.  His research has been supported by grants from NSA, NSF and ONR. He is currently an associate Editor for two international journals: Finite Fields and Their Applications, and Applicable Algebra in Engineering, Communication and Computing.