Cover Image

Optimal Protocols for 2-Party Contention Resolution

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Wang, Dingyu
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Multi-dimensional Approximate Counting
by: Wang, Dingyu
Published: (2024)

A Unified Construction of Streaming Sketches via the Lévy-Khintchine Representation Theorem
by: Pettie, Seth, et al.
Published: (2024)

Universal Perfect Samplers for Incremental Streams
by: Pettie, Seth, et al.
Published: (2024)

Pairwise-Independent Contention Resolution
by: Gupta, Anupam, et al.
Published: (2024)

Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon
by: Pettie, Seth, et al.
Published: (2020)

On HTLC-Based Protocols for Multi-Party Cross-Chain Swaps
by: Clark, Emily, et al.
Published: (2024)

Towards an Optimal Contention Resolution Scheme for Matchings
by: Nuti, Pranav, et al.
Published: (2022)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
by: Gholizadeh, Hossein, et al.
Published: (2025)

Harmonic Decomposition in Data Sketches
by: Wang, Dingyu
Published: (2024)

Instance-Optimality in PageRank Computation
by: Thorup, Mikkel, et al.
Published: (2025)

A Framework for Building Data Structures from Communication Protocols
by: Andoni, Alexandr, et al.
Published: (2025)

Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal
by: Wang, Hanzhi
Published: (2024)

Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes
by: Brubach, Brian, et al.
Published: (2021)

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
by: Hoppenworth, Gary, et al.
Published: (2025)

Optimal Extended Formulations from Optimal Dynamic Programming Algorithms
by: Oliveira, Mateus de Oliveira, et al.
Published: (2026)

Optimal Approximate Matrix Multiplication over Sliding Window
by: Xian, Haoming, et al.
Published: (2025)

Revisiting Local Computation of PageRank: Simple and Optimal
by: Wang, Hanzhi, et al.
Published: (2024)

Efficient and Practical Approximation Algorithms for Advertising in Content Feeds
by: Zhang, Guangyi, et al.
Published: (2025)

The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis
by: Kuszmaul, William, et al.
Published: (2021)

Fingerprint Filters Are Optimal
by: Kuszmaul, William, et al.
Published: (2025)

Optimal antimatroid sorting
by: Berendsohn, Benjamin Aram
Published: (2025)

Optimally detecting uniformly-distributed $\ell_2$ heavy hitters in data streams
by: Velusamy, Santhoshini, et al.
Published: (2025)

Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings
by: De, Rajat, et al.
Published: (2025)

Color Fault-Tolerant Distance Preservers: Õptimal Size in Conditionally Õptimal Time
by: Parter, Merav, et al.
Published: (2025)

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Nearly Optimal List Labeling
by: Bender, Michael A., et al.
Published: (2024)

Time-Optimal $k$-Server
by: Frei, Fabian, et al.
Published: (2025)

The Role of Commitment in Optimal Stopping
by: Correa, José, et al.
Published: (2025)

Simpler Universally Optimal Dijkstra
by: van der Hoog, Ivor, et al.
Published: (2025)

Engineering Optimal Parallel Task Scheduling
by: Akram, Matthew, et al.
Published: (2024)

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

Optimal Sensitivity Oracle for Steiner Mincut
by: Bhanja, Koustav
Published: (2024)

Asymptotically Optimal Representation of Palindromic Structure
by: Itzhaki, Michael
Published: (2024)

Optimal Distance Labeling for Permutation Graphs
by: Gawrychowski, Paweł, et al.
Published: (2024)

Optimal prefix-suffix queries with applications
by: Pissis, Solon P.
Published: (2024)

Nearly Optimal Internal Dictionary Matching
by: Chen, Jingbang, et al.
Published: (2023)

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

An Optimal Algorithm for Stochastic Vertex Cover
by: Brand, Jan van den, et al.
Published: (2026)

Optimal Non-Oblivious Open Addressing
by: Bender, Michael A., et al.
Published: (2025)

Optimal Static Fully Indexable Dictionaries
by: Liang, Jingxun, et al.
Published: (2025)