Editing Communication complexity (section)

== Nondeterministic communication complexity ==

In nondeterministic communication complexity, Alice and Bob have access to an oracle.  After receiving the oracle's word, the parties communicate to deduce <math>f(x,y)</math>.  The nondeterministic communication complexity is then the maximum over all pairs <math>(x,y)</math> over the sum of number of bits exchanged and the coding length of the oracle word.

Viewed differently, this amounts to covering all 1-entries of the 0/1-matrix by combinatorial 1-rectangles (i.e., non-contiguous, non-convex submatrices, whose entries are all one (see Kushilevitz and Nisan or Dietzfelbinger et al.)).  The nondeterministic communication complexity is the binary logarithm of the ''rectangle covering number'' of the matrix: the minimum number of combinatorial 1-rectangles required to cover all 1-entries of the matrix, without covering any 0-entries.

Nondeterministic communication complexity occurs as a means to obtaining lower bounds for deterministic communication complexity (see Dietzfelbinger et al.), but also in the theory of nonnegative matrices, where it gives a lower bound on the [[Nonnegative rank (linear algebra)|nonnegative rank]] of a nonnegative matrix.<ref>{{Cite journal|author=Yannakakis, M. |title=Expressing combinatorial optimization problems by linear programs|journal=J. Comput. Syst. Sci.|volume=43 |issue=3 |pages=441–466 |year=1991 |doi=10.1016/0022-0000(91)90024-y|doi-access= }}</ref>