About me

I work somewhere between category theory and its applications, especially to fields such as cryptography and quantum computing. Lately, I've worked on contextuality & nonlocality in quantum mechanics and on composable security in cryptography. More generally, I enjoy most parts of mathematics and computer science where an abstract, structural approach pays off. This is what I look like on paper.

Papers

Inner autoequivalences in general and those of monoidal categories in particular

Hofstra, P., & Karvonen, M. (2024). Inner autoequivalences in general and those of monoidal categories in particular. Journal of Pure and Applied Algebra, , Volume 228, Issue 11, 107717.
PDF BibTeX ArXiv Journal Abstract Nutshell

We develop a general theory of (extended) inner autoequivalences of objects of any 2-category, generalizing the theory of isotropy groups to the 2-categorical setting. We show how dense subcategories let one compute isotropy in the presence of binary coproducts, unifying various known one-dimensional results and providing tractable computational tools in the two-dimensional setting. In particular, we show that the isotropy 2-group of a monoidal category coincides with its Picard 2-group, i.e., the 2-group on its weakly invertible objects.

Our main result states that inner autoequivalences of monoidal categories are essentially the same as conjugations by a weakly invertible element. For this to be a theorem, there needs to be a general theory of inner autoequivalences, and indeed there is: developing that is the other main contribution.

Categorical composable cryptography: extended version

Broadbent, A., & Karvonen, M. (2023). Categorical composable cryptography: extended version. Logical Methods in Computer Science, volume 19, issue 4, 30:1-30:46.
PDF BibTeX ArXiv Journal Abstract Nutshell

We formalize the simulation paradigm of cryptography in terms of category theory and show that protocols secure against abstract attacks form a symmetric monoidal category, thus giving an abstract model of composable security definitions in cryptography. Our model is able to incorporate computational security, set-up assumptions and various attack models such as colluding or independently acting subsets of adversaries in a modular, flexible fashion. We conclude by using string diagrams to rederive the security of the one-time pad, correctness of Diffie-Hellman key exchange and no-go results concerning the limits of bipartite and tripartite cryptography, ruling out e.g., composable commitments and broadcasting. On the way, we exhibit two categorical constructions of resource theories that might be of independent interest: one capturing resources shared among multiple parties and one capturing resource conversions that succeed asymptotically.

Roughly speaking, a categorical version of abstract/constructive cryptography. Extended version of the FoSSaCS paper below.

Closing Bell: Boxing Black Box Simulations in the Resource Theory of Contextuality

Barbosa, R. S., Karvonen, M., & Mansfield, S. (2023). Closing Bell: Boxing Black Box Simulations in the Resource Theory of Contextuality. In Samson Abramsky on Logic and Structure in Computer Science and Beyond.
PDF BibTeX ArXiv Book Chapter Abstract Nutshell

This chapter contains an exposition of the sheaf-theoretic framework for contextuality emphasising resource-theoretic aspects, as well as some original results on this topic. In particular, we consider functions that transform empirical models on a scenario S to empirical models on another scenario T, and characterise those that are induced by classical procedures between S and T corresponding to 'free' operations in the (non-adaptive) resource theory of contextuality. We construct a new 'hom' scenario built from S and T, whose empirical models induce such functions. Our characterisation then boils down to being induced by a non-contextual model. We also show that this construction on scenarios provides a closed structure on the category of measurement scenarios.

An exposition of the sheaf-theoretic framework for contextuality emphasising resource-theoretic aspects, as well as some original results on this topic.

Categorical composable cryptography

Broadbent, A., & Karvonen, M. (2022). Categorical composable cryptography. In Foundations of Software Science and Computation Structures (FoSSaCS) 2022.
PDF BibTeX ArXiv Proceedings Abstract Nutshell

We formalize the simulation paradigm of cryptography in terms of category theory and show that protocols secure against abstract attacks form a symmetric monoidal category, thus giving an abstract model of composable security definitions in cryptography. Our model is able to incorporate computational security, set-up assumptions and various attack models such as colluding or independently acting subsets of adversaries in a modular, flexible fashion. We conclude by using string diagrams to rederive the security of the one-time pad and no-go results concerning the limits of bipartite and tripartite cryptography, ruling out e.g., composable commitments and broadcasting.

Roughly speaking, a categorical version of abstract/constructive cryptography. See the extended version above.

Neither Contextuality nor Nonlocality Admits Catalysts

Karvonen, M. (2021). Neither Contextuality nor Nonlocality Admits Catalysts. Phys. Rev. Lett. 127, 160402
PDF BibTeX ArXiv Journal Abstract Nutshell

We show that the resource theory of contextuality does not admit catalysts, i.e., there are no correlations that can enable an otherwise impossible resource conversion and still be recovered afterward. As a corollary, we observe that the same holds for nonlocality. As entanglement allows for catalysts, this adds a further example to the list of "anomalies of entanglement," showing that nonlocality and entanglement behave differently as resources. We also show that catalysis remains impossible even if, instead of classical randomness, we allow some more powerful behaviors to be used freely in the free transformations of the resource theory.

