We study several variants of a combinatorial game which is based on Cantor's diagonal argument. The game is between two players called Kronecker and Cantor. The names of the players are motivated by the known fact that Leopold Kronecker did not appreciate Georg Cantor's arguments about the infinite, and even ... more >>>

We prove an $\Omega(d \lg n/ (\lg\lg n)^2)$ lower bound on the dynamic cell-probe complexity of statistically $\mathit{oblivious}$ approximate-near-neighbor search (ANN) over the $d$-dimensional Hamming cube. For the natural setting of $d = \Theta(\log n)$, our result implies an $\tilde{\Omega}(\lg^2 n)$ lower bound, which is a quadratic improvement over the ... more >>>

An Oblivious RAM (ORAM) introduced by Goldreich and Ostrovsky
[JACM'96] is a (possibly randomized) RAM, for which the memory access
pattern reveals no information about the operations
performed. The main performance metric of an ORAM is the bandwidth
overhead, i.e., the multiplicative factor extra memory blocks that must be
accessed ... more >>>

This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic \emph{boolean} (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds.

We introduce a new method for proving dynamic cell probe lower bounds and use it to prove a $\tilde{\Omega}(\log^{1.5} ... more >>>

We study the $\leadingones$ game, a Mastermind-type guessing game first
regarded as a test case in the complexity theory of randomized search
heuristics. The first player, Carole, secretly chooses a string $z \in \{0,1\}^n$ and a
permutation $\pi$ of $[n]$.
The goal of the second player, Paul, is to ... more >>>