Nondeterministic communication complexity with help and graph functions
2019
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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
11
References
0
Citations
NaN
KQI