Metraipolis › archive › dc_f10073e7b8ef
Private Online Release of Adaptive Linear Queries — arXiv:2611.05602
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.05602
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:31:30.290Z
- SHA-256 of the archived text
faf03c5a40573fe5ddbf6344655d469070e7e315431ca4eeb4033f3dcee7d44f- Stable URL of this page
https://metraipolis.com/documento/dc_f10073e7b8ef
How to cite
Private Online Release of Adaptive Linear Queries — arXiv:2611.05602 — arXiv (en), https://arxiv.org/abs/2611.05602 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f10073e7b8ef (Metraipolis archive dc_f10073e7b8ef, sha256 faf03c5a40573fe5ddbf6344655d469070e7e315431ca4eeb4033f3dcee7d44f)
BibTeX
@misc{dcf10073e7b8ef,
title = {Private Online Release of Adaptive Linear Queries — arXiv:2611.05602},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.05602},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f10073e7b8ef; sha256 faf03c5a40573fe5ddbf6344655d469070e7e315431ca4eeb4033f3dcee7d44f},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05602. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In this paper we study answering counting and other linear queries online under differential privacy constraints. Recent work by Nikolov, Tang, and Ullman [STOC 2026] gave the first online algorithm that answers \emph{obliviously chosen} online linear queries privately, and achieves poly-logarithmic competitiveness against an optimal offline factorization mechanism. This also implied poly-logarithmic competitiveness against arbitrary private offline mechanisms when the private dataset is large enough. The error guarantees of their algorithm, however, can fail when the queries are adaptive. We give a new algorithm that also achieves poly-logarithmic competitiveness, while being able to handle \emph{adaptively chosen} queries. This implies that there is no large separation between the optimal error bounds for privately answering, respectively, offline linear queries, obliviously chosen online linear queries, and adaptively chosen online linear queries. Our algorithm combines the online factorization approach from prior work with a novel layered Euclidean iterative database construction, presenting a new way to use factorization in private algorithms. We also give a lower bound that shows that some poly-logarithmic factor in the competitive ratio is unavoidable. Our lower bound first shows that any interactive private mechanism implies a deterministic online factorization algorithm, and then gives a new lower bound for the competitive ratio of any deterministic online factorization algorithm.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.05602 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:21:04.021Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).