Cover Image

Improved Lower Bounds for Privacy under Continual Release

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Aryanfard, Bardiya, Henzinger, Monika, Saulpic, David, Sricharan, A. R.
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Differentially Private Continual Release of Histograms and Related Queries
by: Henzinger, Monika, et al.
Published: (2023)

Tighter Bounds for Local Differentially Private Core Decomposition and Densest Subgraph
by: Henzinger, Monika, et al.
Published: (2024)

Fully Dynamic k-Means Coreset in Near-Optimal Update Time
by: la Tour, Max Dupré, et al.
Published: (2024)

Improved Differentially Private Continual Observation Using Group Algebra
by: Henzinger, Monika, et al.
Published: (2024)

Private Counting of Distinct Elements in the Turnstile Model and Extensions
by: Henzinger, Monika, et al.
Published: (2024)

Making Old Things New: A Unified Algorithm for Differentially Private Clustering
by: la Tour, Max Dupré, et al.
Published: (2024)

Concurrent Composition for Differentially Private Continual Mechanisms
by: Henzinger, Monika, et al.
Published: (2024)

An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
by: Henzinger, Monika, et al.
Published: (2025)

Continual Counting with Gradual Privacy Expiration
by: Andersson, Joel Daniel, et al.
Published: (2024)

Almost Tight Error Bounds on Differentially Private Continual Counting
by: Henzinger, Monika, et al.
Published: (2022)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism
by: Dhulipala, Laxman, et al.
Published: (2025)

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
by: Zheng, Da Wei, et al.
Published: (2023)

Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond
by: Axiotis, Kyriakos, et al.
Published: (2024)

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
by: Bansal, Nikhil, et al.
Published: (2024)

Differentially Private Algorithms for Graphs Under Continual Observation
by: Fichtenberger, Hendrik, et al.
Published: (2021)

Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting
by: Henzinger, Monika, et al.
Published: (2025)

Constant matters: Fine-grained Complexity of Differentially Private Continual Observation
by: Fichtenberger, Hendrik, et al.
Published: (2022)

Binned Group Algebra Factorization for Differentially Private Continual Counting
by: Henzinger, Monika, et al.
Published: (2025)

Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time
by: El-Hayek, Antoine, et al.
Published: (2025)

Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation
by: El-Hayek, Antoine, et al.
Published: (2024)

On $b$-Matching and Fully-Dynamic Maximum $k$-Edge Coloring
by: El-Hayek, Antoine, et al.
Published: (2023)

Efficient Contractions of Dynamic Graphs -- with Applications
by: Henzinger, Monika, et al.
Published: (2025)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
by: Henzinger, Monika, et al.
Published: (2024)

Settling Time vs. Accuracy Tradeoffs for Clustering Big Data
by: Draganov, Andrew, et al.
Published: (2024)

Faster and Simpler Greedy Algorithm for $k$-Median and $k$-Means
by: la Tour, Max Dupré, et al.
Published: (2024)

Improved Lower Bounds on the Expected Length of Longest Common Subsequences
by: Heineman, George T., et al.
Published: (2024)

Dynamic Hierarchical $j$-Tree Decomposition and Its Applications
by: Goranci, Gramoz, et al.
Published: (2026)

Near-Optimal Generalized Private Testing
by: Chaturvedi, Anamay, et al.
Published: (2026)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Tight Bounds for Gaussian Mean Estimation under Personalized Differential Privacy
by: Dong, Wei, et al.
Published: (2026)

Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound
by: Cervenjak, Philip, et al.
Published: (2024)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
by: Goranci, Gramoz, et al.
Published: (2023)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
by: Boneh, Itai, et al.
Published: (2025)

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
by: Yoshida, Yuichi
Published: (2026)

New Algorithms and Lower Bounds for Streaming Tournaments
by: Ghosh, Prantar, et al.
Published: (2024)

Lower Bounds on $0$-Extension with Steiner Nodes
by: Chen, Yu, et al.
Published: (2024)

Double Exponential Lower Bound for Telephone Broadcast
by: Tale, Prafullkumar
Published: (2024)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
by: Chen, Yu, et al.
Published: (2026)

Dynamic PageRank: Algorithms and Lower Bounds
by: Jayaram, Rajesh, et al.
Published: (2024)