Computer Science/Discrete Mathematics Seminar I

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.