[Colloq] Talk by Martin Furer, Monday, February 4

[Rachel Kalweit]

College of Computer and Information Science Colloquium

Presents:
Martin Fürer

Who will speak on:
“Faster Integer Multiplication”

Monday, February 4, 2008
12:00 pm
366 West Village H
Northeastern University

Abstract:
For more than 35 years, the fastest known method for integer multiplication has been the Schönhage-Strassen algorithm running in time O(n log n log log n). Under certain restrictive conditions, there is a corresponding Ω(n log n) lower bound. All this time, the prevailing conjecture has been that the complexity of an optimal integer multiplication algorithm is of order n log n. We present a major step towards closing the gap from above by presenting an algorithm running in time n log n exp(O(log* n)). The running time bound holds for multi-tape Turing machines. The same bound is valid for the size of boolean circuits. 

Brief Biography:
Martin Fürer received his Ph.D. in mathematics from the ETH Zürich in 1978, with the Silver Medal of the ETH. He has held positions at the Universities of Washington, Edinburgh, Tübingen, and Zürich. While at Penn State, he has held visiting research positions at Princeton University, the Forschungsinstitut für Mathematik, ETH Zürich (Summer 1996), and the Max Planck Institute for Computer Science, Saarbrücken (Summer 1999). He also has been a visiting professor at the Department of Mathematics, ETH Zürich (Sabbatical 2001-2002). In 2007, Dr. Fürer received best paper awards at SOFSEM 2007 (with Shiva P. Kasiviswanathan) for the paper, Exact Max 2-Sat: Easier and Faster, and at STOC 2007 for his Faster Integer Multiplication. Fürer's research is in discrete algorithms and complexity. One of his early results is the tight deterministic time hierarchy. Later, he has worked on the graph isomorphism problem, other graph algorithms, and computational complexity. Currently, he mainly designs algorithms and investigates the complexity of approximating NP-hard combinatorial optimization problems, focusing on the permanent and other counting problems. Martin Fürer is a member of the editorial board for the electronic Journal of Graph Algorithms and Applications (www.cs.brown.edu/publications/jgaa) . 

Host: Karl Lieberherr