Cover Image

Linear Hashing Is Optimal

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jaber, Michael, Kumar, Vinayak M., Zuckerman, David
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Near-Optimal Averaging Samplers and Matrix Samplers
by: Xun, Zhiyang, et al.
Published: (2024)

Most Juntas Saturate the Hardcore Lemma
by: Kumar, Vinayak M.
Published: (2025)

On Optimal Testing of Linearity
by: Arora, Vipul, et al.
Published: (2024)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Linear Space Streaming Lower Bounds for Approximating CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)

Near Optimal Alphabet-Soundness Tradeoff PCPs
by: Minzer, Dor, et al.
Published: (2024)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
by: Sajith, Thejas Radhika
Published: (2025)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
by: Rohwedder, Lars, et al.
Published: (2024)

Optimal Parallel Basis Finding in Graphic and Related Matroids
by: Khanna, Sanjeev, et al.
Published: (2025)

Near-Optimality for Single-Source Personalized PageRank
by: Jiang, Xinpeng, et al.
Published: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
by: Fei, Yumou, et al.
Published: (2026)

Encoding Co-Lex Orders of Finite-State Automata in Linear Space
by: Becker, Ruben, et al.
Published: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
by: Singer, Noah G., et al.
Published: (2026)

Placing Green Bridges Optimally, with Close-Range Habitats in Sparse Graphs
by: Wallisch, Christian, et al.
Published: (2025)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
by: Jiang, Cheng, et al.
Published: (2026)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
by: Mao, Songtao
Published: (2026)

Explicit Orthogonal Arrays and Universal Hashing with Arbitrary Parameters
by: Harvey, Nicholas, et al.
Published: (2024)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
by: Gaikwad, Ajinkya, et al.
Published: (2025)

The complexity of testing all properties of planar graphs, and the role of isomorphism
by: Basu, Sabyasachi, et al.
Published: (2021)

Parameterized Algorithms for Editing to Uniform Cluster Graph
by: Gaikwad, Ajinkya, et al.
Published: (2024)

Precoloring extension with demands on paths
by: Das, Arun Kumar, et al.
Published: (2025)

k-SUM Hardness Implies Treewidth-SETH
by: Lampis, Michael
Published: (2025)

The Primal Pathwidth SETH
by: Lampis, Michael
Published: (2024)

Minimum Stable Cut and Treewidth
by: Lampis, Michael
Published: (2021)

On the Parameterized Complexity of Min-Sum-Radii
by: Kumar, Pankaj, et al.
Published: (2026)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
by: Kumar, Mrinal, et al.
Published: (2024)

Deterministic factorization of constant-depth algebraic circuits in subexponential time
by: Bhattacharjee, Somnath, et al.
Published: (2025)

Structural Parameterizations for Induced and Acyclic Matching
by: Lampis, Michael, et al.
Published: (2025)

Structural Parameterizations for Two Bounded Degree Problems Revisited
by: Lampis, Michael, et al.
Published: (2023)

Parameterized Capacitated Vertex Cover Revisited
by: Lampis, Michael, et al.
Published: (2026)

Parameterized Maximum Node-Disjoint Paths
by: Lampis, Michael, et al.
Published: (2024)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Parameterized Max Min Feedback Vertex Set
by: Lampis, Michael, et al.
Published: (2023)

Local Enumeration: The Not-All-Equal Case
by: Gurumukhani, Mohit, et al.
Published: (2025)

Parameterized Vertex Integrity Revisited
by: Hanaka, Tesshu, et al.
Published: (2024)

$O(n +f(k))$: Truly Linear FPT
by: Bumpus, Benjamin Merlin, et al.
Published: (2026)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

A Control-Theoretic Perspective on Optimal High-Order Optimization
by: Lin, Tianyi, et al.
Published: (2019)

Streaming Complexity Separations for Dense and Sparse Graphs
by: Liu, Yang P., et al.
Published: (2026)