Showing cs.LOShow all
2 papers · 1 filter
cs.LO2025
Verifying Quantized Graph Neural Networks is PSPACE-complete
Marco Sälzer, François Schwarzentruber, Nicolas Troquard
In this paper, we investigate the verification of quantized Graph Neural Networks (GNNs), where some fixed-width arithmetic is used to represent numbers. We introduce the linear-co…
cs.LO2025
Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning
Marco Sälzer, Eric Alsmann, Martin Lange
We analyse the complexity of the satisfiability problem, or similarly feasibility problem, (trSAT) for transformer encoders (TE), which naturally occurs in formal verification or i…