Nondeterministic communication complexity with help and graph functions

Abstract We present a new method for proving lower bounds on the communication complexity of explicit graph functions in the Number On the Forehead model. For this purpose we define a nondeterministic version of communication complexity with help, extending the model of Babai, Hayes and Kimmel. We prove logarithmic lower bounds for explicit functions in this model, yielding logarithmic lower bounds for some explicit graph functions as well. These lower bounds are in a way complementary to the bounds proved by Beame, David, Pitassi and Woelfel.