Buchumschlag

Spectral Sparsification by Deterministic Discrepancy Walk

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Lau, Lap Chi, Wang, Robert, Zhou, Hong
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms Combinatorics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

A Combinatorial Characterization of Constant Mixing Time
von: Lau, Lap Chi, et al.
Veröffentlicht: (2025)

On the Houdré-Tetali conjecture about an isoperimetric constant of graphs
von: Lau, Lap Chi, et al.
Veröffentlicht: (2024)

Experimental Design Using Interlacing Polynomials
von: Lau, Lap Chi, et al.
Veröffentlicht: (2024)

Palette Sparsification for Graphs with Sparse Neighborhoods
von: Dhawan, Abhishek
Veröffentlicht: (2024)

Deterministically approximating the volume of a Kostka polytope
von: Narayanan, Hariharan, et al.
Veröffentlicht: (2025)

A Faster Deterministic Approximation Algorithm for TTP-2
von: Kanaya, Yuga, et al.
Veröffentlicht: (2023)

Sub-$n^k$ Deterministic algorithm for minimum $k$-way cut in simple graphs
von: Daga, Mohit
Veröffentlicht: (2025)

Derandomizing Matrix Concentration Inequalities from Free Probability
von: Wang, Robert, et al.
Veröffentlicht: (2026)

Streaming and Communication Complexity of Load-Balancing via Matching Contractors
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Efficient Algorithms for Partitioning Circulant Graphs with Optimal Spectral Approximation
von: Gavva, Surya Teja, et al.
Veröffentlicht: (2025)

Fast and Faithful Edge Bundling using Spectral Sparsification
von: Jiang, Xingjue, et al.
Veröffentlicht: (2026)

Optimal Algorithm for Paired-Domination in Distance-Hereditary Graphs
von: Mu, Ta-Yu, et al.
Veröffentlicht: (2024)

Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting
von: Avila, Tatiana Rocha, et al.
Veröffentlicht: (2026)

A Theory of Spectral CSP Sparsification
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Fully Dynamic Spectral Sparsification of Hypergraphs
von: Goranci, Gramoz, et al.
Veröffentlicht: (2025)

Deterministic approximation for the volume of the truncated fractional matching polytope
von: Guo, Heng, et al.
Veröffentlicht: (2024)

A Faster Deterministic Algorithm for Mader's $\mathcal{S}$-Path Packing
von: Iwata, Satoru, et al.
Veröffentlicht: (2024)

Fully Dynamic Spectral Sparsification for Directed Hypergraphs
von: Forster, Sebastian, et al.
Veröffentlicht: (2025)

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
von: Gaspers, Serge, et al.
Veröffentlicht: (2025)

Average-Case Matrix Discrepancy: Asymptotics and Online Algorithms
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2023)

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
von: Bedert, Benjamin, et al.
Veröffentlicht: (2025)

Integrating High-Dimensional Functions Deterministically
von: Gamarnik, David, et al.
Veröffentlicht: (2024)

Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros
von: Bencs, Ferenc, et al.
Veröffentlicht: (2024)

Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
von: Bodwin, Greg, et al.
Veröffentlicht: (2023)

Complexity and Algorithm for the Matching vertex-cutset Problem
von: Li, Hengzhe, et al.
Veröffentlicht: (2025)

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

Cut Sparsification and Succinct Representation of Submodular Hypergraphs
von: Kenneth, Yotam, et al.
Veröffentlicht: (2023)

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Sparse induced subgraphs in $P_7$-free graphs of bounded clique number
von: Chudnovsky, Maria, et al.
Veröffentlicht: (2024)

Fast computation of permanents over $\mathbb{F}_3$ via $\mathbb{F}_2$ arithmetic
von: Scheinerman, Danny
Veröffentlicht: (2024)

Counting Permutation Patterns with Multidimensional Trees
von: Beniamini, Gal, et al.
Veröffentlicht: (2024)

Lightweight Near-Additive Spanners
von: Gitlitz, Yuval, et al.
Veröffentlicht: (2024)

Lower bounds for graph reconstruction with maximal independent set queries
von: Michel, Lukas, et al.
Veröffentlicht: (2024)

Matroid Intersection under Minimum Rank Oracle
von: Bárász, Mihály, et al.
Veröffentlicht: (2024)

Reconfiguration and Enumeration of Optimal Cyclic Ladder Lotteries
von: Nozaki, Yuta, et al.
Veröffentlicht: (2024)

A Minimum Counterexample Proof of the Seymour Second Neighborhood Conjecture via the Graph Level Order
von: Glover, Charles N.
Veröffentlicht: (2024)

Minor Containment and Disjoint Paths in almost-linear time
von: Korhonen, Tuukka, et al.
Veröffentlicht: (2024)

An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems
von: Murakami, Hitoshi, et al.
Veröffentlicht: (2024)

Sampling List Packings
von: Camrud, Evan, et al.
Veröffentlicht: (2024)

Non-adaptive Bellman-Ford: Yen's improvement is optimal
von: Hu, Jialu, et al.
Veröffentlicht: (2024)