Martin Fürer

CSE Department

Pennsylvania State University

**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.

Martin Fürer: The Tight Deterministic Time Hierarchy.
STOC
1982: 8-16.

Martin Fürer: Data Structures for
Distributed Counting. *J. Comput. Syst. Sci. 28(2)**:* 231-243 (1984).

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.

**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.

Jin-yi Cai,
Martin Fürer, Neil Immerman: An optimal lower bound on
the number of variables for

graph identifications. *Combinatorica 12(4)**:* 389-410 (1992).

**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.

Martin Fürer,
Balaji Raghavachari: Approximating the Minimum Degree
Spanning Tree to within

one from the Optimal Degree. SODA 1992: 317-324.

Martin Fürer, Balaji Raghavachari: Approximating the Minimum-Degree Steiner Tree to within

one of Optimal. J. Algorithms 17(3): 409-423 (1994).

one from the Optimal Degree. SODA 1992: 317-324.

Martin Fürer, Balaji Raghavachari: Approximating the Minimum-Degree Steiner Tree to within

one of Optimal. J. Algorithms 17(3): 409-423 (1994).

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.

Martin Fürer: Graph Isomorphism Testing without
Numberics for Graphs of Bounded Eigenvalue

Multiplicity. SODA 1995: 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.

Martin Fürer: Faster Integer Multiplication.*SIAM J. Comput. 39(3)**: *979-1005 (2009).

Multiplicity. SODA 1995: 624-631.

Martin Fürer: On the power of combinatorial and spectral invariants.

Applications

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.

Martin Fürer: Faster Integer Multiplication.