Copertina

Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Aamand, Anders, Chen, Justin Y., Dalirrooyfard, Mina, Mitrović, Slobodan, Nevmyvaka, Yuriy, Silwal, Sandeep, Xu, Yinzhan
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Differentially Private Gomory-Hu Trees
di: Aamand, Anders, et al.
Pubblicazione: (2024)

Skirting Additive Error Barriers for Private Turnstile Streams
di: Aamand, Anders, et al.
Pubblicazione: (2026)

Graph Partitioning With Limited Moves
di: Behbahani, Majid, et al.
Pubblicazione: (2024)

A Simple Average-case Analysis of Recursive Randomized Greedy MIS
di: Dalirrooyfard, Mina, et al.
Pubblicazione: (2026)

SPARSE-PIVOT: Dynamic correlation clustering for node insertions
di: Dalirrooyfard, Mina, et al.
Pubblicazione: (2025)

Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
di: Dalirrooyfard, Mina, et al.
Pubblicazione: (2024)

Improved Approximations for Hard Graph Problems using Predictions
di: Aamand, Anders, et al.
Pubblicazione: (2025)

How fast can you find a good hypothesis?
di: Aamand, Anders, et al.
Pubblicazione: (2025)

Differentially Private Quantiles with Smaller Error
di: Imola, Jacob, et al.
Pubblicazione: (2025)

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
di: Dalirrooyfard, Mina, et al.
Pubblicazione: (2023)

On the Structure of Replicable Hypothesis Testers
di: Aamand, Anders, et al.
Pubblicazione: (2025)

Learning-Augmented Frequent Directions
di: Aamand, Anders, et al.
Pubblicazione: (2025)

Statistical-Computational Trade-offs for Density Estimation
di: Aamand, Anders, et al.
Pubblicazione: (2024)

Efficiently Computing Similarities to Private Datasets
di: Backurs, Arturs, et al.
Pubblicazione: (2024)

A framework for boosting matching approximation: parallel, distributed, and dynamic
di: Mitrović, Slobodan, et al.
Pubblicazione: (2025)

Eulerian Graph Sparsification by Effective Resistance Decomposition
di: Jambulapati, Arun, et al.
Pubblicazione: (2024)

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
di: Łącki, Jakub, et al.
Pubblicazione: (2025)

Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model and Beyond
di: Fischer, Manuela, et al.
Pubblicazione: (2021)

Locally computing edge orientations
di: Mitrović, Slobodan, et al.
Pubblicazione: (2025)

Near-Optimal Trace Reconstruction for Mildly Separated Strings
di: Aamand, Anders, et al.
Pubblicazione: (2024)

On the Streaming Complexity of Expander Decomposition
di: Chen, Yu, et al.
Pubblicazione: (2024)

Improved Directed Expander Decompositions
di: Fleischmann, Henry, et al.
Pubblicazione: (2025)

Approximate counting of permutation patterns
di: Ben-Eliezer, Omri, et al.
Pubblicazione: (2024)

Expander Decomposition with Almost Optimal Overhead
di: Bansal, Nikhil, et al.
Pubblicazione: (2026)

Simple Length-Constrained Expander Decompositions
di: Bodwin, Greg, et al.
Pubblicazione: (2025)

Expander Decomposition for Non-Uniform Vertex Measures
di: Agassy, Daniel, et al.
Pubblicazione: (2025)

Near-Optimal Algorithm for Directed Expander Decompositions
di: Sulser, Aurelio L., et al.
Pubblicazione: (2024)

Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
di: Mitrović, Slobodan, et al.
Pubblicazione: (2026)

Additive Sparsification of CSPs
di: Pelleg, Eden, et al.
Pubblicazione: (2021)

New Structures and Algorithms for Length-Constrained Expander Decompositions
di: Haeupler, Bernhard, et al.
Pubblicazione: (2024)

Faster Weak Expander Decompositions and Approximate Max Flow
di: Fleischmann, Henry, et al.
Pubblicazione: (2025)

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

Faster Semi-streaming Matchings via Alternating Trees
di: Mitrović, Slobodan, et al.
Pubblicazione: (2024)

Robust Streaming Against Low-Memory Adversaries
di: Ben-Eliezer, Omri, et al.
Pubblicazione: (2025)

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
di: Chen, Daoyuan, et al.
Pubblicazione: (2024)

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
di: Jin, Ce, et al.
Pubblicazione: (2024)

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

Dynamic Construction of the Lovász Local Lemma
di: Haeupler, Bernhard, et al.
Pubblicazione: (2026)

Online Sorting and Translational Packing of Convex Polygons
di: Aamand, Anders, et al.
Pubblicazione: (2021)

Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts
di: Haeupler, Bernhard, et al.
Pubblicazione: (2025)