Person:
Thaler, Justin

Profile Picture

Email Address

AA Acceptance Date

Birth Date

Research Projects

Organizational Units

Job Title

Last Name

Thaler

First Name

Justin

Name

Thaler, Justin

Filters

2012 - 20132

Settings

Author's Publications: search.filters.isAuthorOfPublication.6fa82f80-7564-4049-a13c-88d1ea420922

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    Publication
    Practical Verified Computation with Streaming Interactive Proofs
    (2013-10-14) Thaler, Justin; Mitzenmacher, Michael D.; Mitzenmacher, Michael; Seltzer, Margo; Vadhan, Salil
    As the cloud computing paradigm has gained prominence, the need for verifiable computation has grown urgent. Protocols for verifiable computation enable a weak client to outsource difficult computations to a powerful, but untrusted, server. These protocols provide the client with a (probabilistic) guarantee that the server performed the requested computations correctly, without requiring the client to perform the computations herself.
  • Thumbnail Image
    Publication
    Faster Algorithms for Privately Releasing Marginals
    (Springer Verlag, 2012) Thaler, Justin; Ullman, Jonathan; Vadhan, Salil
    We study the problem of releasing k-way marginals of a database D ∈ {0,1}d)n, while preserving differential privacy. The an- swer to a k-way marginal query is the fraction of D’s records x ∈ {0, 1}d with a given value in each of a given set of up to k columns. Marginal queries enable a rich class of statistical analyses of a dataset, and de- signing efficient algorithms for privately releasing marginal queries has been identified as an important open problem in private data analysis (cf. Barak et. al., PODS ’07). We give an algorithm that runs in time dO( k) and releases a private summary capable of answering any k-way marginal query with at most ±.01 error on every query as long as n ≥ dO( k). To our knowledge, ours is the first algorithm capable of privately releasing marginal queries with non-trivial worst-case accuracy guarantees in time substantially smaller than the number of k-way marginal queries, which is dΘ(k) (for k ≪ d).