Many advanced combinatorial problems have algebraic aspects. Even though the problem formulation can be entirely discrete, significant insight and efficient algorithms might be obtained by applying sophisticated algebraic methods. It is not uncommon that combinatorial problems have simple and elegant formulations, yet they are computationally hard, meaning that the obvious algorithms are useless for their solutions except for very small instances. It can also happen that even though traditional algorithmic approaches are successful, algebraic methods are still more efficient and provide additional insights into a combinatorial problem.
The graph isomorphism problem exemplifies a combinatorial problem where algebraic methods seem to be required for efficient solutions. Interesting for algebraic and combinatorial approaches is also the monomer dimer problem, the counting of matchings in grid graphs, which is of much importance in statistical physics. This proposal studies algorithms based on the scaling method. A particular goal is doing matrix scaling efficiently in parallel, as a tool for approximating the permanent.
This project will look at the computation of all coefficients of graph polynomials for trees and graphs of bounded tree-width. The goal is to compute all coefficients together almost as fast as a single coefficient.
The other main focus of this project is the exploration of variations of the recent faster integer multiplication algorithm and the study of its application to polynomial multiplications and Fourier transforms. One goal is to develop a new algorithm, based on a more discrete method, improving the asymptotic complexity as well as leading to a more practical algorithm for computing products of very long integers.
Integer multiplication is such a fundamental arithmetic task that understanding and improving it is an obvious basic intellectual challenge. Such theoretical goals are foremost in this project. But there could be an impact on the search for Mersenne primes as well as on general purpose computations with high degree polynomials. Other aspects of this research involve topics with applications in Physics and Chemistry.
For many discrete optimization and decision problems, the most natural and obvious algorithms are not good enough. They require too much time, and therefore are only useful for small problem instances. The development of efficient algorithms often requires an in depth study of the mathematical structure of a given problem. For discrete problems, dealing with integers or finite structures like graphs, combinatorics is the main source of tools for such an analysis. But quite often, less obvious algebraic methods provide a path to efficient solutions. Sometimes, no combinatorial method is known to achieve the same efficiency, sometimes the algebraic method is crucial for the discovery process, but can later be replaced by a combinatorial solution. A prototypical problem with efficient algebraic solutions is integer multiplication. School multiplication uses quadratic time. Thus it is very slow for large integers. Fourier transforms allow fast solutions, currently not obtained in any other way. The main and currently unobtainable goal in this area is to design a fastest algorithm and prove that no faster one exist. It turns out that for such efficient algorithms with close to linear running time, the model of computation used to measure the efficiency plays an important role. The supported research has shown, that for a more realistic machine model, the ranking among the best known algorithms changes compared to the usual Turing machine or circuit size model. Another algebraic tool used by this project is the zeta transform with its Möbius inverse. This tool has been used in this project in a new dynamic way to count perfect matchings in a grid, based on a tree decomposition of the grid graph. The algorithm allows to save storage space in exchange for a moderate increase in time. For such hard problems, it is well known, that in practice, storage space is the more serious bottleneck than time. The number of matchings is an important quantity in statistical physics. It can be viewed as the number of embeddings of a pattern graph consisting of a collection of loose edges into a target graph. The project has also designed a polynomial time approximation scheme for the number of embeddings of a large class of different pattern graphs into a random target graph. Graph polynomials are another important class of algebraic tools. The project has studied them in the context of graphs of bounded tree-width. The project has investigated various packing and covering problems, which have applications in many different areas. There is a classical approximation algorithm for k-set packing, that has not been improved for more than twenty years. Shortly, after finding a better approximation algorithm, the PI with a student learned that an algorithm with the same ratio had already been submitted to a conference. Our result is still worthwhile, as its polynomial running time explodes much more moderately, when approaching the optimal approximation ratio. The results of this project have been published in journals and conference proceedings, as well as presented in talks and made available on ArXiv. The research of two PhD students has been supported by this grant.
