# SETH-Based Lower Bounds for Subset Sum and Bicriteria Path

arXiv: https://arxiv.org/abs/1704.04546 · HTML: https://mlsanity.com/paper/1704.04546/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Apr 2017.

## Built on by (most cited first, 2 of 2)

- [Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods](https://mlsanity.com/paper/2202.08907/) (2022)
- [On the Computational Hardness of Transformers](https://mlsanity.com/paper/2603.11332/) (2026)

## Abstract (arXiv)

Subset-Sum and k-SAT are two of the most extensively studied problems in computer science, and conjectures about their hardness are among the cornerstones of fine-grained complexity. One of the most intriguing open problems in this area is to base the hardness of one of these problems on the other. Our main result is a tight reduction from k-SAT to Subset-Sum on dense instances, proving that Bellman's 1962 pseudo-polynomial O*(T)-time algorithm for Subset-Sum on n numbers and target T cannot be improved to time T1-varepsilon· 2o(n) for any varepsilon>0, unless the Strong Exponential Time Hypothesis (SETH) fails. This is one of the strongest known connections between any two of the core problems of fine-grained complexity. As a corollary, we prove a "Direct-OR" theorem for Subset-Sum under SETH, offering a new tool for proving conditional lower bounds: It is now possible to assume that deciding whether one out of N given instances of Subset-Sum is a YES instance requires time (N T)1-o(1). As an application of this corollary, we prove a tight SETH-based lower bound for the classical Bicriteria s,t-Path problem, which is extensively studied in Operations Research. We separate its complexity from that of Subset-Sum: On graphs with m edges and edge lengths bounded by L, we show that the O(Lm) pseudo-polynomial time algorithm by Joksch from 1966 cannot be improved to tildeO(L+m), in contrast to a recent improvement for Subset Sum (Bringmann, SODA 2017).