Paul Beame, T. S. Jayram and Atri Rudra

We prove lower bounds
in this model for algorithms that are allowed to have *2-sided error*.
Previously, such lower bounds were shown only for deterministic
and 1-sided error randomized algorithms.
We consider the classical *set disjointness* problem, where
the goal is to decide if the two input sets have an empty intersection.
For this problem, we show a near-linear lower bound on the size of the internal
memory used by a randomized algorithm with 2-sided error that is allowed
to have sub-logarithmic number of passes.
Applications include near-linear lower bounds on
the internal memory for well-known problems in the literature:
(1) approximately counting the number of distinct elements in the input;
(2) approximating the frequency of the mode of an input sequence;
(3) computing the join of two relations; and
(4) deciding if some node of an XML document matches
an XQuery (or XPath) query.

Our results asymptotically improve previously known bounds for any problem even in deterministic and 1-sided error models of computation.

- Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), Pgs 698-698. 2007. [PDF]