Cover Image

Almost Tight Bounds for Differentially Private Densest Subgraph

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dinitz, Michael, Kale, Satyen, Lattanzi, Silvio, Vassilvitskii, Sergei
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Differentially Private Densest Subgraph Detection
by: Nguyen, Dung, et al.
Published: (2021)

Data-Driven Solution Portfolios
by: Drygala, Marina, et al.
Published: (2024)

Destroying Densest Subgraphs is Hard
by: Bazgan, Cristina, et al.
Published: (2024)

Scalable $k$-clique Densest Subgraph Search
by: Ye, Xiaowei, et al.
Published: (2024)

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

Binary Search with Distributional Predictions
by: Dinitz, Michael, et al.
Published: (2024)

New Parallel and Streaming Algorithms for Directed Densest Subgraph
by: Mitrović, Slobodan, et al.
Published: (2025)

Differentially Private Matchings
by: Dinitz, Michael, et al.
Published: (2025)

A Generalized Binary Tree Mechanism for Differentially Private Approximation of All-Pair Distances
by: Dinitz, Michael, et al.
Published: (2025)

Fast and Simple Densest Subgraph with Predictions
by: Bui, Thai, et al.
Published: (2025)

Almost Tight Bounds for Online Hypergraph Matching
by: Tröbst, Thorben, et al.
Published: (2024)

Differentially Private Learning of Exponential Distributions: Simple Algorithms and Tight Bounds
by: Mahpud, Bar, et al.
Published: (2025)

An Efficient and Exact Algorithm for Locally h-Clique Densest Subgraph Discovery
by: Xu, Xiaojia, et al.
Published: (2024)

Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More
by: Chandra, Rishi, et al.
Published: (2024)

Fast and Optimal Incremental Parametric Procedure for the Densest Subgraph Problem: An Experimental Study
by: Hochbaum, Dorit S., et al.
Published: (2025)

In-depth Analysis of Densest Subgraph Discovery in a Unified Framework
by: Zhou, Yingli, et al.
Published: (2024)

Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
by: Khanna, Sanjeev, et al.
Published: (2024)

A Survey on the Densest Subgraph Problem and Its Variants
by: Lanciano, Tommaso, et al.
Published: (2023)

A Note on Approximability of Densest At-Least-k-Subgraph
by: Laekhanukit, Bundit, et al.
Published: (2026)

Multiplicative Weights Update, Area Convexity and Random Coordinate Descent for Densest Subgraph Problems
by: Nguyen, Ta Duy, et al.
Published: (2024)

Efficient Processing of Subsequent Densest Subgraph Query
by: Hung, Chia-Yang, et al.
Published: (2024)

Controlling tail risk in two-slope ski rental
by: Cui, Qiming, et al.
Published: (2025)

Tree Search With Predictions
by: Dinitz, Michael, et al.
Published: (2026)

The Vertex-Attribute-Constrained Densest $k$-Subgraph Problem
by: Lu, Qiheng, et al.
Published: (2025)

Warm-starting Push-Relabel
by: Davies, Sami, et al.
Published: (2024)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
by: Döring, Simon, et al.
Published: (2024)

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

Tight Bounds for Classical Open Addressing
by: Bender, Michael A., et al.
Published: (2024)

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling
by: Das, Rathish, et al.
Published: (2025)

Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines
by: Dinitz, Michael, et al.
Published: (2025)

Ski Rental with Distributional Predictions of Unknown Quality
by: Cui, Qiming, et al.
Published: (2026)

Tight Differentially Private PCA via Matrix Coherence
by: d'Orsi, Tommaso, et al.
Published: (2025)

Convex Optimization with Local Label Differential Privacy: Tight Bounds in All Privacy Regimes
by: Chua, Lynn, et al.
Published: (2026)

Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling
by: Zhou, Felix
Published: (2025)

Tight Sampling Bounds for Eigenvalue Approximation
by: Swartworth, William, et al.
Published: (2024)

On Densest $k$-Subgraph Mining and Diagonal Loading: Optimization Landscape and Finite-Step Exact Convergence Analysis
by: Lu, Qiheng, et al.
Published: (2024)

OptiRefine: Densest subgraphs and maximum cuts with $k$ refinements
by: Tu, Sijing, et al.
Published: (2025)

Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds
by: Kapralov, Michael, et al.
Published: (2022)