Events Calendar

PhD Defense - Lian Liu

PhD Candidate: Lian Liu

Committee: Ming-Deh Huang (CS, chair), Sheldon Ross (ISE), Shang-Hua Teng (CS)

Title: Expander Cayley Graphs over Finite Strings and Pseudorandomness

Time: March 9 (Thursday) 2:00 - 3:30 pm.

Room: SAL 322 (i.e. the conference room on the 3rd floor of SAL)


Abstract:

We present an explicit construction of expander Cayley graphs over the direct sum of multiple copies of Z/pZ, where p is a prime number. So far as we know, our work is the first expander Cayley graph construction over such groups. Our construction consists of two phases. In the first phase, we consider Cayley graphs over the multiplicative groups of algebras over finite fields. We prove that for some well-chosen small generating sets which can be computed in polynomial time, the induced Cayley graphs are expanding. In the second phase, we construct an new Cayley graph by projecting the graph created in the first phase onto a direct component of the underlying group. We showed that the component on which the graph is projected is isomorphic to the direct sum of multiple copies of Z/pZ, and the resulting Cayley graph is a good expander. Interestingly, we found that many expander graphs whose degrees are not of any special forms can be explicitly constructed under this framework, which could be regarded as a tiny progress towards the open problem of constructing infinite families of Ramanujan graphs of every degree.

An special case of particular interest is when p equals 2. In this situation, the vertices of such a graph naturally correspond to bit strings of a fixed length, and each edge represents a transition between two bit strings under standard exclusive-or operation. As an application, we then propose a simple pseudorandom generator based on random walks on the graph. An important question is whether our pseudorandom generator is indistinguishable from a truly random source under probabilistic polynomial time attacks, which, however, remains open. In fact, constructing a secure and efficient pseudorandom generator has been an open problem since the birth of modern cryptography, whose solution may lead to huge breakthroughs in computer science. Therefore, our goal here is not addressing this problem, even partially. Instead, along with our discussion, we demonstrate that our expander Cayley graphs have some appealing features that all previous constructions do not have. These new features might bring a lot of potential topics for future research.

Location: Henry Salvatori Computer Science Center (SAL) - 322

Audiences: Everyone Is Invited

Contact: Lizsl De Leon