<p>Definitely still active in the area of Weisfeiler-Leman-style algorithms for isomorphism problems such as Graph Isomorphism.  The connection with logic was first (I believe) made in <a href="https://link.springer.com/chapter/10.1007/978-1-4612-4478-3_5" rel="noreferrer">Immerman-Lander</a> and <a href="https://doi.org/10.1007/BF01305232" rel="noreferrer">Cai-Fürer-Immerman</a>. Very recently adapted to Group Isomorphism [<a href="https://doi.org/10.1145/3373718.3394786" rel="noreferrer">Brachter-Schweitzer</a>]. Certain logics are equivalent in their power to distinguish graphs (resp. groups, etc.) to the WL family of algorithms.</p>
<p>Properties of Weisfeiler-Leman, and hence, equivalently, of the corresponding logics, are still an active area of research, e.g. see <a href="https://dl.acm.org/doi/abs/10.1145/3436980.3436982" rel="noreferrer">these</a> <a href="https://arxiv.org/abs/1904.07216" rel="noreferrer">few</a> <a href="https://arxiv.org/abs/1908.05268" rel="noreferrer">papers</a> from the past few years as well as <a href="https://www.iti.zcu.cz/wl2018/" rel="noreferrer">this conference on its 50th anniversary</a>.</p>
<p>Also, a polynomial-time graph canonization algorithm would solve the long-standing question of a logic that captures <span class="math-container">$\mathsf{P}$</span>.</p>

