Martin Fürer
CSE Department
Pennsylvania State University

Some of my most significant research results

Time hierarchy

Theorem: If the maximal running time of a 2-tape Turing machine on inputs of length n is T(n)
(i.e., T(n) is not a crazy function), then there is a decision problem decided by a 2-tape Turing
machine in time O(T(n)), but no 2-tape Turing machine can decide it in time o(T(n)).

Before, the corresponding result has been known for space complexity, but the classical hierarchy
result for time complexity had a factor O(log n) gap.

: The Tight Deterministic Time Hierarchy. STOC : 8-16.:  Data Structures for Distributed Counting. J. Comput. Syst. Sci. 28(2): 231-243 ()

The unfortunate title of the journal publication has been suggested by a referee. It perfectly hides
the result. I am responsible for accepting the suggestion though.

Graph isomorphism

Theorem: There are non-isomorphic graphs of degree 3 with n vertices such that WL[k] does not
detect that they are non-isomorphic for any k=o(n).

Before it has been unknown whether WL[k] can identify all graphs of degree k.
WL[k] has been introduced as a generalization of the Weisfeiler-Lehman edge classification
algorithm, which is WL[2].
WL[k] is the ultimate combinatorial algorithm. For sufficiently large k, every graph property is
discovered by WL[k]. The exact power of WL[k] is captured by a counting logic and by a certain
combinatorial pebble game.

, , :  An optimal lower bound on the number of variables for
graph identifications. Combinatorica 12(4): 389-410 ().

Approximation algorithms, Networking

Theorem: There is a polynomial time approximation algorithm finding a spanning tree whose
degree is at most 1 more than the minimal degree. The same result generalizes to Steiner trees.

This approximation is optimal unless P=NP. Previous approximations were off by a factor log n.

, : Approximating the Minimum Degree Spanning Tree to within
one from the Optimal Degree. SODA : 317-324.
, : Approximating the Minimum-Degree Steiner Tree to within
one of Optimal. J. Algorithms 17(3): 409-423 ().

Spectral graph theory

WL[2] is at least as powerful as any standard spectral graph invariant.

Theorem: The edge colors of WL[2] determine the spectrum of a graph, as well as the projection
lengths of the standard basis vectors into the eigenspaces and the angles between such projections.

The projection lengths are known as angles. The angles between projections have not been studied
before.

: Graph Isomorphism Testing without Numberics for Graphs of Bounded Eigenvalue
Multiplicity. SODA : 624-631.
 Martin Fürer: On the power of combinatorial and spectral invariants. Linear Algebra and its
Applications 432(9): 2373-2380 (2010).

Integer multiplication

Theorem: The product of two integers of length n can be computed by a Boolean circuit of size
n log n exp(O(log*n)). The same function bounds the time of a Turing machine to compute
such products

Before this result, the classical Schönhage-Strassen algorithm running in time O(n log n log log n) has
not been improved for more than 35 years.

: Faster integer multiplication. STOC : 57-66.
: Faster Integer Multiplication. SIAM J. Comput. 39(3): 979-1005 ().