Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Giuseppe Persiano:

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

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