DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2024.4

Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming

Authors: Josh Alman, Ethan Turok, Hantao Yu, and Hengzhi Zhang

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract

Generalizing work of Künnemann, Paturi, and Schneider [ICALP 2017], we study a wide class of high-dimensional dynamic programming (DP) problems in which one must find the shortest path between two points in a high-dimensional grid given a tensor of transition costs between nodes in the grid. This captures many classical problems which are solved using DP such as the knapsack problem, the airplane refueling problem, and the minimal-weight polygon triangulation problem. We observe that for many of these problems, the tensor naturally has low tensor rank or low slice rank. We then give new algorithms and a web of fine-grained reductions to tightly determine the complexity of these problems. For instance, we show that a polynomial speedup over the DP algorithm is possible when the tensor rank is a constant or the slice rank is 1, but that such a speedup is impossible if the tensor rank is slightly super-constant (assuming SETH) or the slice rank is at least 3 (assuming the APSP conjecture). We find that this characterizes the known complexities for many of these problems, and in some cases leads to new faster algorithms.

Cite as

Josh Alman, Ethan Turok, Hantao Yu, and Hengzhi Zhang. Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{alman_et_al:LIPIcs.ITCS.2024.4,
  author =	{Alman, Josh and Turok, Ethan and Yu, Hantao and Zhang, Hengzhi},
  title =	{{Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{4:1--4:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.4},
  URN =		{urn:nbn:de:0030-drops-195324},
  doi =		{10.4230/LIPIcs.ITCS.2024.4},
  annote =	{Keywords: Fine-grained complexity, Dynamic programming, Least-weight subsequence}
}

Search Results

Documents authored by Turok, Ethan

Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming

Abstract

Cite as

Thanks for your feedback!

Could not send message