Conditional lower bounds for space/time tradeoffs

DOI10.1007/978-3-319-62127-2_36zbMath1457.68115arXiv1706.05847OpenAlexW3106319426MaRDI QIDQ2405302

Ely Porat, Moshe Lewenstein, Isaac Goldstein, Tsvi Kopelowitz

Publication date: 22 September 2017

Full work available at URL: https://arxiv.org/abs/1706.05847

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (9)

General space-time tradeoffs via relational queries ⋮ Unnamed Item ⋮ Gapped indexing for consecutive occurrences ⋮ Dynamic and internal longest common substring ⋮ Range closest-pair search in higher dimensions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Solving string problems on graphs using the labeled direct product

This page was built for publication: Conditional lower bounds for space/time tradeoffs