Logician and Theoretical Computer Scientist

Lecturer in Verification at the University of Sheffield, UK.

My 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.

Please, find my publications below grouped into topics, and slides for some of my talks behind the above links.

You can find me at:
dblp, Google Scholar, Scopus, ORCID, ResearchGate.

Email: j.t.virtema@sheffield.ac.uk

Open Positions:

PhD Studentship - Quantitative logics and complexity theory (details), deadline: 01.07.2024.

If you are interested in doing a PhD related to my research areas, please contact me directly by email. Several funding schemes exist for both home and overseas students around the year.

Upcoming Events:

Asynchronous Hyperproperties: From Theory to Practice, July 6-7, 2024, Vienna, Austria.

Dagstuhl Seminar: Semirings in Databases, Automata, and Logic, February 16-21, 2025, Dagstuhl, Germany.

14th International Symposium on Foundations of Information and Knowledge Systems, FoIKS 2026, March 2026, Hannover, Germany

Recent News

  • April 2024 — Joined the PC of KR 2024 to be organised in Hanoi.
  • April 2024 — Co-chairing the PC of FoIKS 2026 to be organised in Hannover.
  • April 2024 — FoIKS 2024 took place in Sheffield.
  • March 2024 — Dagstuhl Seminar Logics for Dependence and Independence: Expressivity and Complexity took place in Dagstuhl.
  • January 2024 — Papers this and that accepted to FoIKS 2024.
  • December 2023 — Paper accepted to AAAI 2024.
  • October 2023 — Paper accepted to CSL 2024.
  • October 2023 — Joined the PC of AWPL 2024.
  • October 2023 — MSc. Timon Barlag returned to Hannover.
  • July 2023 — Papers this and that accepted to JELIA 2023.
  • June 2023 — A paper accepted to MFCS 2023.
  • May 2023 — A paper accepted to KR 2023 and another to WoLLIC 2023.
  • April 2023 — MSc. Timon Barlag joins the group as a research associate.
  • March 2023 — MSc. Max Sandström joins the group as a teaching and research assistant.

Here are some older news:
  • November 2022 — Dr. Nina Pardal joins the group as a postdoctoral researcher.
  • September 2022 — Visiting the University of Helsinki for the Autumn.
  • September 2022 — Dr. Fausto Barbero leaves Sheffield to be an Academy of Finland Research Fellow at the University of Helsinki.
  • June 2022 — Chairing the OC of FoIKS 2024 to be organised in Sheffield.
  • June 2022 — Workshop Logical Approach to Neural Networks organised in Sheffield.
  • April 2022 — Paper accepted to LICS 2022.
  • April 2022 — Dr. Fausto Barbero joins the group as a postdoctoral researcher.
  • March 2022 — Joined the Track B PC of FSTTCS 2022.
  • February 2022 — Paper accepted to Annals of Pure and Applied Logic.
  • September 2021 — Paper accepted to FSTTCS 2021.
  • September 2021 — Started as a Lecturer in Verification at the University of Sheffield.

Neural Networks and Distributed Computing

  • Graph Neural Networks and Arithmetic Circuits (arXiv 2024)
    (Joint work with T. Barlag, V. Holzapfel, L. Strieker, and H. Vollmer.)
  • Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functions (AAAI 2024)
    (Joint work with T. Hankala, M. Hannula, and J. Kontinen.)
  • Weak models of distributed computing, with connections to modal logic ( Distributed Comput. 2015, special issue of ACM PODC 2012)
    (Joint work with L. Hella, M. Järvisalo, A. Kuusisto, J. Laurinharju, T. Lempiäinen, K. Luosto, and J. Suomela.)

Theory of Databases and Knowledge Representation

  • Computing Repairs Under Functional and Inclusion Dependencies via Argumentation (FoIKS 2024)
    (Joint work with Y. Mahmood, T. Barlag, and A. Ngonga Ngomo.)
  • A logic-based framework for database repairs (arXiv 2023)
    (Joint work with Nicolas Fröhlich, Arne Meier, and N. Pardal.)
  • Unified Foundations of Team Semantics via Semirings (KR 2023)
    (Joint work with T. Barlag, M. Hannula, J. Kontinen, and N. Pardal.)
  • Fully Generic Queries: Open Problems and Some Partial Answers (MEDI 2019)
    (Joint work with D. Surinx and J. Van den Bussche.)

Probabilistic Logics and Metafinite Model Theory

  • Expressivity Landscape for Logics with Probabilistic Interventionist Counterfactuals (CSL 2024)
    (Joint work with F. Barbero.)
  • Logics with probabilistic team semantics and the Boolean negation (JELIA 2023)
    (Joint work with Miika Hannula, Minna Hirvonen, Juha Kontinen, Yasir Mahmood, and Arne Meier.)
  • Strongly complete axiomatization for a logic with probabilistic interventionist counterfactuals (JELIA 2023)
    (Joint work with F. Barbero.)
  • Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals (Ann. Pure Appl. Log. 2022, extends JELIA 2021)
    (Joint work with M. Hannula.)
  • Descriptive complexity of real computation and probabilistic independence logic (LICS 2020, slides1, slides2, video)
    (Joint work with M. Hannula, J. Kontinen, and J. Van den Bussche.)
  • Facets of Distribution Identities in Probabilistic Team Semantics (JELIA 2019)
    (Joint work with M. Hannula, Å. Hirvonen, J. Kontinen, and V. Kulikov.)
  • Probabilistic Team Semantics (FOIKS 2018, slides1, slides2, slides3)
    (Joint work with A. Durand, M. Hannula, J. Kontinen, and A. Meier.)

