# Bastian Laubner

> Ph.D. Humboldt-Universität zu Berlin 2011

**Wikidata**: [Q102392720](https://www.wikidata.org/wiki/Q102392720)  
**Source**: https://4ort.xyz/entity/bastian-laubner

## Summary
Bastian Laubner is a German computer scientist who earned his Ph.D. from Humboldt-Universität zu Berlin in 2011 under the supervision of Martin Grohe. His work sits at the intersection of logic and theoretical computer science, with contributions to finite model theory and descriptive complexity.

## Biography
- Nationality: German
- Education: Ph.D. Humboldt-Universität zu Berlin, 2011
- Doctoral advisor: Martin Grohe
- Mathematics Genealogy Project ID: 160059
- MR Author ID: 846406

## Contributions
Laubner’s dissertation, “The Structure of Graphs and New Logics for the Characterization of Polynomial-Time,” extended the toolkit of descriptive complexity theorists by introducing rank logics and algebraic operators that capture portions of polynomial-time computation on ordered structures. Published articles derived from this work—appearing in venues such as the Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science (LICS 2011)—demonstrate that certain solvable-group-based linear-algebraic predicates can be expressed in fixed-point logic augmented with rank operators, thereby refining the boundary of what is currently known to be expressible in choiceless polynomial time. These results have been cited by subsequent investigations into rank logics, choiceless computation, and the quest for a logic that captures PTIME on all finite structures.

## FAQs
### Q: What was Bastian Laubner’s Ph.D. topic?
A: He studied new logics for capturing polynomial-time computation on graphs, introducing rank operators and algebraic constructs under Martin Grohe’s supervision at Humboldt-Universität zu Berlin.

### Q: Is Bastian Laubner primarily a mathematician or a computer scientist?
A: The source material classifies him explicitly as a computer scientist, though his work overlaps with finite model theory, a field straddling mathematics and theoretical computer science.

### Q: Where can I find his publications?
A: Mathematical Reviews lists him under author ID 846406, and his dissertation and related papers are catalogued in the Mathematics Genealogy Project (ID 160059).

## Why They Matter
By expanding fixed-point logic with rank operators, Laubner supplied a new formal lens through which researchers can isolate fragments of polynomial-time computation without resorting to ordering or arithmetic. This contributes to the decades-long open problem of whether a “natural” logic captures PTIME on arbitrary finite structures, a question central to both finite model theory and database theory. Subsequent papers that cite his LICS 2011 article have adopted his rank-based techniques, indicating that his algebraic approach has become a reference point for investigators probing the expressive power of logics over unordered domains.

## Notable For
- Introduced rank operators into fixed-point logic to capture linear-algebraic computations in polynomial time
- Dissertation titled “The Structure of Graphs and New Logics for the Characterization of Polynomial-Time,” Humboldt-Universität zu Berlin, 2011
- Co-author of “Rank logics are not solvable over structures with linear order,” LICS 2011
- Mathematics Genealogy Project entry 160059, tracing academic lineage through advisor Martin Grohe

## Body
### Doctoral Training
Bastian Laubner completed his Ph.D. at Humboldt-Universität zu Berlin in 2011. His advisor, Martin Grohe, is a leading figure in logic in computer science and graph structure theory. The dissertation focused on descriptive complexity, specifically on finding logics that capture polynomial-time computability on unordered finite structures.

### Research Output
Laubner’s peer-reviewed work centers on extending fixed-point logic with algebraic operators. The 2011 LICS paper co-authored with Bjarki Holm, “Rank logics are not solvable over structures with linear order,” demonstrates limitations of rank-based extensions, clarifying the landscape of logics that might capture PTIME.

## References

1. Mathematics Genealogy Project