Buchumschlag

Dynamic Kernel Graph Sparsifiers

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Cao, Yang, Deng, Yichuan, Jin, Wenyu, Li, Xiaoyu, Song, Zhao, Sun, Xiaorui, Weinstein, Omri
Format:	Preprint
Veröffentlicht:	2022
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Discrepancy Minimization in Input-Sparsity Time
von: Deng, Yichuan, et al.
Veröffentlicht: (2022)

Training Overparametrized Neural Networks in Sublinear Time
von: Deng, Yichuan, et al.
Veröffentlicht: (2022)

Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time
von: Jin, Wenyu, et al.
Veröffentlicht: (2024)

Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs
von: Zhao, Yibin
Veröffentlicht: (2025)

Improved Sparse Recovery for Approximate Matrix Multiplication
von: Uffenheimer, Yahel, et al.
Veröffentlicht: (2026)

A Dynamic Low-Rank Fast Gaussian Transform
von: Huang, Baihe, et al.
Veröffentlicht: (2022)

Hardness Amplification for Dynamic Binary Search Trees
von: Jiang, Shunhua, et al.
Veröffentlicht: (2024)

A Framework for Building Data Structures from Communication Protocols
von: Andoni, Alexandr, et al.
Veröffentlicht: (2025)

Sparsifying Cayley Graphs on Every Group
von: Hsieh, Jun-Ting, et al.
Veröffentlicht: (2025)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
von: Koh, Zhuan Khye, et al.
Veröffentlicht: (2024)

(Approximate) Matrix Multiplication via Convolutions
von: Uffenheimer, Yahel, et al.
Veröffentlicht: (2025)

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
von: Das, Syamantak, et al.
Veröffentlicht: (2024)

Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs
von: Chen, Yu, et al.
Veröffentlicht: (2024)

Sparsifying Sums of Positive Semidefinite Matrices
von: Basu, Arpon, et al.
Veröffentlicht: (2025)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
von: Chen, Yu, et al.
Veröffentlicht: (2026)

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
von: Anand, Aditya, et al.
Veröffentlicht: (2025)

Improved Tree Sparsifiers in Near-Linear Time
von: Agassy, Daniel, et al.
Veröffentlicht: (2025)

Faster Algorithm for Structured John Ellipsoid Computation
von: Cao, Yang, et al.
Veröffentlicht: (2022)

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
von: Dughmi, Shaddin, et al.
Veröffentlicht: (2025)

Canonical forms for matrix tuples in polynomial time
von: Qiao, Youming, et al.
Veröffentlicht: (2024)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2024)

Twice-Ramanujan Sparsifiers
von: Batson, Joshua, et al.
Veröffentlicht: (2008)

Many Hamiltonians Are Sparsifiable
von: Basu, Arpon, et al.
Veröffentlicht: (2026)

Dynamic Similarity Graph Construction with Kernel Density Estimation
von: Laenen, Steinar, et al.
Veröffentlicht: (2025)

Unweighted One-Sided Code Sparsifiers and Thin Subgraphs
von: Gharan, Shayan Oveis, et al.
Veröffentlicht: (2025)

Quantum Speedups for Approximating the John Ellipsoid
von: Li, Xiaoyu, et al.
Veröffentlicht: (2024)

Space-Efficient Graph Kernelizations
von: Kammer, Frank, et al.
Veröffentlicht: (2020)

Dynamic Meta-Kernelization
von: Bertram, Christian, et al.
Veröffentlicht: (2025)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
von: Wang, Yichuan
Veröffentlicht: (2024)

Efficient Kernelization Algorithm for Bipartite Graph Matching
von: Wu, Guang, et al.
Veröffentlicht: (2024)

Scheduling two types of jobs with minimum makespan
von: Cao, Song, et al.
Veröffentlicht: (2024)

Tight Bounds for Sparsifying Random CSPs
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2025)

Changing Base Without Losing Pace: A GPU-Efficient Alternative to MatMul in DNNs
von: Ailon, Nir, et al.
Veröffentlicht: (2025)

Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance
von: Song, Zhao, et al.
Veröffentlicht: (2022)

Cluster Vertex Deletion on Chordal Graphs
von: Cao, Yixin, et al.
Veröffentlicht: (2026)

Discrete Effort Distribution via Regret-enabled Greedy Algorithm
von: Cao, Song, et al.
Veröffentlicht: (2025)

Robust Streaming Against Low-Memory Adversaries
von: Ben-Eliezer, Omri, et al.
Veröffentlicht: (2025)

Approximate counting of permutation patterns
von: Ben-Eliezer, Omri, et al.
Veröffentlicht: (2024)

Linear-Sized Spectral Sparsifiers and the Kadison-Singer Problem
von: Paschalidis, Phevos, et al.
Veröffentlicht: (2023)

Approximate Graph Propagation Revisited: Dynamic Parameterized Queries, Tighter Bounds and Dynamic Updates
von: Zhao, Zhuowei, et al.
Veröffentlicht: (2025)