We study interactive proofs with sublinear-time verifiers. These proof systems can be used to ensure approximate correctness for the results of computations delegated to an untrusted server. Following the literature on property testing, we seek proof systems where with high probability the verifier accepts every input in the language, and rejects every input that is far from the language. The verifier's query complexity (and computation complexity), as well as the communication, should all be sublinear. We call such a proof system an Interactive Proof of Proximity (IPP). On the positive side, our main result is that all languages in NC have Interactive Proofs of Proximity with roughly √n query and communication and complexities, and polylog(n) communication rounds. This is achieved by identifying a natural language, membership in an affine subspace (for a structured class of subspaces), that is complete for constructing interactive proofs of proximity, and providing efficient protocols for it. In building an IPP for this complete language, we show a tradeoff between the query and communication complexity and the number of rounds. For example, we give a 2-round protocol with roughly n3/4 queries and communication. On the negative side, we show that there exist natural languages in NC1, for which the sum of queries and communication in any constant-round interactive proof of proximity must be polynomially related to n. In particular, for any 2-round protocol, the sum of queries and communication must be at least ~Ω(√n). Finally, we construct much better IPPs for specific functions, such as bipartiteness on random or well-mixing graphs, and the majority function. The query complexities of these protocols are provably better (by exponential or polynomial factors) than what is possible in the standard property testing model, i.e. without a prover.

%B Proceedings of the 45th annual ACM symposium on Symposium on theory of computing %I ACM %C Palo Alto, California, USA %P 793-802 %@ 978-1-4503-2029-0 %G eng %U http://dx.doi.org/10.1145/2488608.2488709 %1 2488709 %R 10.1145/2488608.2488709 %0 Unpublished Work %D 2013 %T Matching Known Patients to Health Records in Washington State Data %A Sweeney, Latanya %B Data Privacy Lab, IQSS, Harvard University %8 06/01/2013 %G eng %U http://thedatamap.org/risks.html %0 Book Section %B Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques %D 2013 %T Private Learning and Sanitization: Pure vs. Approximate Differential Privacy %A Amos Beimel %A Kobbi Nissim %A Uri Stemmer %A Raghavendra, Prasad %A Raskhodnikova, Sofya %A Jansen, Klaus %A Rolim, JoséD.P. %K differential privacy %K Private Learning %K Sanitization %B Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques %S Lecture Notes in Computer Science %I Springer Berlin Heidelberg %V 8096 %P 363-378 %@ 978-3-642-40327-9 %G eng %U http://dx.doi.org/10.1007/978-3-642-40328-6_26 %R 10.1007/978-3-642-40328-6_26 %0 Journal Article %J JAMA %D 2013 %T Putting Health IT on the Path to Success %A Sweeney, Latanya %A Yasnoff, William A. %A Shortliffe, Edward H. %X The promise of health information technology (HIT) is comprehensive electronic patient records when and where needed, leading to improved quality of care at reduced cost. However, physician experience and other available evidence suggest that this promise is largely unfulfilled. Serious flaws in current approaches to health information exchanges: (1) complex and expensive; (2) prone to error and insecurity; (3) increase liability; (4) not financially sustainable; (5) unable to protect privacy; (6) unable to ensure stakeholder cooperation; and, (7) unable to facilitate robust data sharing. The good news is that personal health record banks pose a viable alternative that is: (a) simpler; (b) scalable; (c) less expensive; (d) more secure; (e) community oriented to ensure stakeholder participation; and, (e) capable of providing the most comprehensive records. The idea of patient controlled records is not new, but what is new is how personally controlled records can help achieve the HIT vision. %B JAMA %V 309 %P 989-990 %G eng %U http://dx.doi.org/10.1001/jama.2013.1474 %N 10 %0 Unpublished Work %D 2013 %T Survey of Publicly Available State Health Databases %A Hooley, Sean %A Sweeney, Latanya %B Data Privacy Lab, IQSS, Harvard University %8 06/01/2013 %G eng %U http://thedatamap.org/states.html %0 Conference Paper %B Proceedings of the fourteenth ACM conference on Electronic commerce %D 2013 %T Truthful mechanisms for agents that value privacy %A Yiling Chen %A Stephen Chong %A Ian A. Kash %A Tal Moran %A Salil Vadhan %X Recent work has constructed economic mechanisms that are both truthful and differentially private. In these mechanisms, privacy is treated separately from the truthfulness; it is not incorporated in players' utility functions (and doing so has been shown to lead to non-truthfulness in some cases). In this work, we propose a new, general way of modelling privacy in players' utility functions. Specifically, we only assume that if an outcome o has the property that any report of player i would have led to o with approximately the same probability, then o has small privacy cost to player i. We give three mechanisms that are truthful with respect to our modelling of privacy: for an election between two candidates, for a discrete version of the facility location problem, and for a general social choice problem with discrete utilities (via a VCG-like mechanism). As the number n of players increases, the social welfare achieved by our mechanisms approaches optimal (as a fraction of n). %B Proceedings of the fourteenth ACM conference on Electronic commerce %I ACM %C Philadelphia, Pennsylvania, USA %P 215-232 %@ 978-1-4503-1962-1 %G eng %U http://dx.doi.org/10.1145/2482540.2482549 %1 2482549 %R 10.1145/2482540.2482549