Is there a linear space lower bound for streaming set equality? Consider two streams. In each stream one string arrives at a time.  A query asks: Is the set of strings that has arrived so far the same in both streams?


  Is there a linear space randomized lower bound for this problem?


If the sets of strings had been given in advance we could just sort them, remove duplicates, concatenate them in each set and then compute a random fingerprint of each of the two concatenated strings which can then be compared quickly using very little space (although there is of course no benefit as we first created something of linear size).  

In the streaming case, we would need an updatable fingerprint it seems to do something similar.  I suspect this is not possible to do in sublinear space but I don't see a proof yet.
There are both deterministic lower bounds and randomized upper bounds (for a version of the problem where you get check-ins and check-outs in a single stream rather than check-ins in one stream and check-outs in the other, but that makes little difference) in my paper

Space-efficient straggler identification in round-trip data streams via Newton's identitities and invertible Bloom filters.
D. Eppstein, and M. T. Goodrich.
arXiv:0704.3313.
IEEE Trans. Knowledge and Data Engineering 23 (2): 297–306, 2011.
(and WADS 2007).

See also:

What's the difference? Efficient set reconciliation without prior context.
D. Eppstein, M. T. Goodrich, F. Uyeda, and G. Varghese.
Proc. ACM SIGCOMM, Toronto, Canada, 2011.

which is more explicitly about comparing two sets.

In short: you can test whether two multisets (or sets with no repetitions) are the same using only very small space, or more generally find their symmetric difference in space roughly proportional to the size of the difference.

If you really mean sets, where repetitions are allowed, I think the problem may be much harder, though I don't know of a randomized lower bound for it.