Differentially Private Approximation Algorithms (2009)
Gupta, Anupam, Ligett, Katrina, McSherry, Frank, Roth, Aaron, Talwar, Kunal
Consider the following problem: given a metric space, some of whose points are "clients", open a set of at most $k$ facilities to minimize the average distance from the clients to these facilities....
Shuchi Chawla, Cynthia Dwork, Frank Mcsherry, Adam Smith, Hoeteck Wee, Larry Joseph Stockmeyer
Abstract. We initiate a theoretical study of the census problem. Informally, in a census individual respondents give private information to a trusted party (the census bureau), who publishes a...
English Only, Prepared Cynthia Dwork, Frank Mcsherry, Kunal Talwar, Cynthia Dwork, Frank Mcsherry, ...
Abstract. We report on a result of Barak et al. on a privacy-preserving technology for release of mutually consistent multi-way marginals [1]. The result ensures differential privacy, a...
Dimitris Achlioptas, Frank Mcsherry, Bernhard Schölkopf
We propose randomized techniques for speeding up Kernel Principal Component Analysis on three levels: sampling and quantization of the Gram matrix in training, randomized rounding in evaluating the...
Dimitris Achlioptas, Frank Mcsherry
We consider the problem of learning mixtures of distributions via spectral methods and derive a tight characterization of when such methods are useful. Specifically, given a mixture-sample, let µ i,...
Dimitris Achlioptas, Frank Mcsherry
Given a matrix A, it is often desirable to find a good approximation to A that has low rank. We introduce a simple technique for accelerating the computation of such approximations when A has strong...
A COOL AND PRACTICAL ALTERNATIVE TO TRADITIONAL HASH (2008)
Ulfar Erlingsson, Mark Manasse, Frank Mcsherry
Recent advances in the theoretical literature have proposed interesting modifications to traditional hash tables. The authors of these papers propose hash tables which a) have a guaranteed constant...
ABSTRACT A Decentralized Algorithm for Spectral Analysis (2008)
In many large network settings, such as computer networks, social networks, or hyperlinked text documents, much information can be obtained from the network’s spectral properties. However,...
Dimitris Achlioptas, Frank Mcsherry, Bernhard Schölkopf
We propose randomized techniques for speeding up Kernel Principal Component Analysis on three levels: sampling and quantization of the Gram matrix in training, randomized rounding in evaluating the...
On Spectral Learning of Mixtures of Distributions (2008)
Dimitris Achlioptas, Frank Mcsherry
We consider the problem of learning mixtures of distributions via spectral methods and derive a tight characterization of when such methods are useful. Specifically, given a mixture-sample, let i , C...
Abstract. The Information Retrieval community uses a variety of performance measures to evaluate the effectiveness of scoring functions. In this paper, we show how to adapt six popular measures —...
--- William Shakespeare, Loves Labours Lost. Act i. Sc. 1. (2007)
Dimitris Achlioptas, Anna R. Karlin, Frank Mcsherry
Small have continual plodders ever won save base authority from others books.
--- William Shakespeare, Loves Labours Lost. Act i. Sc. 1. (2007)
Dimitris Achlioptas, Anna R. Karlin, Frank Mcsherry
Small have continual plodders ever won save base authority from others books.
Mechanism design via differential privacy (2007)
We study the role that privacy-preserving algorithms, which prevent the leakage of specific information about participants, can play in the design of mechanisms for strategic agents, which must...
Calibrating noise to sensitivity in private data analysis (2006)
Cynthia Dwork, Frank Mcsherry, Kobbi Nissim, Adam Smith
Abstract. We continue a line of research initiated in [10, 11] on privacypreserving statistical databases. Consider a trusted server that holds a database of sensitive information. Given a query...
Calibrating noise to sensitivity in private data analysis (2006)
Cynthia Dwork, Frank Mcsherry, Kobbi Nissim, Adam Smith
Abstract. We continue a line of research initiated in [10, 11] on privacypreserving statistical databases. Consider a trusted server that holds a database of sensitive information. Given a query...
Calibrating noise to sensitivity in private data analysis (2006)
Cynthia Dwork, Frank Mcsherry, Kobbi Nissim, Adam Smith
Abstract. We continue a line of research initiated in [10, 11] on privacypreserving statistical databases. Consider a trusted server that holds a database of sensitive information. Given a query...
Our Data, Ourselves: Privacy via Distributed Noise Generation (2006)
Cynthia Dwork, Krishnaram Kenthapadi, Frank Mcsherry, Moni Naor
Abstract. In this work we provide efficient distributed protocols for generating shares of random noise, secure against malicious participants. The purpose of the noise generation is to create a...
Our Data, Ourselves: Privacy via Distributed Noise Generation (2006)
Cynthia Dwork, Krishnaram Kenthapadi, Frank Mcsherry, Moni Naor
Abstract. In this work we provide efficient distributed protocols for generating shares of random noise, secure against malicious participants. The purpose of the noise generation is to create a...
Our Data, Ourselves: Privacy via Distributed Noise Generation (2006)
Cynthia Dwork, Krishnaram Kenthapadi, Frank Mcsherry, Ilya Mironov, Moni Naor
Abstract. In this work we provide efficient distributed protocols for generating shares of random noise, secure against malicious participants. The purpose of the noise generation is to create a...
A Uniform Approach to Accelerated PageRank Computation (2005)
In this note we consider a simple reformulation of the traditional power iteration algorithm for computing the stationary distribution of a Markov chain. Rather than communicate their current...
A First Look at Peer-to-Peer Worms: Threats and Defenses (2005)
Lidong Zhou, Lintao Zhang, Frank Mcsherry, Nicole Immorlica, Manuel Costa, Steve Chien
Peer-to-peer (P2P) worms exploit common vulnerabilities in member hosts of a P2P network and spread topologically in the P2P network, a potentially more effective strategy than random scanning for...
Practical privacy: The SuLQ framework (2005)
Avrim Blum, Cynthia Dwork, Frank Mcsherry, Kobbi Nissim
Abstract. We consider a statistical database in which a trusted administrator introduces noise to the query responses with the goal of maintaining privacy of individual database entries. In such a...
Toward privacy in public databases (2005)
Shuchi Chawla, Cynthia Dwork, Frank Mcsherry, Adam Smith, Larry Joseph Stockmeyer
Abstract. We initiate a theoretical study of the census problem. Informally, in a census individual respondents give private information to a trusted party (the census bureau), who publishes a...
On the Utility of Privacy-Preserving Histograms (2005)
Shuchi Chawla, Cynthia Dwork, Frank Mcsherry, Kunal Talwar
In a census, individual respondents give private information to a trusted party (the census bureau), who publishes a sanitized version of the data. There are two fundamentally conflicting...
Spectral analysis of random Graphs with skewed degree distributions (2004)
Anirban Dasgupta, John E. Hopcroft, Frank Mcsherry
We extend spectral methods to random graphs with skewed degree distributions through a degree based normalization closely connected to the normalized Laplacian. The normalization is based on...
Frank Mcsherry, Frank Mcsherry, Anna Karlin, Dimitris Achlioptas, Paul Beame, Anna Karlin, ...
Reading Committee: Date: and that any and all revisions required by the final examining committee have been made.
Sampling techniques for kernel methods (2002)
Dimitris Achlioptas, Frank Mcsherry, Bernhard Sch Olkopf
We propose randomized techniques for speeding up Kernel Principal Component Analysis on three levels: sampling and quantization of the Gram matrix in training, randomized rounding in evaluating the...
Sampling techniques for kernel methods (2002)
Dimitris Achlioptas, Frank Mcsherry, Bernhard Sch Olkopf
We propose randomized techniques for speeding up Kernel Principal Component Analysis on three levels: sampling and quantization of the Gram matrix in training, randomized rounding in evaluating the...
Sampling techniques for kernel methods (2002)
Correspondence Frank Mcsherry, Dimitris Achlioptas, Frank Mcsherry, Bernhard Sch Olkopf
We propose sampling methods for speeding up kernel techniques on three levels. We sparsify the Gram matrix, the kernel expansion, and, for a class of commonly used kernels, we propose a sampling...
the World Wide Web. comment, Science, 287:2115a, 2000. (2001)
Webgraph Papers, Daniel M. Abrams, Dimitris Achlioptas, Amos Fiat, Anna R. Karlin, Frank Mcsherry, ...
In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 171–180, 2000. [12] William Aiello, Fan R. K. Chung, and Linyuan Lu. Random evolution
Spectral analysis of data (2001)
Yossi Azar, Amos Fiat, Anna R. Karlin, Frank Mcsherry, Jared Saia
Every action must be due to one or other of seven causes: chance, nature, compulsion, habit, reasoning, anger, or appetite.
Spectral Analysis of Data (2001)
Yossi Azar, Amos Fiat, Anna R. Karlin, Frank Mcsherry, Jared Saia
Experimental evidence suggests that spectral techniques are valuable for a wide range of applications. A partial list of such applications include (i) semantic analysis of documents used to cluster...
Web search via hub synthesis (2001)
Dimitris Achlioptas, Amos Fiat, Anna R. Karlin, Frank Mcsherry
Small have continual plodders ever won save base authority from others books. — William Shakespeare, Loves Labours Lost. Act i. Sc. 1. They define themselves in terms of what they oppose. —...
The Performance of Ad Hoc Networking Protocols in Highly Mobile Environments (2000)
Frank Mcsherry, Gerome Miklau, Don Patterson, Steve Swanson, Prof David Wetherall
Ad hoc networking allows hosts to communicate without the benefit of fixed infrastructure. Adaptive routing is of paramount importance in any ad hoc network since routes can change very frequently....