Logics for Verification

  • A Remark on the Expressivity of Asynchronous TeamLTL and HyperLTL (FoIKS 2024)
    (Joint work with Juha Kontinen and Max Sandström.)
  • Set Semantics for Asynchronous TeamLTL: Expressivity and Complexity (MFCS 2023)
    (Joint work with J. Kontinen and M. Sandström.)
  • Temporal Team Semantics Revisited (LICS 2022)
    (Joint work with J. Gutsfeld, A. Meier, and C. Ohrem.)
  • Linear-time Temporal Logic with Team Semantics: Expressivity and Complexity (FSTTCS 2021, slides, video)
    (Joint work with B. Finkbeiner, J. Hofmann, J. Kontinen, and F. Yang.)
  • Team Semantics for the Specification and Verification of Hyperproperties (MFCS 2018, slides)
    (Joint work with A. Krebs, A. Meier, and M. Zimmermann.)
  • A Team Based Variant of CTL (TIME 2015)
    (Joint work with A. Krebs and A. Meier.)

Finite Model Theory

  • Descriptive Complexity of Deterministic Polylogarithmic Time and Space (J. Comput. Syst. Sci. 2021, slides)
    Conference version in WoLLIC 2019.
    (Joint work with F. Ferrarotti, S. Gonzalez, J.M. Turull Torres, and J. Van den Bussche.)
  • Expressivity within second-order transitive-closure logic (CSL 2018, slides1, slides2, slides3)
    (Joint work with F. Ferrarotti and J. Van den Bussche.)

Definability of Modal Logics

  • Semantic Characterizations of Intuitionistic Logic with the Universal Modality and Intuitionistic Inquisitive Logic
    (Joint work with K. Sano.)
  • Characterising Modal Definability of Team-Based Logics via the Universal Modality (Ann. Pure Appl. Log. 2019, slides1, slides2)
    Conference versions in WoLLIC 2015 and 2016.
    (Joint work with K. Sano.)
  • The Expressive Power of Modal Dependence Logic (AIML 2014)
    (Joint work with L. Hella, K. Luosto, and K. Sano.)
  • Extended Modal Dependence Logic EMDL (WoLLIC 2013)
    (Joint work with J. Ebbing, L. Hella, A. Meier, J.S. Müller, and H. Vollmer.)

Complexity of Propositional and Modal Logics

  • Parameterised Complexity of Propositional Inclusion and Independence Logic (WoLLIC 2023)
    (Joint work with Y. Mahmood.)
  • On the Complexity of Horn and Krom Fragments of Second-Order Boolean Logic (CSL 2021, slides, video)
    (Joint work with M. Hannula, J. Kontinen, and M. Lück)
  • Model checking and validity in propositional and modal inclusion logics (J. Log. Comput. 2019, slides)
    Conference version in MFCS 2017.
    (Joint work with L. Hella, A. Kuusisto, and A. Meier.)
  • Complexity of Propositional Logics in Team Semantics (ACM Trans. Comput. Log. 2018, slides1, slides2)
    Conference version in MFCS 2015.
    (Joint work with M. Hannula, J. Kontinen, and H. Vollmer.)
  • Complexity of validity for propositional dependence logics (Inf. Comput. 2017, slides)
    Conference version in GandALF 2014.
  • On quantified propositional logics and the exponential time hierarchy (GandALF 2016, slides)
    (Joint work with M. Hannula, J. Kontinen, and M. Lück)

First-Order Team Semantics

  • Polyteam Semantics ( J. Log. Comput. 2020, slides)
    Conference version in LFCS 2018.
    (Joint work with M. Hannula and J. Kontinen.)
  • Approximation and Dependence via Multiteam Semantics (Ann. Math. Artif. Intell. 2018)
    Conference version in FoIKS 2016.
    (Joint work with A. Durand, M. Hannula, J. Kontinen, and A. Meier.)
  • Boolean Dependence Logic and Partially-Ordered Connectives (J. Comput. Syst. Sci. 2017)
    Conference version in WoLLIC 2013.
    (Joint work with J. Ebbing, L. Hella, and P. Lohmann.)
  • Decidability of predicate logics with team semantics (MFCS 2016, slides)
    (Joint work with J. Kontinen and A. Kuusisto.)
  • Complexity of two-variable Dependence Logic and IF-Logic (Inf. Comput. 2014)
    Conference version in LICS 2011.
    (Joint work with J. Kontinen, A. Kuusisto, and P. Lohmann.)

Axiomatisations in Modal Team Semantics

  • Axiomatizing Propositional Dependence Logics (CSL 2015)
    (Joint work with K. Sano.)

Logical Foundations of Geometry

  • Undecidable First-Order Theories of Affine Geometries (Log. Methods Comput. Sci. 2013)
    Conference version in CSL 2012.
    (Joint work with A. Kuusisto and J. Meyers.)