AF: Medium: Algorithms Based on Algebraic and Combinatorial Methods

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.