Image de couverture de livre

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Khanna, Sanjeev, Li, Huan, Putterman, Aaron
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
par: Khanna, Sanjeev, et autres
Publié: (2024)

Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
par: Khanna, Sanjeev, et autres
Publié: (2025)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
par: Assadi, Sepehr, et autres
Publié: (2025)

A Theory of Spectral CSP Sparsification
par: Khanna, Sanjeev, et autres
Publié: (2025)

Efficient Algorithms and New Characterizations for CSP Sparsification
par: Khanna, Sanjeev, et autres
Publié: (2024)

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
par: Khanna, Sanjeev, et autres
Publié: (2024)

Fully Dynamic Spectral Sparsification of Hypergraphs
par: Goranci, Gramoz, et autres
Publié: (2025)

Fully Dynamic Spectral Sparsification for Directed Hypergraphs
par: Forster, Sebastian, et autres
Publié: (2025)

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
par: Khanna, Sanjeev, et autres
Publié: (2026)

On the Parallel Complexity of Finding a Matroid Basis
par: Khanna, Sanjeev, et autres
Publié: (2025)

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
par: Khanna, Sanjeev, et autres
Publié: (2026)

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
par: Chuzhoy, Julia, et autres
Publié: (2026)

Optimal Parallel Basis Finding in Graphic and Related Matroids
par: Khanna, Sanjeev, et autres
Publié: (2025)

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs
par: Assadi, Sepehr, et autres
Publié: (2024)

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
par: Agarwal, Arpit, et autres
Publié: (2024)

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
par: Cohen-Addad, Vincent, et autres
Publié: (2025)

Cut Sparsification and Succinct Representation of Submodular Hypergraphs
par: Kenneth, Yotam, et autres
Publié: (2023)

Maximum Bipartite Matching in $n^{2+o(1)}$ Time via a Combinatorial Algorithm
par: Chuzhoy, Julia, et autres
Publié: (2024)

An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths
par: Khanna, Sanjeev, et autres
Publié: (2026)

Sketching Cuts in Graphs and Hypergraphs
par: Kogan, Dmitry, et autres
Publié: (2014)

Structure-Aware Spectral Sparsification via Uniform Edge Sampling
par: He, Kaiwen, et autres
Publié: (2025)

Quantum Speedup for Hypergraph Sparsification
par: Liu, Chenghua, et autres
Publié: (2025)

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
par: Khanna, Sanjeev, et autres
Publié: (2025)

Fast and Faithful Edge Bundling using Spectral Sparsification
par: Jiang, Xingjue, et autres
Publié: (2026)

Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval
par: Kuszmaul, William, et autres
Publié: (2024)

Faster Spectral Density Estimation and Sparsification in the Nuclear Norm
par: Jin, Yujia, et autres
Publié: (2024)

Spectral Sparsification by Deterministic Discrepancy Walk
par: Lau, Lap Chi, et autres
Publié: (2024)

Bootstrapping Dynamic APSP via Sparsification
par: Kyng, Rasmus, et autres
Publié: (2024)

Eulerian Graph Sparsification by Effective Resistance Decomposition
par: Jambulapati, Arun, et autres
Publié: (2024)

Fully Dynamic Algorithms for Chamfer Distance
par: Goranci, Gramoz, et autres
Publié: (2025)

Fully Dynamic Algorithms for Transitive Reduction
par: Goranci, Gramoz, et autres
Publié: (2025)

Linear-Time Multilevel Graph Partitioning via Edge Sparsification
par: Gottesbüren, Lars, et autres
Publié: (2025)

Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs
par: Zhao, Yibin
Publié: (2025)

Streaming Maximal Matching with Bounded Deletions
par: Khanna, Sanjeev, et autres
Publié: (2025)

Query Complexity of the Metric Steiner Tree Problem
par: Chen, Yu, et autres
Publié: (2022)

Adaptive Sparsification for Linear Programming
par: Objois, Étienne, et autres
Publié: (2025)

Simple Algorithms for Fully Dynamic Edge Connectivity
par: Kenneth-Mordoch, Yotam, et autres
Publié: (2025)

Simpler O(1) Query Algorithm for Level Ancestors
par: Saxena, Sanjeev
Publié: (2022)

Near-Optimal Minimum Cuts in Hypergraphs at Scale
par: Chhabra, Adil, et autres
Publié: (2025)

Near-optimal Algorithms for Stochastic Online Bin Packing
par: Ayyadevara, Nikhil, et autres
Publié: (2022)