Catalytic space enables exact multi-pass algorithms for frequency moments F_k and induced subgraph counting using O(k log m) clean space, while single-pass catalytic algorithms add no power.
Journal of Computer and System Sciences , volume =
11 Pith papers cite this work, alongside 1,177 external citations. Polarity classification is still indexing.
11
Pith papers citing it
1,177
external citations · external index
citation-role summary
background 2
citation-polarity summary
years
2026 11roles
background 2polarities
background 2representative citing papers
Quantum-inspired estimators for F_alpha(P) and F_alpha(rho) achieve optimal sample complexity n ~ alpha and minimax MSE rate alpha/n, improving prior O(alpha^2) bounds.
Streaming max-cut requires Ω(n) space for dense graphs but Ω(n log(ε² n)/ε²) space for graphs with Θ(n/ε²) edges when outputting the cut, with matching upper bounds for dense case and similar separations for densest subgraph.
Computing GapMAJ∘fⁿ requires n·(I−O(1)) bits of information, making GapMAJ the third outer gadget with a strong composition theorem in two-player communication.
Improved (O(pw), Δ)-LDD for pathwidth-pw digraphs and O(tw log n) integrality gap for directed sparsest-cut LP on treewidth-tw graphs via refined quasipartition analysis.
Direct fixed-weight solver for free-support Wasserstein medians relocates atoms using OT barycentric projections and inverse-distance weights, achieving monotone descent on smoothed objectives with fewer subproblems than nested Weiszfeld baselines.
Proposes a scale-calibrated median-of-means estimator for robust aggregation of distributed PCA estimates on the product of Euclidean space and Grassmann manifold.
Hybrid sketching saves up to 97% space on dense graphs and 15% on sparse ones by sketching dense cores and storing sparse parts exactly, with new BalloonSketch reducing sketch sizes up to 8x.
The profile maximum likelihood estimator for the location in anisotropic hyperbolic wrapped normal models is strongly consistent, asymptotically normal, and attains the Hájek-Le Cam minimax lower bound under squared geodesic loss.
Joint location-scale minimization for geometric medians on product manifolds degenerates to marginal medians, and three new scale-selection methods restore identifiability with asymptotic guarantees.
A review reframing density estimation as 'density evolution' across scales, linking kernel smoothing to heat flow, mixtures to compression, and topology to level sets, while stating three structural results on modes, Gaussian semigroups, and log-concavity.
citing papers explorer
-
Computing over Data Streams using Catalytic Space
Catalytic space enables exact multi-pass algorithms for frequency moments F_k and induced subgraph counting using O(k log m) clean space, while single-pass catalytic algorithms add no power.
-
Towards Minimax Estimation of High-Order Functionals by Quantum Arguments
Quantum-inspired estimators for F_alpha(P) and F_alpha(rho) achieve optimal sample complexity n ~ alpha and minimax MSE rate alpha/n, improving prior O(alpha^2) bounds.
-
Streaming Complexity Separations for Dense and Sparse Graphs
Streaming max-cut requires Ω(n) space for dense graphs but Ω(n log(ε² n)/ε²) space for graphs with Θ(n/ε²) edges when outputting the cut, with matching upper bounds for dense case and similar separations for densest subgraph.
-
Gap-Majority Lemmas in Communication Complexity
Computing GapMAJ∘fⁿ requires n·(I−O(1)) bits of information, making GapMAJ the third outer gadget with a strong composition theorem in two-player communication.
-
Directed Low Diameter Decomposition for Structured Digraphs
Improved (O(pw), Δ)-LDD for pathwidth-pw digraphs and O(tw log n) integrality gap for directed sparsest-cut LP on treewidth-tw graphs via refined quasipartition analysis.
-
Fast Computation of Free-Support Wasserstein Medians
Direct fixed-weight solver for free-support Wasserstein medians relocates atoms using OT barycentric projections and inverse-distance weights, achieving monotone descent on smoothed objectives with fewer subproblems than nested Weiszfeld baselines.
-
Scale-Calibrated Median-of-Means for Robust Distributed Principal Component Analysis
Proposes a scale-calibrated median-of-means estimator for robust aggregation of distributed PCA estimates on the product of Euclidean space and Grassmann manifold.
-
Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs
Hybrid sketching saves up to 97% space on dense graphs and 15% on sparse ones by sketching dense cores and storing sparse parts exactly, with new BalloonSketch reducing sketch sizes up to 8x.
-
Profile Likelihood Inference for Anisotropic Hyperbolic Wrapped Normal Models on Hyperbolic Space
The profile maximum likelihood estimator for the location in anisotropic hyperbolic wrapped normal models is strongly consistent, asymptotically normal, and attains the Hájek-Le Cam minimax lower bound under squared geodesic loss.
-
Scale selection for geometric medians on product manifolds
Joint location-scale minimization for geometric medians on product manifolds degenerates to marginal medians, and three new scale-selection methods restore identifiability with asymptotic guarantees.
-
Density Evolution: A Multiscale View of Density Estimation
A review reframing density estimation as 'density evolution' across scales, linking kernel smoothing to heat flow, mixtures to compression, and topology to level sets, while stating three structural results on modes, Gaussian semigroups, and log-concavity.