It turns out that there are no catalysts for contextuality nor for non-locality. This is in contrast with entanglement, for which catalysts famously exist.

Biproducts without pointedness

Karvonen, M. (2020). Biproducts without pointedness. Cahiers de topologie et géométrie différentielle catégoriques, Vol LXI, Issue 3, 229-238.
PDF BibTeX ArXiv Journal Abstract Nutshell

We show how to define biproducts up to isomorphism in an arbitrary category without assuming any enrichment. The resulting notion coincides with the usual definitions whenever all binary biproducts exist or the category is suitably enriched, resulting in a modest yet strict generalization otherwise. We also characterize when a category has all binary biproducts in terms of an ambidextrous adjunction. Finally, we give some new examples of biproducts that our definition recognizes.

Turns out one can define a well-behaved notion of a biproduct in any category without assuming pointedness.

A comonadic view of simulation and quantum resources

Abramsky, S., Barbosa, R. S., Karvonen, M., & Mansfield, S. (2019). A comonadic view of simulation and quantum resources. In Logic in Computer Science (LICS) 2019.
PDF BibTeX ArXiv Proceedings Abstract Nutshell

We study simulation and quantum resources in the setting of the sheaf-theoretic approach to contextuality and non-locality. Resources are viewed behaviourally, as empirical models. In earlier work, a notion of morphism for these empirical models was proposed and studied. We generalize and simplify the earlier approach, by starting with a very simple notion of morphism, and then extending it to a more useful one by passing to a co-Kleisli category with respect to a comonad of measurement protocols. We show that these morphisms capture notions of simulation between empirical models obtained via `free' operations in a resource theory of contextuality, including the type of classical control used in measurement-based quantum computation schemes.

We improve on the ideas in the QPL paper below.

Limits in dagger categories

Heunen, C., & Karvonen, M. (2019). Limits in dagger categories. Theory and Applications of Categories, Vol. 34, No. 18, 468-513.
PDF BibTeX ArXiv Journal Abstract Nutshell

We develop a notion of limit for dagger categories, that we show is suitable in the following ways: it subsumes special cases known from the literature; dagger limits are unique up to unitary isomorphism; a wide class of dagger limits can be built from a small selection of them; dagger limits of a fixed shape can be phrased as dagger adjoints to a diagonal functor; dagger limits can be built from ordinary limits in the presence of polar decomposition; dagger limits commute with dagger colimits in many cases.

We define a notion of limit suitable for dagger categories and explore it.

Reversible effects as inverse arrows

Heunen, C., Kaarsgaard, R., & Karvonen, M. (2018). Reversible effects as inverse arrows. Proceedings of MFPS 2018. ENTCS, 341, 179-199.
PDF BibTeX ArXiv Proceedings Abstract Nutshell

Reversible computing models settings in which all processes can be reversed. Applications include low-power computing, quantum computing, and robotics. It is unclear how to represent side-effects in this setting, because conventional methods need not respect reversibility. We model reversible effects by adapting Hughes' arrows to dagger arrows and inverse arrows. This captures several fundamental reversible effects, including serialization and mutable store computations. Whereas arrows are monoids in the category of profunctors, dagger arrows are involutive monoids in the category of profunctors, and inverse arrows satisfy certain additional properties. These semantics inform the design of functional reversible programs supporting side-effects.

We study (reversible) side-effects in a reversible programming language. As reversible computing can be modelled by inverse categories, we model side-effects using a notion of arrow suitable for inverse categories. Since inverse categories can be defined as certain dagger categories, we also develop a notion of a dagger arrow.

Categories of Empirical Models

Karvonen, M. (2018). Categories of empirical models. Proceedings of QPL 2018, EPTCS 287, pp. 239-252.
PDF BibTeX ArXiv Abstract Nutshell

A notion of morphism that is suitable for the sheaf-theoretic approach to contextuality is developed, resulting in a resource theory for contextuality. The key features involve using an underlying relation rather than a function between measurement scenarios, and allowing for stochastic mappings of outcomes to outcomes. This formalizes an intuitive idea of using one empirical model to simulate another one with the help of pre-shared classical randomness. This allows one to reinterpret concepts and earlier results in terms of morphisms. Most notably: non-contextual models are precisely those allowing a morphism from the terminal object; contextual fraction is functorial; Graham-reductions induce morphisms, reinterpreting Vorob'evs theorem; contextual models cannot be cloned.

Formalizes an intuitive idea of using one empirical model to simulate another one with the help of pre-shared classical randomness, resulting in a resource theory for contextuality. Arguably the theory is superseded by the framework of the LICS paper above.

Monads on dagger categories

Heunen, C., & Karvonen, M. (2016). Monads on dagger categories. Theory and Applications of Categories, Vol. 31, No. 35, 1016-1043.
PDF BibTeX ArXiv Journal Abstract Nutshell

The theory of monads on categories equipped with a dagger (a contravariant identity-on-objects involutive endofunctor) works best when everything respects the dagger: the monad and adjunctions should preserve the dagger, and the monad and its algebras should satisfy the so-called Frobenius law. Then any monad resolves as an adjunction, with extremal solutions given by the categories of Kleisli and Frobenius-Eilenberg-Moore algebras, which again have a dagger. We characterize the Frobenius law as a coherence property between dagger and closure, and characterize strong such monads as being induced by Frobenius monoids.

This is the extended version of the previous conference paper. When everything respects the dagger, one gets a nice theory of dagger monads analogous to the usual one.

Reversible monadic computing

Heunen, C., & Karvonen, M. (2015). Reversible monadic computing. Electronic Notes in Theoretical Computer Science, 319, 217-237.
PDF BibTeX ArXiv Proceedings Abstract Nutshell

We extend categorical semantics of monadic programming to reversible computing, by considering monoidal closed dagger categories: the dagger gives reversibility, whereas closure gives higher-order expressivity. We demonstrate that Frobenius monads model the appropriate notion of coherence between the dagger and closure by reinforcing Cayley's theorem; by proving that effectful computations (Kleisli morphisms) are reversible precisely when the monad is Frobenius; by characterizing the largest reversible subcategory of Eilenberg-Moore algebras; and by identifying the latter algebras as measurements in our leading example of quantum computing. Strong Frobenius monads are characterized internally by Frobenius monoids.

First steps towards a theory of dagger monads. Arguably superseded by the TAC paper above.

Preprints

Towards a Unified Theory of Time-varying Data

Bumpus, B. M., Fairbanks, F., Karvonen, M., Leal, W., & Simard, F. (2024). Towards a Unified Theory of Time-varying Data
PDF ArXiv Abstract Nutshell

What is a time-varying graph, or a time-varying topological space and more generally what does it mean for a mathematical structure to vary over time? Here we introduce categories of narratives: powerful tools for studying temporal graphs and other time-varying data structures. Narratives are sheaves on posets of intervals of time which specify snapshots of a temporal object as well as relationships between snapshots over the course of any given interval of time. This approach offers two significant advantages. First, when restricted to the base category of graphs, the theory is consistent with the well-established theory of temporal graphs, enabling the reproduction of results in this field. Second, the theory is general enough to extend results to a wide range of categories used in data analysis, such as groups, topological spaces, databases, Petri nets, simplicial complexes and many more. The approach overcomes the challenge of relating narratives of different types to each other and preserves the structure over time in a compositional sense. Furthermore our approach allows for the systematic relation of different kinds of narratives. In summary, this theory provides a consistent and general framework for analyzing dynamic systems, offering an essential tool for mathematicians and data scientists alike.

We develop a general theory of temporal objects, abstracting from temporal graphs and their homomomorphisms.

Uncloneable Quantum Advice

Broadbent, A., Karvonen, M. & Lord, S. (2023). Uncloneable Quantum Advice
PDF ArXiv Abstract Nutshell

The famous no-cloning principle has been shown recently to enable a number of uncloneable functionalities. Here we address for the first time unkeyed quantum uncloneablity, via the study of a complexity-theoretic tool that enables a computation, but that is natively unkeyed: quantum advice. Remarkably, this is an application of the no-cloning principle in a context where the quantum states of interest are not chosen by a random process. We show the unconditional existence of promise problems admitting uncloneable quantum advice, and the existence of languages with uncloneable advice, assuming the feasibility of quantum copy-protecting certain functions. Along the way, we note that state complexity classes, introduced by Rosenthal and Yuen (ITCS 2022) - which concern the computational difficulty of synthesizing sequences of quantum states - can be naturally generalized to obtain state cloning complexity classes. We make initial observations on these classes, notably obtaining a result analogous to the existence of undecidable problems. Our proof technique establishes the existence of ingenerable sequences of finite bit strings - essentially meaning that they cannot be generated by any uniform circuit family. We then prove a generic result showing that the difficulty of accomplishing a computational task on uniformly random inputs implies its difficulty on any fixed, ingenerable sequence. We use this result to derandomize quantum cryptographic games that relate to cloning, and then incorporate a result of Kundu and Tan (arXiv 2022) to obtain uncloneable advice. Applying this two-step process to a monogamy-of-entanglement game yields a promise problem with uncloneable advice, and applying it to the quantum copy-protection of pseudorandom functions with super-logarithmic output lengths yields a language with uncloneable advice.

We show the unconditional existence of promise problems admitting uncloneable quantum advice, and the existence of languages with uncloneable advice, assuming the feasibility of quantum copy-protecting certain functions

CV and Thesis


Get In Touch

  • Visiting Address

    UCL Department of Computer Science
    Room B.09
    Gower Street 66-72, London WC1E 6BT
  • Snail mail Address

    Computer Science
    University College London
    Gower Street 66-72
    London WC1E 6BT
    United Kingdom
  • Email

    martti.karvonen{the squiggly symbol}ucl.ac.uk