This research deals with computationally hard algebraic and combinatorial problems. It investigates variations of the recent faster integer multiplication algorithm and explores its applications to polynomial multiplication and Fourier transforms. Integer multiplication is such a fundamental arithmetic task that understanding and improving it is an obvious basic intellectual challenge. There could be an impact on the search for Mersenne primes. Another major goal is to design and analyze discrete algorithms that are approximating solutions to combinatorial optimization and counting problems. Exact solutions for hard problems are often not feasible. In such cases approximation algorithms are a viable alternative. Of particular interest is the monomer dimer problem, the counting of matchings in grid graphs, which is of much importance in statistical physics.
As a tool for approximating the permanent, this research explores the possibility of doing matrix scaling efficiently in parallel. Such a solution would allow to solve (in NC) the outstanding bipartite matching problem of parallel computing. Even though the matching problem is easy for a sequential machine, it is very challenging to coordinate the many processors of a parallel machine to work simultaneously on the same matching and be efficient. The intellectual merit of this research relies on the fact that many solutions require sophisticated methods of mathematical reasoning. Successful solutions have the potential to enhance the understanding of the possibilities of approximations and parallel computations in general. A broader impact is given by the potential of having a significant effect on a major problem in statistical physics.
