Martin Fürer

Department of Computer Science and Engineering
The Pennsylvania State University
W106 Westgate
University Park, PA 16802-6822


Office: W356 Westgate [former 346F IST Building]
Phone: (814) 863-1857
Email: furer AT cse.psu.edu
URL: http://www.cse.psu.edu/~furer
My research Interests
  • Graph Algorithms and Algebraic Graph Theory
  • Width Parameters and Fixed Parameter Tractability
  • Combinatorial and Algebraic Algorithms
  • Approximation Algorithms to Combinatorial Optimization Problems
  • Computational Complexity
  • The Graph Isomorphism Problem
    •
    Some of my most significant research results
    My Faster Integer Multiplication Algorithm (SIAM J. Comp. 39, 3, pp. 979-1005 (2009)).
    Sicomp subscribers click here.
    An earlier version has appeared in the Proceedings of the 39th ACM STOC 2007 conference,
    pp. 57-66 (Best paper award STOC 2007).
    Article on the Faster Integer Multiplication Algorithm (page 1, 2, 3)
    in the German Newspaper DIE ZEIT Nr. 49, November 27, 2008.
    2019: David Harvey and Joris van der Hoeven have found an O(n log n) integer multiplication algorithm (HAL archives-ouvertes).
    E.g., see the reports in ScienceNews and QuantaMagazine.
    Some Publications
    I am on the Editorial Board of
    Journal of Graph Algorithms and Applications and
    Information and Computation
    Teaching:
    Fall 2019: Cmpsc 464, Introduction to the Theory of Computation, 110 Wartik, TR 3:05 - 4:20 pm
    Spring 2019: CSE 597.6, Graph Algorithms Based on Width Parameters, 103 Walker, TR 4:35 - 5:50 pm
    Fall 2018: CSE 565, Algorithm Design and Analysis, EES 118, MW 2:30 - 3:45 pm
    Spring 2018: CSE 564,  Complexity of Combinatorial Problems, 107 EE West, WF 2:30 - 3:45 pm
    Fall 2017: Cmpsc 464,  Introduction to the Theory of Computation, 110 Wartik Lab, TR 3:05 - 4:20 pm
    Spring 2017: Cmpsc 464,  Introduction to the Theory of Computation, 362 Willard, TR 3:05 - 4:20 pm
    Spring 2017: CSE 598.1, Theory Seminar, Earth and Eng Sciences 118, F 12:10 - 1:10 pm
    Fall 2016: CSE 597.2, Graphs of Bounded Widths - Theory and Algorithms, EE West 105, TR 9:05 - 10:20 am
    2015/2016: Sabbatical. (COPPE, Univ. Fed. do Rio de Janeiro; Math, Unive. Fed. do Rio Grande do Sul; Computer Science, ETH-Zürich)
    Office hours:   Tuesday, Thurdsy  4:40 - 5:40 pm
    Link to the EECS Faculty and Staff page, and the CSE Theory page
    Thank you for your interest in Internship positions.
    I have no budget for such positions and I have stopped responding to the requests individually.