I am Martti Karvonen,
a postdoc in computer science
at University College London.

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

Uncloneable Quantum Advice

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.
Broadbent, A., Karvonen, M. & Lord, S. (2023). Uncloneable Quantum Advice
PDF ArXiv

Categorical composable cryptography: extended version

We formalize the key ideas of constructive cryptography in categorical terms. This results in viewing cryptography as a resource theory in the sense of Fritz, Coecke & Spekkens: the resources are cryptographic functionalities and resources conversions are protocols that transform securely such resources to others. 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 also use 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. On the way, we exhibit two categorical constructions of resource theories that might be of independent interest: one capturing resources shared among n parties and one capturing resource conversions that succeed asymptotically.
Broadbent, A., & Karvonen, M. (2023). Categorical composable cryptography: extended version. To appear in LMCS.
PDF ArXiv

Inner autoequivalences in general and those of monoidal categories in particular

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.
Hofstra, P., & Karvonen, M. (2022). Inner autoequivalences in general and those of monoidal categories in particular.
PDF ArXiv

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

After an exposition of the sheaf-theoretic approach to contextuality, we discuss and answer the following question: given a function that maps empirical models over a scenario S to those over a scenario T, when is this function induced by a mapping between the scenarios? To answer this, we build a new scenario out of S and T, and associate to any such function an empirical model over this. Modulo some technicalities, a function between models is then induced by a map of scenarios iff the corresponding model is noncontextual.
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

Categorical composable cryptography

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.
Broadbent, A., & Karvonen, M. (2022). Categorical composable cryptography. In Foundations of Software Science and Computation Structures (FoSSaCS) 2022.
PDF BibTeX ArXiv Proceedings

Neither Contextuality nor Nonlocality Admits Catalysts

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.
Karvonen, M. (2021). Neither Contextuality nor Nonlocality Admits Catalysts. Phys. Rev. Lett. 127, 160402
PDF BibTeX ArXiv Journal

Biproducts without pointedness

Turns out one can define a well-behaved notion of a biproduct in any category without assuming 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

A comonadic view of simulation and quantum resources

We simplify and generalize the ideas in the QPL paper below.
Abramsky, S., Barbosa, R. S., Karvonen, M., & Mansfield, S. (2019). A comonadic view of simulation and quantum resources. In 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE.
PDF BibTeX ArXiv Proceedings

Limits in dagger categories

We define a notion of limit suitable for dagger categories and explore it.
Heunen, C., & Karvonen, M. (2019). Limits in dagger categories. Theory and Applications of Categories, Vol. 34, No. 18, 468-513.
PDF BibTeX ArXiv Journal

Reversible effects as inverse arrows

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.
Heunen, C., Kaarsgaard, R., & Karvonen, M. (2018). Reversible effects as inverse arrows. Proceedings of MFPS 2018. ENTCS, 341, 179-199.
PDF BibTeX ArXiv Proceedings

Categories of Empirical Models

A notion of morphism that is suitable for the sheaf-theoretic approach to contextuality is developed, resulting in a resource theory for contextuality.
Karvonen, M. (2018). Categories of empirical models. Proceedings of QPL 2018, EPTCS 287, pp. 239-252.
PDF BibTeX ArXiv

Monads on dagger categories

This is the extended version of the previous conference paper.
Heunen, C., & Karvonen, M. (2016). Monads on dagger categories. Theory and Applications of Categories, Vol. 31, No. 35, 1016-1043.
PDF BibTeX ArXiv Journal

Reversible monadic computing

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

CV and Thesis