Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.

DOI10.4230/LIPIcs.ICALP.2019.8OpenAlexW2964920388MaRDI QIDQ5091156

Amir Abboud

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.8

zbMATH Keywords

dynamic programmingquantum algorithms\(k\)-cliqueset-coverfine-grained complexity\(k\)-SUM3-SUM

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items (1)

A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constrained multilinear detection and generalized graph motifs
• On finding rainbow and colorful paths
• On the complexity of fixed parameter clique and dominating set
• Dynamic parameterized problems
• Strong computational lower bounds via parameterized complexity
• General context-free recognition in less than cubic time
• Which problems have strongly exponential complexity?
• On a class of \(O(n^ 2)\) problems in computational geometry
• Narrow sieves for parameterized paths and packings
• Tight lower bounds for certain parameterized NP-hard problems
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
• Losing Weight by Gaining Edges
• The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems
• Powers of tensors and fast matrix multiplication
• Set Partitioning via Inclusion-Exclusion
• Subcubic Equivalences Between Path, Matrix, and Triangle Problems
• On Problems Equivalent to (min,+)-Convolution
• On Problems as Hard as CNF-SAT
• ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
• SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
• Quantum Speedups for Exponential-Time Dynamic Programming Algorithms
• Exact Weight Subgraphs and the k-Sum Conjecture
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Multiplying matrices faster than coppersmith-winograd
• Graph-Theoretic Concepts in Computer Science
• On the complexity of \(k\)-SAT

This page was built for publication: Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.