Picture
JONNI VIRTEMA
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.

Open positions:

PhD Studentship - Logical Approach to Verification of Hyperproperties (details).

Probabilistic Logics and Metafinite Model Theory

  • Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals (APAL 2022)
    Conference version in 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

  • 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 (JCSS 2021, slides)
    Conference version in WoLLIC 2019.
    (Joint work with F. Ferrarotti, S. González, 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.)
  • Weak models of distributed computing, with connections to modal logic (DC 2015)
    Conference version in ACM PODC 2012.
    (Joint work with L. Hella, M. Järvisalo, A. Kuusisto, J. Laurinharju, T. Lempiäinen, K. Luosto, and J. Suomela.)

First-Order Team Semantics

  • Polyteam Semantics (JLC 2020, slides)
    Conference version in LFCS 2018.
    (Joint work with M. Hannula and J. Kontinen.)
  • Approximation and Dependence via Multiteam Semantics (AMAI 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 (JCSS 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 (I&C 2014)
    Conference version in LICS 2011.
    (Joint work with J. Kontinen, A. Kuusisto, and P. Lohmann.)

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 (APAL 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 with Team Semantics

  • Parameterised Complexity of Propositional Inclusion and Independence Logic (arXiv 2021)
    (Joint work with Y. Mahmood.)
  • Model checking and validity in propositional and modal inclusion logics (JLC 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 ToCL 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 (I&C 2017, slides)
    Conference version in GandALF 2014.

Quantified Propositional Logics

  • 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)
  • On quantified propositional logics and the exponential time hierarchy (GandALF 2016, slides)
    (Joint work with M. Hannula, J. Kontinen, and M. Lück)

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 (LMCS 2013)
    Conference version in CSL 2012.
    (Joint work with A. Kuusisto and J. Meyers.)

Theory of Database Query Languages

  • Fully Generic Queries: Open Problems and Some Partial Answers (MEDI 2019)
    (Joint work with D. Surinx and J. Van den Bussche.)