Nondeterministic Communication Complexity with Help and Graph Functions

10/25/2017
by   Adi Shraibman, et al.
0

We define nondeterministic communication complexity in the model of communication complexity with help of Babai, Hayes and Kimmel. We use it to prove logarithmic lower bounds on the NOF communication complexity of explicit graph functions, which are complementary to the bounds proved by Beame, David, Pitassi and Woelfel.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset