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.
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.
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.
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.
WL is at least as powerful as any standard spectral graph
Theorem: The edge colors of WL 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