next up previous
Next: References

Budapest Problem Exchange in MathematicsProblem No. XXX Area: Theoretical Computer Science, Complexity Theory, Communication Games

Title: Bounding the randomized communication complexity of Boolean functions in Ltex2html_wrap_inline53 norms

Problem Description: Prove, that there exists a constant c>0 such that the 2-party, probabilistic, common-coin communication complexity of tex2html_wrap_inline57 is at most

Background: For definitions, see [2]. Presently, only a tex2html_wrap_inline61 upper bound is known, where the error-probability is tex2html_wrap_inline63 [2].

For multi-party (deterministic) communication complexity, a poly-logarithmic upper bound is known [1].

The question is motivated by the following conjecture of [3]:

Prove, that there exists a constant c>0 such that the 2-party (deterministic) communication complexity of tex2html_wrap_inline67 is at most
where tex2html_wrap_inline71 is the communication-matrix of function f.

Contact person: Vince Grolmusz (

Posted by: Vince Grolmusz (

Originated from: [2]

Vince Grolmusz
Sun Mar 15 20:45:09 MET 1998