Budapest Problem Exchange in Mathematics                    Problem No. 2

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
displaymath59

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
displaymath69
where tex2html_wrap_inline71 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]

References

1
 V. Grolmusz. Harmonic analysis, real approximation, and the communication complexity of boolean functions. In Computing and Combinatorics, Proc. 2nd Ann. Int. Conf.\ COCOON'96. LNCS 1090, pages 142-151, June 1996. To appear in Algorithmica.
2
 V. Grolmusz. On the power of circuits with gates of low ltex2html_wrap_inline53 norms. Theoretical Computer Science A, (188):117-128, 1997. Also appeared as ECCC Report TR95-046; ftp://ftp.eccc.uni- trier.de/pub/eccc/reports/1995/TR95-046.
3
 L. Lovász and M. Saks. Lattices, Möbius functions, and communication complexity. In Proc. 29th Ann. IEEE Symp. Found. Comput. Sci., pages 81-90, 1988.