Deterministic Weighted Expander Decomposition in Almost-linear Time

Jason Li; Thatchaphol Saranurak

Deterministic Weighted Expander Decomposition in Almost-linear Time

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

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

arxiv 2106.01567 v1 pith:R4ATUCFN submitted 2021-06-03 cs.DS

Jason Li , Thatchaphol Saranurak This is my paper

classification cs.DS

keywords almost-lineardecompositiondeterministicexpanderproblemsettingtimeweighted

verification ladder T0 review T1 audit T2 compute T3 formal

0 comments

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.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers
cs.DS 2026-07 conditional novelty 8.0 of 10

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)).

Pith tools