Buchumschlag

Beyond Worst Case Local Computation Algorithms

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Biswas, Amartya Shankha, Cao, Ruidi, Marcussen, Cassandra, Pyne, Edward, Rubinfeld, Ronitt, Shapira, Asaf, Tauber, Shlomo
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 Fast Coloring Oracle for Average Case Hypergraphs
von: Marcussen, Cassandra, et al.
Veröffentlicht: (2025)

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

Stochastic Matching via In-n-Out Local Computation Algorithms
von: Azarmehr, Amir, et al.
Veröffentlicht: (2024)

Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
von: Mitrović, Slobodan, et al.
Veröffentlicht: (2026)

Locally computing edge orientations
von: Mitrović, Slobodan, et al.
Veröffentlicht: (2025)

Testable algorithms for approximately counting edges and triangles in sublinear time and space
von: Eden, Talya, et al.
Veröffentlicht: (2025)

Optimal Algorithms for Augmented Testing of Discrete Distributions
von: Aliakbarpour, Maryam, et al.
Veröffentlicht: (2024)

Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time
von: Eden, Talya, et al.
Veröffentlicht: (2025)

No Price Tags? No Problem: Query Strategies for Unpriced Information
von: Nadimpalli, Shivam, et al.
Veröffentlicht: (2025)

Better Private Distribution Testing by Leveraging Unverified Auxiliary Data
von: Aliakbarpour, Maryam, et al.
Veröffentlicht: (2025)

Efficient Catalytic Graph Algorithms
von: Cook, James, et al.
Veröffentlicht: (2025)

Polynomial Property Testing
von: Gishboliner, Lior, et al.
Veröffentlicht: (2025)

Online Metric Matching: Beyond the Worst Case
von: Yang, Mingwei, et al.
Veröffentlicht: (2024)

Catalytic Tree Evaluation From Matching Vectors
von: Henzinger, Alexandra, et al.
Veröffentlicht: (2026)

Worst-Case to Expander-Case Reductions: Derandomized and Generalized
von: Abboud, Amir, et al.
Veröffentlicht: (2024)

Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
von: Silwal, Sandeep, et al.
Veröffentlicht: (2025)

From Amortized to Worst Case Delay in Enumeration Algorithms
von: Capelli, Florent, et al.
Veröffentlicht: (2021)

(Worst-Case) Optimal Adaptive Dynamic Bitvectors
von: Navarro, Gonzalo
Veröffentlicht: (2024)

Dynamic Set Cover with Worst-Case Recourse
von: Solomon, Shay, et al.
Veröffentlicht: (2025)

The Structure of In-Place Space-Bounded Computation
von: Cook, James, et al.
Veröffentlicht: (2025)

Learning and Testing Convex Functions
von: Pinto Jr., Renato Ferreira, et al.
Veröffentlicht: (2025)

Optimal Static Dictionary with Worst-Case Constant Query Time
von: Hu, Yang, et al.
Veröffentlicht: (2024)

Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
von: Ghaffari, Mohsen, et al.
Veröffentlicht: (2025)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
von: Meierhans, Simon, et al.
Veröffentlicht: (2025)

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
von: Meierhans, Simon, et al.
Veröffentlicht: (2025)

Finding the root in random nearest neighbor trees
von: Brandenberger, Anna, et al.
Veröffentlicht: (2024)

Triangle Detection in Worst-Case Sparse Graphs via Local Sketching
von: Duan, Hongyi, et al.
Veröffentlicht: (2025)

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2025)

Improved Sublinear Algorithms for Classical and Quantum Graph Coloring
von: Ferber, Asaf, et al.
Veröffentlicht: (2025)

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

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

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

Count-Min Sketch with Conservative Updates: Worst-Case Analysis
von: Mazziane, Younes Ben, et al.
Veröffentlicht: (2024)

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

Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
von: Mao, Xiao
Veröffentlicht: (2023)

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

Fault-Equivalent Lowest Common Ancestors
von: Petruschka, Asaf
Veröffentlicht: (2024)

Parks and Recreation: Color Fault-Tolerant Spanners Made Local
von: Parter, Merav, et al.
Veröffentlicht: (2024)

Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
von: Peng, Pan, et al.
Veröffentlicht: (2026)

Perfect Simulation of Las Vegas Algorithms via Local Computation
von: Fu, Xinyu, et al.
Veröffentlicht: (2023)