Skip to main content

Loading Events

« All Events

  • This event has passed.

Adam Marcus, Princeton University, Ramanujan colorings

March 29, 2019 | 2:00 pm - 3:00 pm EDT

An important construction for (the information theoretic version of) semantic security is a “Biregular Irreducible Function” (BRI). These can be constructed from a complete biregular graph on $2^k d \times 2^k d$ by by coloring it with $2^k$ colors in such a way that each vertex has degree $d$ in each color. Good BRI’s are ones in which each color class forms an expander graph on the underlying vertex set. I will show a result of Wiese and Boche that shows the existence of colorings in which each color class has (spectrally) optimal expansion, which we call a “Ramanujan coloring”. The proof is a clever modification of an earlier result that uses the “method of interlacing polynomials” to understand the expansion of graph lifts, which I will discuss as well.

Details

Date:
March 29, 2019
Time:
2:00 pm - 3:00 pm EDT
Event Category:

Venue