Martin Furer

Dr. 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 a best paper award at SOFSEM 2007 (with Shiva P. Kasiviswanathan), and received another one at STOC 2007 for his Faster Integer Multiplication.

Dr. 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. Dr. Fürer is a member of the editorial board for the electronic Journal of Graph Algorithms and Applications (www.cs.brown.edu/ publications/jgaa).

Research Interests:

Efficient Discrete Algorithms, Approximation Algorithms, Computational Complexity, The Graph Isomorphism Problem

Selected Publications:

1. Fürer, M., S. Kasiviswanathan. August 2007. Spanners for Geometric Intersection Graphs. Proceedings of the Tenth Workshop on Algorithms and Data Structures (WADS 2007). Springer-Verlag LNCS 4619:312-324. Halifax, Canada.
   
2. Fürer, M. June 2007. Faster Integer Multiplication. Proceedings of the Thirty-Ninth ACM Symposium on Theory of Computing (STOC 2007). pp. 57-66. San Diego, CA. (Best Paper Award)
   
3. Fürer, M. July 2001. Weisfeiler-Lehman Refinement Requires at Least a Linear Number of Iterations. Proceedings of the Twenty-Eighth International Colloquium on Automata, Languages and Programming (ICALP 2001). Springer-Verlag LNCS 2076:322-333. Crete, Greece.
4. Fürer, M. May 2000. Approximating Permanents of Complex Matrices. Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC 2000). pp. 667-669. Portland, OR.
   
5. Duh, R.-C., M. Fürer. May 1997. Approximation of k-Set Cover by Semi-Local Optimization. Proceedings of STOC 97. pp. 256-264. El Paso, TX.