Title: Lower bounds on the randomized communication complexity
of read-once functions.

Speaker: Nikos Leonardos

Abstract: We prove lower bounds on the randomized two-party
communication complexity of functions that arise from read-once
boolean formulae.

A read-once boolean formula is a formula in propositional logic
with the property that every variable appears exactly once. Such
a formula can be represented by a tree, where the leaves
correspond to variables, and the internal nodes are labeled by
binary connectives. Under certain assumptions, this
representation is unique. Thus, one can define the depth of a
formula as the depth of the tree that represents it.

The complexity of the evaluation of general read-once formulae
has attracted interest mainly in the decision tree model. In the
communication complexity model, many interesting results deal
with specific read-once formulae, such as DISJOINTNESS and
TRIBES. In this paper we use information theory methods to prove
lower bounds that hold for any read-once formula. Our lower
bounds are of the form $n(f)/c^{d(f)}$, where $n(f)$ is the
number of variables and $d(f)$ the depth of the formula, and
they are optimal up to the constant $c$ in the denominator.

Joint work with Michael Saks.

ECCC link:
http://eccc.hpi-web.de/eccc-reports/2009/TR09-010/index.html