Our computational model is a random access machine with $n$ read only input registers each containing $ c \log n$ bits of information and a read and write memory. We measure the time by the number of accesses to the input registers. We show that for all $k$ there is ... more >>>

Alice and Bob want to know if two strings of length $n$ are almost equal. That is, do they differ on at most $a$ bits? Let $0\le a\le n-1$. We show that any deterministic protocol, as well as any error-free quantum protocol ($C^*$ version), for this problem requires at least ... more >>>

The Gap-Hamming-Distance problem arose in the context of proving space lower bounds for a number of key problems in the data stream model. In this problem, Alice and Bob have to decide whether the Hamming distance between their $n$-bit input strings is large (i.e., at least $n/2 + \sqrt n$) ... more >>>