Support
Swiss National Science Foundation (SNSF)
Members
Description
We want to conduct research on algorithmic problems on lattices, which are sets of the form L = {Ax : x ∈ Zn}, where A ∈ Rn*n is a non-singular matrix. Lattices are central in many areas of mathematics and computer science, such as number theory, cryptography or optimization. Although lattices are well-studied, many of the algorithmic questions that are concerned with them remain among the most prominent challenges of algorithms and complexity.
For example, the classical theorem of Minkowski states that the lattice L contains a non-zero lattice point v whose infinity norm is bounded by the n-th root of the lattice determinant. Finding such a vector should not be NP-hard but a good algorithm is still not known.
Another well-known lattice problem is the lattice isomorphism problem: Given two lattices L and L’, does there exist a rotation matrix Q such that QL=L’? If bases, or Gram-matrices of the two lattices are given, how quickly can the isomorphism problem be solved?
Integer programming is the following general lattice problem. Given a matrix B ∈ Zm*n, a vector b ∈ Zm and c ∈ Zn, find max{cTx : Bx = b, x ∈ Zn}. Integer programming is a versatile modeling tool in discrete optimization with many applications in science, engineering or decision making. Also, integer programming poses deep and prominent algorithmic questions. One of the guiding open problems is whether an integer program can be solved in singly exponential time 2O(n). When the number m of rows of the matrix B is small, then integer programming lends itself to dynamic programming approaches. For a long time, the fastest algorithm was the one of Papadimitriou whose running time was roughly of the form (mΔ)O(m^2), where Δ is the largest absolute value of a component of B and b. The applicant, together with Robert Weismantel, achieved the first significant progress in roughly 35 years. The running time of their algorithm is (mΔ)O(m) and this is optimal under a widely believed complexity assumption. But what is the complexity of integer programming with bounds on the variables? This is a very important setting in practice. Here, the running time of the best algorithm is still exponential in m2. This question, among others on integer programming, currently receive considerable attention.
Our research group is among the best qualified to achieve considerable advance in this domain. We propose a two-tier research program. A) On the one hand, we develop novel algorithms for general and block-structured integer programming problems, like integer programs with few inequality constraints and upper bounds, or block-structured integer programs. This setting seems to be suitable for novel algorithms based on proximity and dynamic programming. We aim at optimal algorithms with respect to the Exponential Time Hypothesis. A benchmark problem is for example whether general integer programming as described above can be solved in (mΔ)O(m) time in the presence of upper bounds 0 <= x <= u on the variables. B) On the other hand, we aim at faster algorithms for visible classical problems on lattices in full generality and in special parameterized settings. For example, we consider the lattice isomorphism problem and search for a single exponential time algorithm. In the special setting of deciding whether a lattice is isomorphic to Zn, we have more structure and aim at subexponential time algorithms.