Talk Title:

Dependent Random Graphs and Multiparty Pointer Jumpin

Abstract:

We initiate a study of a relaxed version of the standard Erdos-Renyi random graph model, where each edge may depend on a few other edges.  We call such graphs *dependent random graphs*  and give tight bounds on the clique and chromatic numbers of such graphs.  Surprisingly, some of the bounds in the standard random graph model continue to hold in this relaxed setting.  For example, the size of the largest clique in a dependent random graph remains roughly log(n)/log(1/p).

As an application, we give a new upper bound on communication complexity of the Multiparty Pointer Jumping (MPJ) problem in the number-on-the-forehead (NOF) model.  NOF communication lies at the current frontier of our understanding of communication complexity, and MPJ is one of the canonical problems in this setting.  Furthermore, sufficiently strong bounds for MPJ would have important consequences for circuit complexity.

No prior knowledge is assumed aside from basic discrete probability.  I hope to motivate both random graphs and the application and demonstrate why NOF communication is an important active research area.

This talk is based on research that is joint work with Mario Sanchez.

Bio:

Joshua Brody received a bachelor’s degree in Mathematics/Computer Science from Carnegie Mellon University, a Master’s Degree in Computer Science from New York University, and a  PhD in Computer Science from Dartmouth College.  Prior to graduate school, he served in the Peace Corps teaching high school mathematics in Burkina Faso, West Africa.  Dr. Brody is currently an Assistant Professor in the Computer Science department at Swarthmore College.  His primary research area is communication complexity.  Additional research interests include several areas of theoretical computer science, including streaming algorithms, property testing, and data structures.