Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > KEVIN YEO:
All reports by Author Kevin Yeo:

TR20-003 | 15th January 2020
Giuseppe Persiano, Kevin Yeo

Tight Static Lower Bounds for Non-Adaptive Data Structures

In this paper, we study the static cell probe complexity of non-adaptive data structures that maintain a subset of $n$ points from a universe consisting of $m=n^{1+\Omega(1)}$ points. A data structure is defined to be non-adaptive when the memory locations that are chosen to be accessed during a query depend ... more >>>


TR19-055 | 9th April 2019
Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo

Lower Bounds for Oblivious Near-Neighbor Search

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


TR18-181 | 30th October 2018
Giuseppe Persiano, Kevin Yeo

Lower Bounds for Differentially Private RAMs

In this work, we study privacy-preserving storage primitives that are suitable for use in data analysis on outsourced databases within the differential privacy framework. The goal in differentially private data analysis is to disclose global properties of a group without compromising any individual’s privacy. Typically, differentially private adversaries only ever ... more >>>




ISSN 1433-8092 | Imprint