- On the communication complexity of sparse set disjointness and exists-equal problems

(with Gábor Tardos)

54th Annual Symposium on Foundations of Computer Science (FOCS 2013)

[pdf] [abstract] [arXiv] [bib]We show that the $r$-round communication complexity of the $k$-disjointness problem is precisely $\Theta(k\log^{(r)} k)$ bits. Setting $r=\log^* k$, our upper bound gives an $O(k)$-bits, $\log^* k$-rounds protocol with error probability exponentially small in $k$. This improves the best previous protocol due to Håstad and Wigderson, which ran in $O(\log k)$ rounds and erred with constant probability.

Our lower bound applies even to the simpler task of computing the OR of $k$ independent instances of equality. An important aspect of our work is that the lower bound we get is super-linear in $k$, even though a single instance of equality can be solved with $O(1)$ bits and constant error probability.

- Tight Bounds for Data Stream Algorithms and Communication Problems

(supervisor: Gábor Tardos)

M.Sc. Thesis, SFU, School of Computing Science. September 2011.

[pdf] [bib] - Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems

(with Hossein Jowhari and Gábor Tardos)

30th Symposium on Principles of Database Systems (PODS 2011)

[pdf] [abstract] [arXiv] [bib]We present $L_p$ sampling algorithms using $O(\log^2 n)$ bits of space for $p\in[0,2)$ in the streaming model and show that $\Omega(\log^2 n)$ space is required by any such algorithm.

As an application, we present an $O(\log^2 n)$ space algorithm for finding a duplicate in a stream of length $n+1$ over the alphabet $[n]$, improving on the previous $O(\log^3 n)$ bound due to Gopalan and Radhakrishnan.

- Periodicity in Streams

(with Funda Ergün and Hossein Jowhari)

14th Intl. Workshop on Randomization and Computation (RANDOM 2010)

[pdf] [abstract] [bib]We give an $O(\log^2 n)$ space one pass streaming algorithm that finds the period of a stream, provided the stream is periodic. At the core of this algorithm is a new one pass $O(\log n\log m)$ space pattern matching algorithm for finding occurrences of a length $m$ pattern in a text of size $n$. This algorithm uses similar ideas to Porat and Porat’s algorithm in FOCS 2009 but it does not need an offline pre-processing stage and is simpler.

In the second part, we study distance to $p$-periodicity under the Hamming metric and provide space efficient approximation algorithms.