2013/04/13 by Karthekeyan Chandrasekaran, Justin Thaler, Chandrasekaran, Karthekeyan +5 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.1304.3754
openalex publication_date 2013/04/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of answering k-way marginal queries on a database D ∈ (\0,1\d)n, while preserving differential privacy. The answer to a k-way marginal query is the fraction of the database'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 on a dataset, and designing efficient algorithms for privately answering marginal queries has been identified as an important open problem in private data analysis. For any k, we give a differentially private online algorithm that runs in time minexp(d1-Ω(1/√(k))), exp(d / log.99 d)\ per query and answers any (possibly superpolynomially long and adaptively chosen) sequence of k-way marginal queries up to error at most ± .01 on every query, provided n \gtrsim d.51 . To the best of our knowledge, this is the first algorithm capable of privately answering marginal queries with a non-trivial worst-case accuracy guarantee on a database of size \poly(d, k) in time exp(o(d)). Our algorithms are a variant of the private multiplicative weights algorithm (Hardt and Rothblum, FOCS '10), but using a different low-weight representation of the database. We derive our low-weight representation using approximations to the OR function by low-degree polynomials with coefficients of bounded L1-norm. We also prove a strong limitation on our approach that is of independent approximation-theoretic interest. Specifically, we show that for any k = o(log d), any polynomial with coefficients of L1-norm poly(d) that pointwise approximates the d-variate OR function on all inputs of Hamming weight at most k must have degree d1-O(1/√(k)).