Martin Grohe

Last updated

Martin Grohe (born 1967) [1] is a German mathematician and computer scientist known for his research on parameterized complexity, mathematical logic, finite model theory, the logic of graphs, database theory, and descriptive complexity theory. He is a University Professor of Computer Science at RWTH Aachen University, where he holds the Chair for Logic and Theory of Discrete Systems. [2]

Contents

Education

Grohe earned his doctorate (dr. rer. nat.) at the University of Freiburg in 1994. His dissertation, The Structure of Fixed-Point Logics, was supervised by Heinz-Dieter Ebbinghaus. [3] After postdoctoral research at the University of California, Santa Cruz and Stanford University, he earned his habilitation at the University of Freiburg in 1998. [4]

Books

Grohe is the author of Descriptive Complexity, Canonisation, and Definable Graph Structure Theory (Lecture Notes in Logic 47, Cambridge University Press, 2017). [5] In 2011, Grohe and Johann A. Makowsky published as editors the 558th proceedings of the AMS-ASL special session on Model Theoretic Methods in Finite Combinatorics, which was held on January 5-8 2009 in Washington, DC. With Jörg Flum, he is the co-author of Parameterized Complexity Theory (Springer, 2006). [6]

Recognition

Grohe won the Heinz Maier–Leibnitz Prize awarded by the German Research Foundation in 1999. [4] He was elected as an ACM Fellow in 2018 for "contributions to logic in computer science, database theory, algorithms, and computational complexity". [7]

Related Research Articles

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics and from evolutionary biology to computer science.

<span class="mw-page-title-main">Discrete mathematics</span> Study of discrete mathematical structures

Discrete mathematics is the study of mathematical structures that can be considered "discrete" rather than "continuous". Objects studied in discrete mathematics include integers, graphs, and statements in logic. By contrast, discrete mathematics excludes topics in "continuous mathematics" such as real numbers, calculus or Euclidean geometry. Discrete objects can often be enumerated by integers; more formally, discrete mathematics has been characterized as the branch of mathematics dealing with countable sets. However, there is no exact definition of the term "discrete mathematics".

<span class="mw-page-title-main">Ronald Graham</span> American mathematician (1935–2020)

Ronald Lewis Graham was an American mathematician credited by the American Mathematical Society as "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years". He was president of both the American Mathematical Society and the Mathematical Association of America, and his honors included the Leroy P. Steele Prize for lifetime achievement and election to the National Academy of Sciences.

Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not vary smoothly in this way, but have distinct, separated values. Discrete mathematics, therefore, excludes topics in "continuous mathematics" such as calculus and analysis.

In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. The first systematic work on parameterized complexity was done by Downey & Fellows (1999).

<span class="mw-page-title-main">Neil Immerman</span> American theoretical computer scientist

Neil Immerman is an American theoretical computer scientist, a professor of computer science at the University of Massachusetts Amherst. He is one of the key developers of descriptive complexity, an approach he is currently applying to research in model checking, database theory, and computational complexity theory.

Finite model theory is a subarea of model theory. Model theory is the branch of logic which deals with the relation between a formal language (syntax) and its interpretations (semantics). Finite model theory is a restriction of model theory to interpretations on finite structures, which have a finite universe.

In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI. Ladner's theorem, shown in 1975 by Richard E. Ladner, is a result asserting that, if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete. Since it is also true that if NPI problems exist, then P ≠ NP, it follows that P = NP if and only if NPI is empty.

In mathematical logic, monadic second-order logic (MSO) is the fragment of second-order logic where the second-order quantification is limited to quantification over sets. It is particularly important in the logic of graphs, because of Courcelle's theorem, which provides algorithms for evaluating monadic second-order formulas over graphs of bounded treewidth. It is also of fundamental importance in automata theory, where the Büchi-Elgot-Trakhtenbrot theorem gives a logical characterization of the regular languages.

