# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

__Mittagsseminar Talk Information__ | |

**Date and Time**: Tuesday, February 15, 2005, 12:15 pm

**Duration**: This information is not available in the database

**Location**: This information is not available in the database

**Speaker**: Bartosz Przydatek

## Solving Medium-Density Subset Sum Problems in Expected Polynomial Time

The subset sum problem (*SSP*) (given *n* numbers and a target bound *B*,
find a subset of the numbers summing to *B*), is a classic *NP*-hard problem.
The hardness of *SSP* varies greatly with the density of the problem.
In particular, when *m*, the logarithm of the largest input number,
is at least *c*n* for some constant *c*, the problem can be solved by a
reduction to finding a short vector in a lattice. On the other hand, when
*m=O(log n)* the problem can be solved in polynomial time using dynamic
programming or some other algorithms especially designed for dense
instances. However, as far as we are aware, all known algorithms for
dense SSP take at least *Ω(2*^{m}) time, and no polynomial time
algorithm is known which solves *SSP* when *m=ω(log n)* (and *m=o(n)*).

We present an expected polynomial time algorithm for solving uniformly
random instances of the subset sum problem over the domain *Z*_{M}, with
*m=O((log n)*^{2}). To the best of our knowledge, this is the first algorithm
working efficiently beyond the magnitude bound of *O(log n)*, thus
narrowing the interval of hard-to-solve *SSP* instances.

(Joint work with Abie Flaxman)

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login