Copertina

Worst-Case to Expander-Case Reductions: Derandomized and Generalized

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Abboud, Amir, Wallheimer, Nathan
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Triangle Detection in H-Free Graphs
di: Abboud, Amir, et al.
Pubblicazione: (2025)

Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
di: Abboud, Amir, et al.
Pubblicazione: (2026)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
di: Meierhans, Simon, et al.
Pubblicazione: (2025)

Recognizing Sumsets is NP-Complete
di: Abboud, Amir, et al.
Pubblicazione: (2024)

Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
di: Silwal, Sandeep, et al.
Pubblicazione: (2025)

Parallel Derandomization for Coloring
di: Coy, Sam, et al.
Pubblicazione: (2023)

Online Metric Matching: Beyond the Worst Case
di: Yang, Mingwei, et al.
Pubblicazione: (2024)

Beyond Worst Case Local Computation Algorithms
di: Biswas, Amartya Shankha, et al.
Pubblicazione: (2024)

(Worst-Case) Optimal Adaptive Dynamic Bitvectors
di: Navarro, Gonzalo
Pubblicazione: (2024)

Dynamic Set Cover with Worst-Case Recourse
di: Solomon, Shay, et al.
Pubblicazione: (2025)

On Beating $2^n$ for the Closest Vector Problem
di: Abboud, Amir, et al.
Pubblicazione: (2025)

Witness-Sensitive Detection of Induced Diamonds
di: Censor-Hillel, Keren, et al.
Pubblicazione: (2026)

Derandomizing Pseudopolynomial Algorithms for Subset Sum
di: Chan, Timothy M.
Pubblicazione: (2026)

Optimal Static Dictionary with Worst-Case Constant Query Time
di: Hu, Yang, et al.
Pubblicazione: (2024)

Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
di: Ghaffari, Mohsen, et al.
Pubblicazione: (2025)

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
di: Meierhans, Simon, et al.
Pubblicazione: (2025)

Quantum Worst-Case to Average-Case Reduction for Matrix-Vector Multiplication
di: Aggarwal, Divesh, et al.
Pubblicazione: (2025)

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2025)

Faster Combinatorial k-Clique Algorithms
di: Abboud, Amir, et al.
Pubblicazione: (2024)

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
di: Bansal, Nikhil, et al.
Pubblicazione: (2024)

Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection
di: van der Hoog, Ivor, et al.
Pubblicazione: (2025)

Cactus Representation of Minimum Cuts: Derandomize and Speed up
di: He, Zhongtian, et al.
Pubblicazione: (2024)

Count-Min Sketch with Conservative Updates: Worst-Case Analysis
di: Mazziane, Younes Ben, et al.
Pubblicazione: (2024)

Adaptive Fully Dynamic $k$-Center Clustering with (Near-)Optimal Worst-Case Guarantees
di: Grilnberger, Mara, et al.
Pubblicazione: (2026)

A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition
di: Gutenberg, Maximilian Probst, et al.
Pubblicazione: (2025)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
di: Haeupler, Bernhard, et al.
Pubblicazione: (2024)

Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
di: Mao, Xiao
Pubblicazione: (2023)

From Amortized to Worst Case Delay in Enumeration Algorithms
di: Capelli, Florent, et al.
Pubblicazione: (2021)

Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space
di: Jang, Jihoon, et al.
Pubblicazione: (2025)

Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles
di: Yan, Shuyi
Pubblicazione: (2025)

On the Streaming Complexity of Expander Decomposition
di: Chen, Yu, et al.
Pubblicazione: (2024)

Improved Directed Expander Decompositions
di: Fleischmann, Henry, et al.
Pubblicazione: (2025)

Hypergraph Samplers: Typical and Worst Case Behavior
di: Alev, Vedat Levi, et al.
Pubblicazione: (2026)

Expanderizing Higher Order Random Walks
di: Alev, Vedat Levi, et al.
Pubblicazione: (2024)

Optimal Electrical Oblivious Routing on Expanders
di: Florescu, Cella, et al.
Pubblicazione: (2024)

Finding Colorings in One-Sided Expanders
di: Buhai, Rares-Darius, et al.
Pubblicazione: (2025)

Expander Decomposition with Almost Optimal Overhead
di: Bansal, Nikhil, et al.
Pubblicazione: (2026)

Simple Length-Constrained Expander Decompositions
di: Bodwin, Greg, et al.
Pubblicazione: (2025)

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
di: Abboud, Amir, et al.
Pubblicazione: (2023)

Triangle Detection in Worst-Case Sparse Graphs via Local Sketching
di: Duan, Hongyi, et al.
Pubblicazione: (2025)