## Abstract

We study non-deterministic communication protocols in which no input has too many witnesses. Define n_{k}(f) to be the minimum complexity of a non-deterministic protocol for the function f in which each input has at most k witnesses. We present two different lower bounds for n_{k}(f). Our first result shows that n_{k}(f) is below by Ω(√c(f)/k), where c(f) is the deterministic complexity. Our second results bounds n_{k}(f) by log(rk(M_{f}))/k - 1, where rk(M_{f}) is the rank of the representing matrix of f. As a consequence, it follows that the communication complexity analogue of the Turing-complexity class FewP is equal to the analogue of the class P.

Original language | English (US) |
---|---|

Pages (from-to) | 247-257 |

Number of pages | 11 |

Journal | Journal of Computer and System Sciences |

Volume | 49 |

Issue number | 2 |

DOIs | |

State | Published - Oct 1994 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics