**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 L norms

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

**Background:** For definitions, see [2]. Presently, only a upper bound is known, where the error-probability is [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 is at most

where is the communication-matrix of function *f*.

**Contact person:** Vince Grolmusz (grolmusz@cs.elte.hu)

**Posted by:** Vince Grolmusz (grolmusz@cs.elte.hu)

**Originated from:** [2]

Sun Mar 15 20:45:09 MET 1998