You will find most, if not all, my publications on dblp or google scholar. It is probably also the most up-to-date place.
Published in arXiv, 2024
TL;DR: We investigate the challenges and possibilities of formal reasoning for encoder-only transformers (EOT) by examining their satisfiability problem (SAT). We find SAT is undecidable for general EOT but identify decidable and NEXPTIME-hard scenarios for quantized EOT, highlighting the complexity of these cases.
Recommended citation: https://arxiv.org/abs/2405.18548
Published in arXiv, 2024
TL;DR: We introduce a modal logic incorporating counting modalities into linear inequalities and demonstrate that each formula can be converted into an equivalent graph neural network (GNN). We also show that a broad class of GNNs can be efficiently transformed into formulas and that the satisfiability problem is PSPACE-complete, enabling polynomial space solutions for various applications like GNN querying and equivalence checking.
Recommended citation: https://arxiv.org/abs/2405.00205
Published in The Eleventh International Conference on Learning Representations, ICLR, 2023
TL;DR: We proof that formal verification of different safety properties of graph-classifying MPNN is impossible in general and that verification problems for node-classifying GNN are solvable if the considered graphs have bounded degree.
Recommended citation: https://openreview.net/forum?id=WlbG820mRH-
Published in International Conference on Reachability Problems 2021 (RP21), 2021
TL;DR: We give a thorough proof for the NP-completeness of verifying output reachability of NN and show that the problem remains NP-hard if restricted to one-layered NN of minimal dimensionality.
Recommended citation: https://link.springer.com/chapter/10.1007/978-3-030-89716-1_10
Published in 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), 2021
TL;DR: We show that there are structures with infinite bisimulation quotient that ensure finite convergence of all mu-calculus formulas.
Recommended citation: https://drops.dagstuhl.de/opus/volltexte/2021/14464/