REVIEW 2 cited by
Deterministic Weighted Expander Decomposition in Almost-linear Time
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
In this note, we study the expander decomposition problem in a more general setting where the input graph has positively weighted edges and nonnegative demands on its vertices. We show how to extend the techniques of Chuzhoy et al. (FOCS 2020) to this wider setting, obtaining a deterministic algorithm for the problem in almost-linear time.
Forward citations
Cited by 2 Pith papers
-
Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers
An edge-differentially-private algorithm approximates every cut of any unweighted n-vertex graph with error γ·cut + Õ(n^(13/12+o(1))), beating the previous polynomial-time bound of n^(5/4+o(1)).
-
Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
A polynomial-time differentially private algorithm approximates every cut in a graph within (1+γ) multiplicative and n^{1.25+o(1)} additive error, breaking the previous n^{1.5} barrier.
Discussion (0). Continue with ORCID to comment.