Solving Hard Problems via a New Representation Technique

For many NP hard problems like the subset sum problem, syndrome decoding or the computation of a shortest vector in a lattice we basically know algorithms which perform not much better than a simple brute force search over the solution space. This might serve our intuition that we actually expect exponential complexity for NP hard problems in general.
There are few general techniques that help to lower the running time exponent. One of them is the so-called sort and match technique, where the search space is splitted in two parts of equal size. This technique can be used to obtain a time memory tradeoff, e.g. instead of complexity O(2^n) and constant space we obtain O(2^{\frac n 2}) both for time and space.
In 2010, Howgrave-Graham and Joux presented another technique, that we call the representation technique, in the context of solving the subset sum problem. The idea is to represent the solution of a subset sum in an ambiguous way which results in an exponential number of representations. Out of this exponential number, one looks for a special unique solution, again. Surprisingly, this blowup-and-cut strategy helped Howgrave-Graham and Joux to lower the subset sum complexity from O(2^{0.5n}) to O(2^{0.337n}).
Our goal is give a general analysis of the representation technique that allows to apply the technique as a generic algorithmic tool in various contexts. Our first application is an improvement of the best known algorithm for decoding general linear codes, for which we can significantly lower the complexity. Further applications of the representation technique are among others the computation of shortest vectors and a new combinatorial algorithm for a hard problem in cyclic lattices that is underlying the NTRU encryption scheme.

Publications