Buchumschlag

Efficient Algorithms and New Characterizations for CSP Sparsification

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Khanna, Sanjeev, Putterman, Aaron L., Sudan, Madhu
Format:	Preprint
Veröffentlicht:	2024
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

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

Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

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

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2024)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

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

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2026)

On the Parallel Complexity of Finding a Matroid Basis
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2026)

Streaming approximation resistance of every ordering CSP
von: Singer, Noah G., et al.
Veröffentlicht: (2021)

Optimal Parallel Basis Finding in Graphic and Related Matroids
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Lower Bounds for Non-adaptive Local Computation Algorithms
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
von: Saxena, Raghuvansh R., et al.
Veröffentlicht: (2024)

Maximum Bipartite Matching in $n^{2+o(1)}$ Time via a Combinatorial Algorithm
von: Chuzhoy, Julia, et al.
Veröffentlicht: (2024)

An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2026)

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
von: Chuzhoy, Julia, et al.
Veröffentlicht: (2026)

Markov Chains with Rewinding
von: Azarmehr, Amir, et al.
Veröffentlicht: (2026)

Eulerian Graph Sparsification by Effective Resistance Decomposition
von: Jambulapati, Arun, et al.
Veröffentlicht: (2024)

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Query Complexity of the Metric Steiner Tree Problem
von: Chen, Yu, et al.
Veröffentlicht: (2022)

Streaming Maximal Matching with Bounded Deletions
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Structure-Aware Spectral Sparsification via Uniform Edge Sampling
von: He, Kaiwen, et al.
Veröffentlicht: (2025)

Simpler O(1) Query Algorithm for Level Ancestors
von: Saxena, Sanjeev
Veröffentlicht: (2022)

Quality control in sublinear time: a case study via random graphs
von: Marcussen, Cassandra, et al.
Veröffentlicht: (2025)

Towards an algebraic approach to the reconfiguration CSP
von: Kimura, Kei
Veröffentlicht: (2025)

Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval
von: Kuszmaul, William, et al.
Veröffentlicht: (2024)

Redundancy Is All You Need (for CSP Sparsification)
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2024)

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

Bounded Independence Edge Sampling for Combinatorial Graph Properties
von: Putterman, Aaron, et al.
Veröffentlicht: (2026)

Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette Sparsification
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Parameterized Complexity of MinCSP over the Point Algebra
von: Osipov, George, et al.
Veröffentlicht: (2023)

Max-Distance Sparsification for Diversification and Clustering
von: Kumabe, Soh
Veröffentlicht: (2024)

Bootstrapping Dynamic APSP via Sparsification
von: Kyng, Rasmus, et al.
Veröffentlicht: (2024)

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

Linear Space Streaming Lower Bounds for Approximating CSPs
von: Chou, Chi-Ning, et al.
Veröffentlicht: (2021)

Balancing Weights, Directed Sparsification, and Augmenting Paths
von: Li, Jason
Veröffentlicht: (2026)

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

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

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