Portfolio item number 1
Short description of portfolio item number 1
Posts by Collection
arxiv
portfolio
Portfolio item number 2
Short description of portfolio item number 2
publications
Finite Convergence of Mu-Calculus Fixpoints on Genuinely Infinite Structures
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/
Reachability is NP-complete Even For the Simplest Neural Networks
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
Fundamental Limits in Formal Verification of Message-Passing Neural Networks
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-
A Logic for Reasoning About Aggregate-Combine Graph Neural Networks
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
The Computational Complexity of Formal Reasoning for Encoder-Only Transformers
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
talks
Talk 1 on Relevant Topic in Your Field
Published:
This is a description of your talk, which is a markdown files that can be all markdown-ified like any other post. Yay markdown!
Conference Proceeding talk 3 on Relevant Topic in Your Field
Published:
This is a description of your conference proceedings talk, note the different field in type. You can put anything in this field.
teaching
Teaching experience 2
Workshop, University 1, Department, 2015
This is a description of a teaching experience. You can use markdown like any other post.