# Is it possible to prove stronger bounds for the deterministic communication complexity compared to nondeterministic communication complexity?

Inspired by the questions Nondeterministic communication complexity of set disjointness?, I was wondering about the following:

Is there an example of a function $f$ where the nondeterministic communication complexity $N(f)$ is asymptotically smaller than the deterministic communication complexity $D(f)$.

When $f$ is the Equality problem or the Set Disjointness problem, we seem to have $D(f) = N(f)$ and, as far as I can tell, the common techniques for showing lower bounds for deterministic protocols (fooling sets and the rank method) work just as well for nondeterministic protocols.

Are there any known techniques that yield stronger lower bounds for deterministic protocols compared to nondeterministic protocols?

• I don't think rank gives lower bounds for non-deterministic protocols. For example the negation of the equality function corresponds to a full rank matrix but has a non-deterministic protocol with $\log n$ bits. – Sasho Nikolov Feb 19 '15 at 8:55
• See Kushilevitz/Nisan Example 2.12: this shows that the $k$-disjointness function (where Alice and Bob each receive a $k$-element subset of $[n]$ and have to determine if they are disjoint) achieves a quadratic gap when $k = \log n$. – András Salamon Feb 19 '15 at 10:35

It seems to me that there is some incoherency in the question. What do you mean by better? Are you looking for a function where $N(f) \ll D(f)$ or a function where $D(f) \ll N(f)$?
Deterministic protocols are a special case of nondeterministic protocols, so we always have $N(f) \leq D(f)$.
For examples of functions where $N(f) \ll D(f)$ have a look at the Nisan and Kushilevitz's book.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9066887497901917, "perplexity": 351.1129702031392}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2019-26/segments/1560628001138.93/warc/CC-MAIN-20190627115818-20190627141818-00037.warc.gz"}