Cover Image

A Framework for Building Data Structures from Communication Protocols

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Andoni, Alexandr, Jiang, Shunhua, Weinstein, Omri
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Hardness Amplification for Dynamic Binary Search Trees
by: Jiang, Shunhua, et al.
Published: (2024)

Improved Sparse Recovery for Approximate Matrix Multiplication
by: Uffenheimer, Yahel, et al.
Published: (2026)

Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems
by: Alman, Josh, et al.
Published: (2024)

On Solving Linear Systems in Sublinear Time
by: Andoni, Alexandr, et al.
Published: (2018)

Efficient Algorithms for Adversarially Robust Approximate Nearest Neighbor Search
by: Andoni, Alexandr, et al.
Published: (2026)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
by: Koh, Zhuan Khye, et al.
Published: (2024)

(Approximate) Matrix Multiplication via Convolutions
by: Uffenheimer, Yahel, et al.
Published: (2025)

Discrepancy Minimization in Input-Sparsity Time
by: Deng, Yichuan, et al.
Published: (2022)

Nearly Optimal Attention Coresets
by: Liberty, Edo, et al.
Published: (2026)

Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
by: Jiang, Shunhua, et al.
Published: (2025)

A Dynamic Low-Rank Fast Gaussian Transform
by: Huang, Baihe, et al.
Published: (2022)

On Sketching Quadratic Forms
by: Andoni, Alexandr, et al.
Published: (2015)

Acceleration Meets Inverse Maintenance: Faster $\ell_{\infty}$-Regression
by: Adil, Deeksha, et al.
Published: (2024)

Dynamic Kernel Graph Sparsifiers
by: Cao, Yang, et al.
Published: (2022)

Training Overparametrized Neural Networks in Sublinear Time
by: Deng, Yichuan, et al.
Published: (2022)

Changing Base Without Losing Pace: A GPU-Efficient Alternative to MatMul in DNNs
by: Ailon, Nir, et al.
Published: (2025)

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

Statistical-Computational Trade-offs for Density Estimation
by: Aamand, Anders, et al.
Published: (2024)

Robust Streaming Against Low-Memory Adversaries
by: Ben-Eliezer, Omri, et al.
Published: (2025)

Approximate counting of permutation patterns
by: Ben-Eliezer, Omri, et al.
Published: (2024)

Recovering Communities in Structured Random Graphs
by: Kapralov, Michael, et al.
Published: (2026)

Succinct Data Structures for Segments
by: Bille, Philip, et al.
Published: (2024)

The Kinetic Hourglass Data Structure for Computing the Bottleneck Distance of Dynamic Data
by: Munch, Elizabeth, et al.
Published: (2025)

Optimal Protocols for 2-Party Contention Resolution
by: Wang, Dingyu
Published: (2024)

A Modern Approach to Electoral Delimitation using the Quadtree Data Structure
by: Kale, Sahil, et al.
Published: (2024)

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
by: Charikar, Moses, et al.
Published: (2024)

Zip-Tries: Simple Dynamic Data Structures for Strings
by: Eppstein, David, et al.
Published: (2025)

Succinct Data Structures for Baxter Permutation and Related Families
by: Chakraborty, Sankardeep, et al.
Published: (2024)

Succinct Data Structure for Graphs with $d$-Dimensional $t$-Representation
by: Balakrishnan, Girish, et al.
Published: (2023)

Compressibility Measures and Succinct Data Structures for Piecewise Linear Approximations
by: Ferragina, Paolo, et al.
Published: (2025)

Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage
by: Balakrishnan, Girish, et al.
Published: (2024)

Tight Static Lower Bounds for Non-Adaptive Data Structures
by: Persiano, Giuseppe, et al.
Published: (2020)

Towards Efficient Data Structures for Approximate Search with Range Queries
by: Kian, Ladan, et al.
Published: (2026)

Engineering Rank/Select Data Structures for Large-Alphabet Strings
by: Arroyuelo, Diego, et al.
Published: (2023)

A Sierpinski Triangle Data Structure for Efficient Array Value Update and Prefix Sum Calculation
by: Harrison, Brent, et al.
Published: (2024)

Structured Downsampling for Fast, Memory-efficient Curation of Online Data Streams
by: Moreno, Matthew Andres, et al.
Published: (2024)

Review of Three Algorithms That Build k-d Trees
by: Brown, Russell A.
Published: (2025)

String Partition for Building Long Burrows-Wheeler Transforms
by: Adler, Enno, et al.
Published: (2024)

Southwest Tree: A Low-Memory Data Structure for Partial Accumulations by Non-Commutative Invertible Operations
by: Papadopoulos, Nicholas J. C.
Published: (2025)

Space-efficient Data Structure for Next/Previous Larger/Smaller Value Queries
by: Jo, Seungbum, et al.
Published: (2022)