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.