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]