CC BY-SA 4.0
2020-11-28T09:31:28.553Z
Perhaps also [this](https://www.cs.upc.edu/~atserias/papers/quantumisomorphism/quantumisomorphisms.pdf).
Yuval Filmus
CC BY-SA 4.0
2020-11-27T17:13:03.160Z
2020-11-27T17:13:03.160Z
Joshua Grochow
<p>Since Immerman's book was published, a few other books have come out.. (But they may have &quot;Finite Model Theory&quot; in their titles.)</p>
<p>&quot;<em>Lot of hope at the beginning, but then <strong>not</strong> much happened</em>&quot;
--- this has been the case with several approaches in Computational Complexity.. So we cannot (or should not) single out Descriptive Complexity for blaming.</p>
<p>In terms of its application:</p>
<p>&quot;<em>Consider Problem <span class="math-container">$A$</span>.. We show that it can be expressed in Logic <span class="math-container">$B$</span>.. And hence, it follows that its computational (or approximation) complexity is <span class="math-container">$C$</span></em>&quot; --- How many <strong>new</strong> results have been published along these lines? <span class="math-container">$~$</span> <strong>Not</strong> many, to my knowledge.. (But I'm happy to be proven wrong.)</p>

CC BY-SA 4.0
2021-08-23T20:49:19.190Z
2021-08-23T21:16:03.483Z
2021-08-23T21:16:03.483Z
Shuxue Jiaoshou
<p>I also have the impression that Descriptive Complexity is a less active area of research nowadays. Nevertheless, there are some topics in which people are still active:</p>
<ol>
<li><strong>Rank logics:</strong></li>
</ol>
<ul>
<li><a href="https://arxiv.org/abs/1503.05423" rel="nofollow noreferrer">Rank Logic is Dead, Long Live Rank Logic! by Grädel and Pakusa</a></li>
<li><a href="https://arxiv.org/abs/1804.02939" rel="nofollow noreferrer">Symmetric Circuits for Rank Logic by Dawar and Wilsenach</a></li>
<li><a href="https://arxiv.org/abs/2104.12999" rel="nofollow noreferrer">Separating Rank Logic from Polynomial Time
by Lichter</a></li>
</ul>
<ol start="2">
<li><strong>Choiceless Polynomial Time:</strong></li>
</ol>
<ul>
<li><a href="https://arxiv.org/abs/2010.12182" rel="nofollow noreferrer">Canonization for Bounded and Dihedral Color Classes in Choiceless Polynomial Time by Lichter and Schweitzer</a></li>
<li><a href="https://drops.dagstuhl.de/opus/volltexte/2019/10975/" rel="nofollow noreferrer">Choiceless Logarithmic Space by Grädel and Schalthöfer</a></li>
<li><a href="https://www.sciencedirect.com/science/article/pii/S0168007207001066?via%3Dihub" rel="nofollow noreferrer">Choiceless polynomial time, counting and the Cai–Fürer–Immerman graphs by Dawar et al.</a></li>
</ul>
<ol start="3">
<li><strong>Dynamic Complexity:</strong></li>
</ol>
<ul>
<li><a href="https://arxiv.org/abs/1910.06004" rel="nofollow noreferrer">Dynamic Complexity of Parity Exists Queries by Vortmeier and Zeume</a></li>
<li><a href="https://dl.acm.org/doi/abs/10.1145/3212685" rel="nofollow noreferrer">Reachability Is in DynFO by Datta, Kulkarni, Mukherjee, Schwentick and Zeume</a></li>
<li><a href="https://d-nb.info/110226881X/34" rel="nofollow noreferrer">PHD thesis of Thomas Zeume</a></li>
</ul>
<ol start="4">
<li><strong>Other interesting things:</strong></li>
</ol>
<ul>
<li><a href="https://ieeexplore.ieee.org/abstract/document/8005150" rel="nofollow noreferrer">Descriptive Complexity for Counting Complexity Classes by Arenas Muñoz and Riveros</a></li>
<li><a href="https://arxiv.org/abs/2003.00644" rel="nofollow noreferrer">Descriptive complexity of real computation and probabilistic independence logic by Hannula, Kontinen, Van den Bussche and Virtema</a></li>
<li><a href="https://link.springer.com/chapter/10.1007/978-3-662-59533-6_13" rel="nofollow noreferrer">Descriptive Complexity of Deterministic Polylogarithmic Time by Ferrarotti et al</a></li>
<li><a href="https://ieeexplore.ieee.org/abstract/document/8785792" rel="nofollow noreferrer">On the Power of Symmetric Linear Programs by Atserias, Dawar and Ochremiak</a></li>
<li><a href="https://arxiv.org/abs/2006.07067" rel="nofollow noreferrer">Traversal-invariant characterizations of logarithmic space by Bhaskar, Lindell and Weinstein</a></li>
</ul>
<p>The list is not supposed to be complete. Just giving you a glimpse on what kind of problems are people looking at.</p>

CC BY-SA 4.0
2020-11-28T09:31:53.853Z
Perhaps also [this](https://www.cs.upc.edu/~atserias/papers/symmetric-lps/symmetric-lps.pdf).
Yuval Filmus
CC BY-SA 4.0
2021-04-28T15:46:08.447Z
An important paper just appeared on arxiv (accepted to LICS 2021): Separating Rank Logic from Polynomial Time. I updated the references.
Bartosz Bednarczyk
CC BY-SA 4.0
2023-11-30T17:01:11.613Z
From 2008: https://doi.org/10.1016/j.apal.2007.11.011 Dawar, Richerby, & Rossman Choiceless polynomial time, counting and the Cai–Fürer–Immerman graphs.
Joshua Grochow
CC BY-SA 4.0
2020-11-27T17:03:37.033Z
2023-12-01T08:21:29.623Z
2023-12-01T08:21:29.623Z
Bartosz Bednarczyk
<p>I recently started reading about Descriptive Complexity, the branch of Complexity Theory studying the logic languages needed to express complexity classes. The main milestone in the area seems to be Neil Immerman's book, but this is already quite old. Seems like this line of research is dead. Is this the case? If so, why?</p>

CC BY-SA 4.0
2020-11-27T17:15:08.373Z
While some questions are particular to descriptive complexity, for many other descriptive complexity simply offers an alternative characterization of other things (e.g. Fagin's Theorem). That alternative characterization can be a useful viewpoint for some people to make progress or ask interesting questions that wouldn't have been thought of with a different viewpoint. So regardless of it is dead or not as a research area in & of itself, it could still be useful to learn that viewpoint.
Joshua Grochow
CC BY-SA 4.0
2020-11-29T20:24:35.133Z
Isn't there a conference every year on the descriptional complexity of formal systems (DCFS) or is this something different from what you meant?  Link: http://www.informatik.uni-giessen.de/dcfs/proceedings.html
Michael Wehar
CC BY-SA 4.0
2020-11-30T21:40:17.017Z
I believe that descriptional complexity and descriptive complexity are different branches of mathematics. Descriptional complexity is about finding the bounds on the size of an automaton recognizing some language while descriptive complexity is about finding a logic that characterizes some complexity class.
Bartosz Bednarczyk
<cc.complexity-theory><big-picture><descriptive-complexity>
Is Descriptive Complexity dead?
Noel Arteche
# Is Descriptive Complexity dead?

(Asked by: username_0 on 2020-11-27)

I recently started reading about Descriptive Complexity, the branch of Complexity Theory studying the logic languages needed to express complexity classes. The main milestone in the area seems to be Neil Immerman's book, but this is already quite old. Seems like this line of research is dead. Is this the case? If so, why?

**Tags:** cc.complexity-theory, big-picture, descriptive-complexity
> **Comments:**
> **username_1**: While some questions are particular to descriptive complexity, for many other descriptive complexity simply offers an alternative characterization of other things (e.g. Fagin's Theorem). That alternative characterization can be a useful viewpoint for some people to make progress or ask interesting questions that wouldn't have been thought of with a different viewpoint. So regardless of it is dead or not as a research area in & of itself, it could still be useful to learn that viewpoint.  
> **username_2**: Isn't there a conference every year on the descriptional complexity of formal systems (DCFS) or is this something different from what you meant?  Link: http://www.informatik.uni-giessen.de/dcfs/proceedings.html  
> **username_3**: I believe that descriptional complexity and descriptive complexity are different branches of mathematics. Descriptional complexity is about finding the bounds on the size of an automaton recognizing some language while descriptive complexity is about finding a logic that characterizes some complexity class.  

---

## 3 answers

### Answer by username_3 on 2020-11-27. Score: 30 | Accepted answer

I also have the impression that Descriptive Complexity is a less active area of research nowadays. Nevertheless, there are some topics in which people are still active:

1. **Rank logics:**

* [Rank Logic is Dead, Long Live Rank Logic! by Grädel and Pakusa](https://arxiv.org/abs/1503.05423)
* [Symmetric Circuits for Rank Logic by Dawar and Wilsenach](https://arxiv.org/abs/1804.02939)
* [Separating Rank Logic from Polynomial Time
  by Lichter](https://arxiv.org/abs/2104.12999)

2. **Choiceless Polynomial Time:**

* [Canonization for Bounded and Dihedral Color Classes in Choiceless Polynomial Time by Lichter and Schweitzer](https://arxiv.org/abs/2010.12182)
* [Choiceless Logarithmic Space by Grädel and Schalthöfer](https://drops.dagstuhl.de/opus/volltexte/2019/10975/)
* [Choiceless polynomial time, counting and the Cai–Fürer–Immerman graphs by Dawar et al.](https://www.sciencedirect.com/science/article/pii/S0168007207001066?via%3Dihub)

3. **Dynamic Complexity:**

* [Dynamic Complexity of Parity Exists Queries by Vortmeier and Zeume](https://arxiv.org/abs/1910.06004)
* [Reachability Is in DynFO by Datta, Kulkarni, Mukherjee, Schwentick and Zeume](https://dl.acm.org/doi/abs/10.1145/3212685)
* [PHD thesis of Thomas Zeume](https://d-nb.info/110226881X/34)

4. **Other interesting things:**

* [Descriptive Complexity for Counting Complexity Classes by Arenas Muñoz and Riveros](https://ieeexplore.ieee.org/abstract/document/8005150)
* [Descriptive complexity of real computation and probabilistic independence logic by Hannula, Kontinen, Van den Bussche and Virtema](https://arxiv.org/abs/2003.00644)
* [Descriptive Complexity of Deterministic Polylogarithmic Time by Ferrarotti et al](https://link.springer.com/chapter/10.1007/978-3-662-59533-6_13)
* [On the Power of Symmetric Linear Programs by Atserias, Dawar and Ochremiak](https://ieeexplore.ieee.org/abstract/document/8785792)
* [Traversal-invariant characterizations of logarithmic space by Bhaskar, Lindell and Weinstein](https://arxiv.org/abs/2006.07067)

The list is not supposed to be complete. Just giving you a glimpse on what kind of problems are people looking at.

> **Comments:**
> **username_4**: Perhaps also [this](https://www.cs.upc.edu/~atserias/papers/symmetric-lps/symmetric-lps.pdf).  
> **username_3**: An important paper just appeared on arxiv (accepted to LICS 2021): Separating Rank Logic from Polynomial Time. I updated the references.  
> **username_1**: From 2008: https://doi.org/10.1016/j.apal.2007.11.011 Dawar, Richerby, & Rossman Choiceless polynomial time, counting and the Cai–Fürer–Immerman graphs.  

---

### Answer by username_1 on 2020-11-27. Score: 15

Definitely still active in the area of Weisfeiler-Leman-style algorithms for isomorphism problems such as Graph Isomorphism. The connection with logic was first (I believe) made in [Immerman-Lander](https://link.springer.com/chapter/10.1007/978-1-4612-4478-3_5) and [Cai-Fürer-Immerman](https://doi.org/10.1007/BF01305232). Very recently adapted to Group Isomorphism [[Brachter-Schweitzer](https://doi.org/10.1145/3373718.3394786)]. Certain logics are equivalent in their power to distinguish graphs (resp. groups, etc.) to the WL family of algorithms.

Properties of Weisfeiler-Leman, and hence, equivalently, of the corresponding logics, are still an active area of research, e.g. see [these](https://dl.acm.org/doi/abs/10.1145/3436980.3436982) [few](https://arxiv.org/abs/1904.07216) [papers](https://arxiv.org/abs/1908.05268) from the past few years as well as [this conference on its 50th anniversary](https://www.iti.zcu.cz/wl2018/).

Also, a polynomial-time graph canonization algorithm would solve the long-standing question of a logic that captures $\mathsf{P}$.

> **Comments:**
> **username_4**: Perhaps also [this](https://www.cs.upc.edu/~atserias/papers/quantumisomorphism/quantumisomorphisms.pdf).  

---

### Answer by username_5 on 2021-08-23. Score: 2

Since Immerman's book was published, a few other books have come out.. (But they may have "Finite Model Theory" in their titles.)

"*Lot of hope at the beginning, but then **not** much happened*"
--- this has been the case with several approaches in Computational Complexity.. So we cannot (or should not) single out Descriptive Complexity for blaming.

In terms of its application:

"*Consider Problem $A$.. We show that it can be expressed in Logic $B$.. And hence, it follows that its computational (or approximation) complexity is $C$*" --- How many **new** results have been published along these lines? $~$ **Not** many, to my knowledge.. (But I'm happy to be proven wrong.)


---

