The NOF Communication Complexity of Multiparty Pointer Jumping

Video of this lecture

COMPUTER SCIENCE/DISCRETE MATH I
Topic:The NOF Communication Complexity of Multiparty Pointer Jumping
Speaker:Joshua Brody
Affiliation:Dartmouth College
Date:Monday, December 7
Time/Room:11:15am - 12:15pm/S-101
Video Link:https://video.ias.edu/csdm/nofcomplex

We give new results on the number-on-the-forhead (NOF) communication complexity of the multiparty pointer jumping problem. The origional motivation for this problem comes from circuit complexity. Specifically, there is no explicit function known to lie outside the complexity class ACC0. However, a long line of research in the early 90's showed that a sufficiently strong NOF communication lower bound for a function would place it outside ACC0. Pointer jumping is widely considered to be a strong candidate for such a lower bound. We give a surprising general upper bound to this problem, as well as a tight upper and lower bounds for a restricted class of protocols. Part of this talk was joint work with Amit Chakrabarti.