Martin Fürer
Location: (University Park, PA (State College))
Personal Research Web Page: http://www.cse.psu.edu/~furer/
Keywords: Approximation Algorithms, The Graph Isomorphism Problem, Algebraic Algorithms, Computational Complexity, Graph Algorithms, Fixed Parameter Tractable Problems, Computational Complexity
Posted on: Tuesday, May 18th, 2010
Broad Research Area: Theory / Algorithms
Research Interests:
My best known early result is the tight deterministic time hierarchy. It says that as soon as we allow a k-tape Turing machine to run a little longer, it can tackle a more di?cult problem. The classical hierarchy result has only guaranteed such a performance increase, when the time was multiplied by a factor of log n.
In Approximation Algorithms, my best results are on “Approximating Maximum Independent Set in Bounded Degree Graphs” with Piotr Berman and “Approximation of k-Set Cover by Semi-Local Optimization” with Rong-chii Duh. With Shiva Kasiviswanathan, I have the fastest approximation algorithm for the permanent of random 0-1 matrices.
On the graph isomorphism problem, I have obtained “Normal Forms for Trivalent Graphs and Graphs of Bounded Valence” with Walter Schnyder and Ernst Specker, I have shown how to do “Graph Isomorphism Testing without Numerics for Graphs of Bounded
Eigenvalue Multiplicity” and most importantly, I have shown the limits of combinatorial methods in “An Optimal Lower Bound on the Number of Variables for Graph Identification” with Jin-Yi Cai and Neil Immerman. On the other hand, I have shown that combinatorial invariants are at least as powerful as any spectral invariants.
On fixed parameter tractable problems, I have by far the fastest algorithm for computing the characteristic polynomial of bounded degree graphs. I also have results on moderately exponential time algorithms for NP-hard problems.
In the area of algebraic algorithms, I have found the fastest integer multiplication algorithm. Still, I would like to further improve its asymptotic running time.
