I am curious whether these results can be combined with work on "streaming
reductions," as defined by this paper .
But I will focus first on making sure we all understand the basic paper.
In this paper, we consider the problem of private searching on streaming
data, where we can efficiently implement searching for documents under a
secret criteria (such as presence or absence of a hidden combination of
hidden keywords) under various cryptographic assumptions. Our results can
be viewed in a variety of ways: as a generalization of the notion of a
Private Information Retrieval (to the more general queries and to a
streaming environment as well as to public-key program obfuscation); as
positive results on privacy-preserving datamining; and as a delegation of
hidden program computation to other machines.
The paper can be obtained here .
Date
Speaker
Topic and Paper Reference
Sep 14
No Speaker
Sep 21
Robi
I can speak about "Approximating edit distance efficiently". I
plan to present the two sketching algorithms in a paper
by Ziv Bar-Yossef, T.S. Jayram, myself, and Ravi Kumar.
Sep 28
Kamalika
I will follow up
on Robi's talk last week by presenting "Low Distortion Embeddings for Edit
Distances", Ostrovsky and Rabani, STOC 2005. This paper provides an
embedding of the edit distance metric on a hypercube into l_1, with
distortion at most 2^{O(\sqrt{\log d \log \log d})}.
Oct 5
David Molnar
Next week I'll talk about...another paper by R. Ostrovsky! This one is
joint work with William Skeith and considers "private searching on
streaming data." Abstract and link follows.
Private Searching on Streaming Data
Oct 12
Kamalika
Embedding block edit distances into l1 with low distortion
Oct 19
Cancelled
Oct 26
Cancelled
Nov 2
Nov 9
Jittat
Nov 16
Nov 25
Thanksgiving Week!
Dec 2
Dec 9
Dec 16
Finals Week!