Source author record

Pascal Bergsträßer

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Logic in Computer Science Machine Learning math.GR

Catalog footprint

Research overview

2works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

The Polynomial Counting Capabilities of Message Passing Neural Networks

The counting power of Message Passing Neural Networks (MPNN) has been the subject of many recent papers, showing that they can express logic that involves counting up to a threshold or more generally satisfy a linear arithmetic constraint. In this paper, we study the counting capabilities of MPNN beyond linear arithmetic, primarily utilising local and global mean aggregations. In particular, our goal is to tease out conditions required to express extensions of graded modal logic with polynomial counting constraints. We show that global polynomial counting constraints in node-labelled graphs can be checked using mean MPNN under mild assumptions. Checking local constraints is also possible, if we consider formulas with no nested modalities and additionally either (i) permit sum/max aggregations, or (ii) only restrict to regular graphs. We also show how formulas with nested modalities can be captured by mean MPNN over graphs with tree-like structures and similar assumptions.

preprint2021arXiv

A characterization of wreath products where knapsack is decidable

The knapsack problem for groups was introduced by Miasnikov, Nikolaev, and Ushakov. It is defined for each finitely generated group $G$ and takes as input group elements $g_1,\ldots,g_n,g\in G$ and asks whether there are $x_1,\ldots,x_n\ge 0$ with $g_1^{x_1}\cdots g_n^{x_n}=g$ . We study the knapsack problem for wreath products $G\wr H$ of groups $G$ and $H$ . Our main result is a characterization of those wreath products $G\wr H$ for which the knapsack problem is decidable. The characterization is in terms of decidability properties of the indiviual factors $G$ and $H$ . To this end, we introduce two decision problems, the intersection knapsack problem and its restriction, the positive intersection knapsack problem. Moreover, we apply our main result to $H_3(\mathbb{Z})$ , the discrete Heisenberg group, and to Baumslag-Solitar groups $\mathsf{BS}(1,q)$ for $q\ge 1$ . First, we show that the knapsack problem is undecidable for $G\wr H_3(\mathbb{Z})$ for any $G\ne 1$ . This implies that for $G\ne 1$ and for infinite and virtually nilpotent groups $H$ , the knapsack problem for $G\wr H$ is decidable if and only if $H$ is virtually abelian and solvability of systems of exponent equations is decidable for $G$ . Second, we show that the knapsack problem is decidable for $G\wr\mathsf{BS}(1,q)$ if and only if solvability of systems of exponent equations is decidable for $G$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.