Dr Jonni Virtema
School of Computer Science
Lecturer in Verification
Study Abroad / International Student Exchange Officer
Member of the Foundations of Computation research group
J.T.Virtema@sheffield.ac.uk
Regent Court (DCS)
Full contact details
Dr Jonni Virtema
School of Computer Science
Regent Court (DCS)
211 Portobello
Sheffield
S1 4DP
School of Computer Science
Regent Court (DCS)
211 Portobello
Sheffield
S1 4DP
- Profile
-
Jonni is a Lecturer in Verification at the Department of Computer Science. Before joining, in September 2021, he held research positions as a PI or a hired postdoc in a series of projects funded by the German Research Foundation (DFG), the Japan Society for the Promotion of Science (JSPS), the Research Foundation – Flanders (FWO), and the Academy of Finland (AKA).
Jonni received his MSc (2008) and PhD (2014) in mathematics from the University of Tampere, Finland. In 2020, he received the title of a Docent in Mathematical Logic from the University of Helsinki, Finland. His research interests originate from the general fields of finite model theory and logic in computer science. His research themes revolve around the interplay between expressivity and complexity of different logical formalisms, and in logical characterisations of complexity classes.
- Research interests
-
Dr Jonni Virtema's research interests include: finite model theory, logic in computer science, logics for dependence and independence, modal logics, logics for verification, logical foundations of neural networks, logical foundations of quantum information theory, computational complexity, and logics with team semantics.
- Publications
-
Show: Featured publications All publications
Featured publications
Journal articles
- Rewriting consistent answers on annotated data. Proceedings of the ACM on Management of Data, 3(2), 1-26. View this article in WRRO
- Set semantics for asynchronous TeamLTL: expressivity and complexity. Information and Computation, 304. View this article in WRRO
- Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals. Annals of Pure and Applied Logic, 173(10).
- Descriptive complexity of deterministic polylogarithmic time and space. Journal of Computer and System Sciences, 119, 145-163.
Conference proceedings
- Graph neural networks and arithmetic circuits. Advances in Neural Information Processing Systems (NeurIPS 2024), Vol. 37. Vancouver, Canada, 10 December 2024 - 10 December 2024. View this article in WRRO
- Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functions. THIRTY-EIGHTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 38 NO 11 (pp 12278-12285)
- Unified foundations of team semantics via semirings. Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning, KR 2023 (pp 75-85). Rhodes, Greece, 2 September 2023 - 2 September 2023. View this article in WRRO
- Temporal team semantics revisited. LICS '22: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science. Haifa Israel, 2 August 2022 - 2 August 2022. View this article in WRRO
- Descriptive complexity of real computation and probabilistic independence logic. Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (pp 550-563)
- Weak models of distributed computing, with connections to modal logic. Proceedings of the 2012 ACM symposium on Principles of distributed computing (pp 185-194)
- Complexity of Two-Variable Dependence Logic and IF-Logic. 2011 IEEE 26th Annual Symposium on Logic in Computer Science (pp 289-298), 21 June 2011 - 24 June 2011.
All publications
Journal articles
- Rewriting consistent answers on annotated data. Proceedings of the ACM on Management of Data, 3(2), 1-26. View this article in WRRO
- Logics with probabilistic team semantics and the Boolean negation. Journal of Logic and Computation, 35(3). View this article in WRRO
- Set semantics for asynchronous TeamLTL: expressivity and complexity. Information and Computation, 304. View this article in WRRO
- Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals. Annals of Pure and Applied Logic, 173(10).
- Descriptive complexity of deterministic polylogarithmic time and space. Journal of Computer and System Sciences, 119, 145-163.
- Polyteam semantics. Journal of Logic and Computation, 30(8), 1541-1566.
- Characterising modal definability of team-based logics via the universal modality. Annals of Pure and Applied Logic, 170(9), 1100-1127.
- Model checking and validity in propositional and modal inclusion logics. Journal of Logic and Computation, 29(5), 605-630.
- Approximation and dependence via multiteam semantics. Annals of Mathematics and Artificial Intelligence, 83(3-4), 297-320.
- Complexity of Propositional Logics in Team Semantic. ACM Transactions on Computational Logic, 19(1), 1-14.
- Boolean dependence logic and partially-ordered connectives. Journal of Computer and System Sciences, 88, 103-125.
- Complexity of validity for propositional dependence logics. Information and Computation, 253, 224-236.
- Weak models of distributed computing, with connections to modal logic. Distributed Computing, 28(1), 31-53.
- Complexity of two-variable dependence logic and IF-logic. Information and Computation, 239, 237-253.
- Undecidable First-Order Theories of Affine Geometries. Logical Methods in Computer Science, Volume 9, Issue 4.
Conference proceedings
- Graph neural networks and arithmetic circuits. Advances in Neural Information Processing Systems (NeurIPS 2024), Vol. 37. Vancouver, Canada, 10 December 2024 - 10 December 2024. View this article in WRRO
- A remark on the expressivity of asynchronous TeamLTL and HyperLTL. Foundations of Information and Knowledge Systems: 13th International Symposium, FoIKS 2024, Sheffield, UK, April 8–11, 2024, Proceedings, Vol. LNCS 14589 (pp 275-286). Sheffield, UK, 8 April 2024 - 8 April 2024. View this article in WRRO
- Computing repairs under functional and inclusion dependencies via argumentation. Foundations of Information and Knowledge Systems: 13th International Symposium, FoIKS 2024, Sheffield, UK, April 8–11, 2024, Proceedings, Vol. LNCS 14589 (pp 23-42). Sheffield, UK, 8 April 2024 - 8 April 2024. View this article in WRRO
- Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functions. THIRTY-EIGHTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 38 NO 11 (pp 12278-12285)
- Expressivity landscape for logics with probabilistic interventionist counterfactuals. 32nd EACSL Annual Conference on Computer Science Logic, CSL 2024, Vol. 288 (pp 15:1-15:19). Naples, Italy, 19 February 2024 - 19 February 2024. View this article in WRRO
- Strongly complete axiomatization for a logic with probabilistic interventionist counterfactuals. Logics in Artificial Intelligence: 18th European Conference, JELIA 2023, Dresden, Germany, September 20–22, 2023, Proceedings(LNAI 14281) (pp 649-664). Dresden, Germany, 20 September 2023 - 20 September 2023. View this article in WRRO
- Logics with probabilistic team semantics and the Boolean negation. Logics in Artificial Intelligence: 18th European Conference, JELIA 2023, Dresden, Germany, September 20–22, 2023, Proceedings(LNAI 14281) (pp 665-680). Dresden, Germany, 20 September 2023 - 20 September 2023. View this article in WRRO
- Parameterized complexity of propositional inclusion and independence logic. Logic, Language, Information, and Computation: 29th International Workshop, WoLLIC 2023, Halifax, NS, Canada, July 11–14, 2023, Proceedings, Vol. LNCS 13923 (pp 274-291). Halifax, NS, Canada View this article in WRRO
- Set semantics for asynchronous TeamLTL: expressivity and complexity. 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Vol. 272 (pp 60:1-60:14). Bordeaux, France, 28 August 2023 - 28 August 2023. View this article in WRRO
- Unified foundations of team semantics via semirings. Proceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning, KR 2023 (pp 75-85). Rhodes, Greece, 2 September 2023 - 2 September 2023. View this article in WRRO
- Temporal team semantics revisited. LICS '22: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science. Haifa Israel, 2 August 2022 - 2 August 2022. View this article in WRRO
- Linear-time temporal logic with team semantics: expressivity and complexity. 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021), Vol. 213 (pp 52:1-52:17). Virtual Conference, 15 December 2021 - 15 December 2021. View this article in WRRO
- Tractability Frontiers in Probabilistic Team Semantics and Existential Second-Order Logic over the Reals (pp 262-278)
- On the complexity of horn and krom fragments of second-order boolean logic. Leibniz International Proceedings in Informatics Lipics, Vol. 183
- Descriptive complexity of real computation and probabilistic independence logic. Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (pp 550-563)
- Fully Generic Queries: Open Problems and Some Partial Answers (pp 20-31)
- Descriptive Complexity of Deterministic Polylogarithmic Time (pp 208-222)
- Facets of Distribution Identities in Probabilistic Team Semantics (pp 304-320)
- Team semantics for the specification and verification of hyperproperties. Leibniz International Proceedings in Informatics Lipics, Vol. 117
- Expressivity within second-order transitive-closure logic. Leibniz International Proceedings in Informatics Lipics, Vol. 119
- Probabilistic Team Semantics (pp 186-206)
- Polyteam Semantics (pp 190-210)
- Model checking and validity in propositional and modal inclusion logics. Leibniz International Proceedings in Informatics Lipics, Vol. 83
- Characterizing Relative Frame Definability in Team Semantics via the Universal Modality (pp 392-409)
- Decidability of predicate logics with team semantics. Leibniz International Proceedings in Informatics Lipics, Vol. 58
- Approximation and Dependence via Multiteam Semantics (pp 271-291)
- A Team Based Variant of CTL. 2015 22nd International Symposium on Temporal Representation and Reasoning (TIME) (pp 140-149), 23 September 2015 - 25 September 2015.
- Axiomatizing propositional dependence logics. Leibniz International Proceedings in Informatics Lipics, Vol. 41 (pp 292-307)
- Complexity of Propositional Independence and Inclusion Logic (pp 269-280)
- Characterizing Frame Definability in Team Semantics via the Universal Modality (pp 140-155)
- The expressive power of modal dependence logic. Advances in Modal Logic, Vol. 10 (pp 294-312)
- Boolean Dependence Logic and Partially-Ordered Connectives (pp 111-125)
- Extended Modal Dependence Logic $mathcal{EMDL}$ (pp 126-137)
- Weak models of distributed computing, with connections to modal logic. Proceedings of the 2012 ACM symposium on Principles of distributed computing (pp 185-194)
- Undecidable first-order theories of affine geometries. Leibniz International Proceedings in Informatics Lipics, Vol. 16 (pp 470-484)
- Complexity of Two-Variable Dependence Logic and IF-Logic. 2011 IEEE 26th Annual Symposium on Logic in Computer Science (pp 289-298), 21 June 2011 - 24 June 2011.
- A Logic-Based Framework for Database Repairs. Proceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning, KR 2025
- Halting Recurrent GNNs and the Graded μ-Calculus. Proceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning, KR 2025
- On Quantified Propositional Logics and the Exponential Time Hierarchy. Electronic Proceedings in Theoretical Computer Science, Vol. 226 (pp 198-212)
- Complexity of validity for propositional dependence logics. Electronic Proceedings in Theoretical Computer Science, Vol. 161 (pp 18-31)
Preprints
- Local consistency and axioms of functional dependence.
- Halting Recurrent GNNs and the Graded $μ$-Calculus.
- Rewriting Consistent Answers on Annotated Data.
- Graph Neural Networks and Arithmetic Circuits.
- Computing Repairs Under Functional and Inclusion Dependencies via
Argumentation.
- A logic-based framework for database repairs, arXiv.
- Logics with probabilistic team semantics and the Boolean negation.
- Complexity of Neural Network Training and ETR: Extensions with
Effectively Continuous Functions.
- Set Semantics for Asynchronous TeamLTL: Expressivity and Complexity.
- Strongly complete axiomatization for a logic with probabilistic
interventionist counterfactuals.
- Expressivity Landscape for Logics with Probabilistic Interventionist
Counterfactuals.
- Unified Foundations of Team Semantics via Semirings, arXiv.
- Temporal Team Semantics Revisited.
- Tractability frontiers in probabilistic team semantics and existential
second-order logic over the reals.
- Linear-time Temporal Logic with Team Semantics: Expressivity and
Complexity.
- On the Complexity of Horn and Krom Fragments of Second-Order Boolean
Logic.
- Descriptive complexity of real computation and probabilistic
independence logic.
- Descriptive Complexity of Deterministic Polylogarithmic Time and Space.
- Facets of Distribution Identities in Probabilistic Team Semantics.
- Expressivity within second-order transitive-closure logic.
- Probabilistic team semantics.
- Team Semantics for the Specification and Verification of Hyperproperties.
- Polyteam Semantics.
- Model Checking and Validity in Propositional and Modal Inclusion Logics.
- Characterizing Relative Frame Definability in Team Semantics via the
Universal Modality.
- Approximation and Dependence via Multiteam Semantics.
- A Team Based Variant of CTL.
- Complexity of Propositional Logics in Team Semantics.
- Characterising Modal Definability of Team-Based Logics via the Universal
Modality.
- Decidability of predicate logics with team semantics.
- Axiomatizing Propositional Dependence Logics.
- Boolean Dependence Logic and Partially-Ordered Connectives.
- Complexity of validity for propositional dependence logics.
- The Expressive Power of Modal Dependence Logic.
- Undecidable First-Order Theories of Affine Geometries.
- Undecidable First-Order Theories of Affine Geometries.
- Weak Models of Distributed Computing, with Connections to Modal Logic.
- Complexity of two-variable Dependence Logic and IF-Logic.
- Rewriting consistent answers on annotated data. Proceedings of the ACM on Management of Data, 3(2), 1-26. View this article in WRRO
- Grants
-
- Logical approach to quantum mechanics and contextuality, DFG, 09/2021 - 10/2024, £160,711, as PI