Buchumschlag

Improved Time-Space Tradeoffs for 3SUM-Indexing

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Dinur, Itai, Golovnev, Alexander
Format:	Preprint
Veröffentlicht:	2025
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

Data Structures Meet Cryptography: 3SUM with Preprocessing
von: Golovnev, Alexander, et al.
Veröffentlicht: (2019)

Preprocessed 3SUM for Unknown Universes with Subquadratic Space
von: Kirkpatrick, Yael, et al.
Veröffentlicht: (2026)

3SUM in Preprocessed Universes: Faster and Simpler
von: Kasliwal, Shashwat, et al.
Veröffentlicht: (2024)

Sumsets, 3SUM, Subset Sum: Now for Real!
von: Fischer, Nick
Veröffentlicht: (2024)

Output-Sparse Matrix Multiplication Using Compressed Sensing
von: Bennett, Huck, et al.
Veröffentlicht: (2025)

Matrix Multiplication Verification Using Coding Theory
von: Bennett, Huck, et al.
Veröffentlicht: (2023)

New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
von: Fischer, Nick, et al.
Veröffentlicht: (2024)

Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics
von: Ameli, Afrouz Jabal, et al.
Veröffentlicht: (2026)

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

Gapped String Indexing in Subquadratic Space and Sublinear Query Time
von: Bille, Philip, et al.
Veröffentlicht: (2022)

On Time-Memory Tradeoffs for Maximal Palindromes with Wildcards and $k$-Mismatches
von: Amir, Amihood, et al.
Veröffentlicht: (2026)

Construction of Sparse Suffix Trees and LCE Indexes in Optimal Time and Space
von: Kosolobov, Dmitry, et al.
Veröffentlicht: (2021)

Online Orthogonal Vectors Revisited
von: Gajulapalli, Karthik, et al.
Veröffentlicht: (2026)

k-SUM Hardness Implies Treewidth-SETH
von: Lampis, Michael
Veröffentlicht: (2025)

The Complexity of Dynamic LZ77 is $\tildeΘ(n^{2/3})$
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Compressed Index with Construction in Compressed Space
von: Kosolobov, Dmitry
Veröffentlicht: (2026)

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Space-Efficient k-Mismatch Text Indexes
von: Kociumaka, Tomasz, et al.
Veröffentlicht: (2025)

Indexing Tries within Entropy-Bounded Space
von: Carfagna, Lorenzo, et al.
Veröffentlicht: (2025)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Dynamic Grammar-Compressed Self-Index in $δ$-Optimal Space
von: Nishimoto, Takaaki, et al.
Veröffentlicht: (2026)

Space-Efficient Text Indexing with Mismatches using Function Inversion
von: Bibbens, Jackson, et al.
Veröffentlicht: (2026)

Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
von: Karczmarz, Adam, et al.
Veröffentlicht: (2025)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
von: Dory, Michal, et al.
Veröffentlicht: (2022)

Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters
von: Woodruff, David P., et al.
Veröffentlicht: (2024)

Space-Efficient Indexes for Uncertain Strings
von: Gabory, Esteban, et al.
Veröffentlicht: (2024)

Settling Time vs. Accuracy Tradeoffs for Clustering Big Data
von: Draganov, Andrew, et al.
Veröffentlicht: (2024)

Balancing Two-Dimensional Straight-Line Programs
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Hamming Distance Oracle
von: Boneh, Itai, et al.
Veröffentlicht: (2024)

Multi-Way Co-Ranking: Index-Space Partitioning of Sorted Sequences Without Merge
von: Joshi, Amit
Veröffentlicht: (2025)

Improved Distance (Sensitivity) Oracles with Subquadratic Space
von: Bilò, Davide, et al.
Veröffentlicht: (2024)

Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors
von: Chatziafratis, Vaggos, et al.
Veröffentlicht: (2023)

Dynamic r-index: An Updatable Self-Index in LCP-bounded Time
von: Nishimoto, Takaaki, et al.
Veröffentlicht: (2025)

DialSort: Non-Comparative Integer Sorting via the Self-Indexing Principle: Architecture, Implementation, and Substrate-Aware Analysis
von: Narvaez, Alexander
Veröffentlicht: (2026)

Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
von: Kempa, Dominik, et al.
Veröffentlicht: (2025)

Improved Space Bounds for Subset Sum
von: Belova, Tatiana, et al.
Veröffentlicht: (2024)

Longest Common Extensions with Wildcards: Trade-off and Applications
von: Bathie, Gabriel, et al.
Veröffentlicht: (2024)

Querying in Constant Expected Time with Learned Indexes
von: Croquevielle, Luis, et al.
Veröffentlicht: (2024)

Deterministic Longest Common Subsequence Approximation in Near-Linear Time
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Improved Tree Sparsifiers in Near-Linear Time
von: Agassy, Daniel, et al.
Veröffentlicht: (2025)