All reports by Author Nikos Leonardos:

__
TR12-099
| 5th August 2012
__

Nikos Leonardos#### An improved lower bound for the randomized decision tree complexity of recursive majority

Revisions: 1

__
TR09-010
| 29th January 2009
__

Nikos Leonardos, Michael Saks#### Lower bounds on the randomized communication complexity of read-once functions

Nikos Leonardos

We prove that the randomized decision tree complexity of the recursive majority-of-three is $\Omega(2.6^d)$, where $d$ is the depth of the recursion. The proof is by a bottom up induction, which is same in spirit as the one in the proof of Saks and Wigderson in their FOCS 1986 paper ... more >>>

Nikos Leonardos, Michael Saks

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 ... more >>>