All reports by Author Kasper Green Larsen:

__
TR19-055
| 9th April 2019
__

Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo#### Lower Bounds for Oblivious Near-Neighbor Search

__
TR18-109
| 29th May 2018
__

Kasper Green Larsen, Jesper Buus Nielsen#### Yes, There is an Oblivious RAM Lower Bound!

__
TR17-047
| 10th March 2017
__

Kasper Green Larsen, Omri Weinstein, Huacheng Yu#### Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

__
TR12-087
| 4th July 2012
__

Peyman Afshani, Manindra Agrawal, Doerr Benjamin, Winzen Carola, Kasper Green Larsen, Kurt Mehlhorn#### The Deterministic and Randomized Query Complexity of a Simple Guessing Game

Revisions: 1

Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo

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 >>>

Kasper Green Larsen, Jesper Buus Nielsen

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 >>>

Kasper Green Larsen, Omri Weinstein, Huacheng Yu

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 >>>

Peyman Afshani, Manindra Agrawal, Doerr Benjamin, Winzen Carola, Kasper Green Larsen, Kurt Mehlhorn

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 >>>