In computer science, a kernelization is a technique for designing efficient algorithms that achieve their efficiency by a preprocessing stage in which inputs to the algorithm are replaced by a smaller input, called a "kernel". The result of solving the problem on the kernel should either be the same as on the original input, or it should be easy to transform the output on the kernel to the desired output for the original problem.

András Hajnal was a professor of mathematics at Rutgers University and a member of the Hungarian Academy of Sciences known for his work in set theory and combinatorics.

<span class="mw-page-title-main">Heinz-Dieter Ebbinghaus</span> German mathematician and logician

Heinz-Dieter Ebbinghaus is a German mathematician and logician. He received his PhD in 1967 at the University of Münster under Hans Hermes and Dieter Rödding.

In graph theory, a Trémaux tree of an undirected graph is a type of spanning tree, generalizing depth-first search trees. They are defined by the property that every edge of connects an ancestor–descendant pair in the tree. Trémaux trees are named after Charles Pierre Trémaux, a 19th-century French author who used a form of depth-first search as a strategy for solving mazes. They have also been called normal spanning trees, especially in the context of infinite graphs.

In the study of graph algorithms, Courcelle's theorem is the statement that every graph property definable in the monadic second-order logic of graphs can be decided in linear time on graphs of bounded treewidth. The result was first proved by Bruno Courcelle in 1990 and independently rediscovered by Borie, Parker & Tovey (1992). It is considered the archetype of algorithmic meta-theorems.

<span class="mw-page-title-main">Johann Makowsky</span>

Johann (János) A. Makowsky is a Hungarian born and naturalized Swiss mathematician who works in mathematical logic and the logical foundations of computer science and combinatorics. He studied at ETH Zurich from 1967–73. He was a student in Zürich of Ernst Specker and Hans Läuchli in mathematical logic,, of Beno Eckmann and Volker Strassen (Algorithmics), and in Warsaw of Andrzej Mostowski and Witek Marek, where he spent 1972 as an exchange student. Makowsky held visiting positions at the Banach Center in Warsaw (Poland), Stanford University (USA), Simon Fraser University (Canada), University of Florence (Italy), MIT (USA), Lausanne University and ETH Zurich (Switzerland). He held regular positions at the Free University of Berlin and the Technion – Israel Institute of Technology where he was a full professor.

In mathematical logic and computer science, two-variable logic is the fragment of first-order logic where formulae can be written using only two different variables. This fragment is usually studied without function symbols.

In mathematical logic, a fragment of a logical language or theory is a subset of this logical language obtained by imposing syntactical restrictions on the language. Hence, the well-formed formulae of the fragment are a subset of those in the original logic. However, the semantics of the formulae in the fragment and in the logic coincide, and any formula of the fragment can be expressed in the original logic.

In the mathematical fields of graph theory and finite model theory, the logic of graphs deals with formal specifications of graph properties using sentences of mathematical logic. There are several variations in the types of logical operation that can be used in these sentences. The first-order logic of graphs concerns sentences in which the variables and predicates concern individual vertices and edges of a graph, while monadic second-order graph logic allows quantification over sets of vertices or edges. Logics based on least fixed point operators allow more general predicates over tuples of vertices, but these predicates can only be constructed through fixed-point operators, restricting their power.

Algorithms and Combinatorics is a book series in mathematics, and particularly in combinatorics and the design and analysis of algorithms. It is published by Springer Science+Business Media, and was founded in 1987.

References

  1. Birth year from German National Library catalog entry, retrieved 2018-12-08.
  2. Dr. rer. nat., Universitätsprofessor Martin Grohe, RWTH Aachen University , retrieved 2018-12-08
  3. Martin Grohe at the Mathematics Genealogy Project
  4. 1 2 Martin Grohe, 1999 Heinz Maier-Leibnitz Prize, University of Freiburg , retrieved 2021-08-08
  5. Review of Descriptive Complexity, Canonisation, and Definable Graph Structure Theory:
  6. Reviews of Parameterized Complexity Theory:
  7. ACM Recognizes 2017 Fellows for Making Transformative Contributions and Advancing Technology in the Digital Age, Association for Computing Machinery, December 11, 2017