Publications
My academic articles sorted in reverse chronological order.
2025
-
Empirical measures and strong laws of large numbers in categorical probability2025The Glivenko–Cantelli theorem is a uniform version of the strong law of large numbers. It states that for every IID sequence of random variables, the empirical measure converges to the underlying distribution (in the sense of uniform convergence of the CDF). In this work, we provide tools to study such limits of empirical measures in categorical probability. We propose two axioms, namely permutation invariance and empirical adequacy, that a morphism of type X^\mathbbN \to X should satisfy to be interpretable as taking an infinite sequence as input and producing a sample from its empirical measure as output. Since not all sequences have a well-defined empirical measure, such \textitempirical sampling morphisms live in quasi-Markov categories, which, unlike Markov categories, allow for partial morphisms. Given an empirical sampling morphism and a few other properties, we prove representability as well as abstract versions of the de Finetti theorem, the Glivenko–Cantelli theorem and the strong law of large numbers. We provide several concrete constructions of empirical sampling morphisms as partially defined Markov kernels on standard Borel spaces. Instantiating our abstract results then recovers the standard Glivenko–Cantelli theorem and the strong law of large numbers for random variables with finite first moment. Our work thus provides a joint proof of these two theorems in conjunction with the de Finetti theorem from first principles.
@article{fritz2025empirical, title = {Empirical measures and strong laws of large numbers in categorical probability}, author = {Fritz, Tobias and Gonda, Tom{\'a}{\v{s}} and Lorenzin, Antonio and Perrone, Paolo and Mohammed, Areeb Shah}, year = {2025}, } -
Epistemic horizons from deterministic laws: Lessons from a nomic toy theoryJohannes Fankhauser, Tomáš Gonda, and Gemma De les CovesSynthese, 2025Quantum theory has an epistemic horizon, i.e. exact values cannot be assigned simultaneously to incompatible physical quantities. As shown by Spekkens’ toy theory, positing an epistemic horizon akin to Heisenberg’s uncertainty principle in a classical mechanical setting also leads to a plethora of quantum phenomena. We introduce a deterministic theory - nomic toy theory - in which information gathering agents are explicitly modelled as physical systems. Our main result shows the presence of an epistemic horizon for such agents. They can only simultaneously learn the values of observables whose Poisson bracket vanishes. Therefore, nomic toy theory has incompatible measurements and the complete state of a physical system cannot be known. The best description of a system by an agent is via an epistemic state of Spekkens’ toy theory. Our result reconciles us to measurement uncertainty as an aspect of the inseparability of subjects and objects. Significantly, the claims follow even though nomic toy theory is essentially classical. This work invites further investigations of epistemic horizons, such as the one of (full) quantum theory.
@article{fankhauser2025epistemic, title = {Epistemic horizons from deterministic laws: {L}essons from a nomic toy theory}, author = {Fankhauser, Johannes and Gonda, Tom{\'a}{\v{s}} and {De les Coves}, Gemma}, journal = {Synthese}, volume = {205}, number = {4}, pages = {136}, year = {2025}, doi = {10.1007/s11229-024-04852-0}, publisher = {Springer Netherlands Dordrecht}, } -
Conceptual and formal groundwork for the study of resource dependence relationsYı̀lè Yı̄ng, Tomáš Gonda, and Robert SpekkensJournal of Physics A: Mathematical and Theoretical, 2025A resource theory imposes a preorder over states, with one state being above another if the first can be converted to the second by a free operation, and where the set of free operations defines the notion of resourcefulness under study. In general, the location of a state in the preorder of one resource theory can constrain its location in the preorder of a different resource theory. It follows that there can be nontrivial dependence relations between different notions of resourcefulness. In this article, we lay out the conceptual and formal groundwork for the study of resource dependence relations. In particular, we note that the relations holding among a set of monotones that includes a complete set for each resource theory provides a full characterization of resource dependence relations. As an example, we consider three resource theories concerning the about-face asymmetry properties of a qubit along three mutually orthogonal axes on the Bloch ball, where about-face symmetry refers to a representation of \mathbbZ_2, consisting of the identity map and a \pi rotation about the given axis. This example is sufficiently simple that we are able to derive a complete set of monotones for each resource theory and to determine all of the relations that hold among these monotones, thereby completely solving the problem of determining resource dependence relations. Nonetheless, we show that even in this simplest of examples, these relations are already quite nuanced.
@article{ying2025conceptual, title = {Conceptual and formal groundwork for the study of resource dependence relations}, author = {Y{\=\i}ng, Y{\`\i}l{\`e} and Gonda, Tom{\'a}{\v{s}} and Spekkens, Robert}, journal = {Journal of Physics A: Mathematical and Theoretical}, volume = {58}, number = {33}, pages = {335303}, year = {2025}, doi = {10.1088/1751-8121/adf307}, publisher = {IOP Publishing}, } -
The Aldous–Hoover theorem in categorical probabilityAlgebraic Statistics, 2025The Aldous-Hoover Theorem concerns an infinite matrix of random variables whose distribution is invariant under finite permutations of rows and columns. It states that, up to equality in distribution, each random variable in the matrix can be expressed as a function only depending on four key variables: one common to the entire matrix, one that encodes information about its row, one that encodes information about its column, and a fourth one specific to the matrix entry. We state and prove the theorem within a category-theoretic approach to probability, namely the theory of Markov categories. This makes the proof more transparent and intuitive when compared to measure-theoretic ones. A key role is played by a newly identified categorical property, the Cauchy–Schwarz axiom, which also facilitates a new synthetic de Finetti Theorem. We further provide a variant of our proof using the ordered Markov property and the d-separation criterion, both generalized from Bayesian networks to Markov categories. We expect that this approach will facilitate a systematic development of more complex results in the future, such as categorical approaches to hierarchical exchangeability.
@article{chen2025aldous, title = {The {A}ldous--{H}oover theorem in categorical probability}, author = {Chen, Leihao and Fritz, Tobias and Gonda, Tom{\'a}{\v{s}} and Klingler, Andreas and Lorenzin, Antonio}, journal = {Algebraic Statistics}, volume = {16}, number = {2}, pages = {131--174}, year = {2025}, doi = {10.2140/astat.2025.16.131}, publisher = {Mathematical Sciences Publishers}, }
2024
-
A framework for universality in physics, computer science, and beyondTomáš Gonda, Tobias Reinhart, Sebastian Stengele, and Gemma De les CovesCompositionality, 2024Turing machines and spin models share a notion of universality according to which some simulate all others. Is there a theory of universality that captures this notion? We set up a categorical framework for universality which includes as instances universal Turing machines, universal spin models, NP completeness, top of a preorder, denseness of a subset, and more. By identifying necessary conditions for universality, we show that universal spin models cannot be finite. We also characterize when universality can be distinguished from a trivial one and use it to show that universal Turing machines are non-trivial in this sense. Our framework allows not only to compare universalities within each instance, but also instances themselves. We leverage a Fixed Point Theorem inspired by a result of Lawvere to establish that universality and negation give rise to unreachability (such as uncomputability). As such, this work sets the basis for a unified approach to universality and invites the study of further examples within the framework.
@article{gonda2024framework, title = {A framework for universality in physics, computer science, and beyond}, author = {Gonda, Tom{\'a}{\v{s}} and Reinhart, Tobias and Stengele, Sebastian and {De les Coves}, Gemma}, journal = {Compositionality}, volume = {6}, year = {2024}, doi = {10.46298/compositionality-6-3}, publisher = {Episciences.org}, } -
Resource-theoretic hierarchy of contextuality for general probabilistic theoriesLorenzo Catani, Thomas D Galley, and Tomáš Gonda2024In this work we present a hierarchy of generalized contextuality. It refines the traditional binary distinction between contextual and noncontextual theories, and facilitates their comparison based on how contextual they are. Our approach focuses on the contextuality of prepare-and-measure scenarios, described by general probabilistic theories (GPTs). To motivate the hierarchy, we define it as the resource ordering of a novel resource theory of GPT-contextuality. The building blocks of its free operations are classical systems and univalent simulations between GPTs. These simulations preserve operational equivalences and thus cannot generate contextuality. Noncontextual theories can be recovered as least elements in the hierarchy. We then define a new contextuality monotone, called classical excess, given by the minimal error of embedding a GPT within an infinite classical system. In addition, we show that the optimal success probability in the parity oblivious multiplexing game also defines a monotone in our resource theory. Finally, we discuss whether the non-free operations can be understood as implementing information erasure and thus explaining the fine-tuning aspect of contextuality.
@article{catani2024resource, title = {Resource-theoretic hierarchy of contextuality for general probabilistic theories}, author = {Catani, Lorenzo and Galley, Thomas D and Gonda, Tom{\'a}{\v{s}}}, year = {2024}, } -
An Invitation to universality in physics, computer Science, and beyondTomáš Gonda and Gemma De les Coves2024A universal Turing machine is a powerful concept - a single device can compute any function that is computable. A universal spin model, similarly, is a class of physical systems whose low energy behavior simulates that of any spin system. Our categorical framework for universality (\hrefhttps://arxiv.org/abs/2307.06851arXiv:2307.06851) captures these and other examples of universality as instances. In this article, we present an accessible account thereof with a focus on its basic ingredients and ways to use it. Specifically, we show how to identify necessary conditions for universality, compare types of universality within each instance, and establish that universality and negation give rise to unreachability (such as uncomputability).
@article{gonda2024invitation, title = {An Invitation to universality in physics, computer Science, and beyond}, author = {Gonda, Tom{\'a}{\v{s}} and {De les Coves}, Gemma}, year = {2024}, }
2023
-
Representable Markov categories and comparison of statistical experiments in categorical probabilityTheoretical computer science, 2023Markov categories are a recent categorical approach to the mathematical foundations of probability and statistics. Here, this approach is advanced by stating and proving equivalent conditions for second-order stochastic dominance, a widely used way of comparing probability distributions by their spread. Furthermore, we lay foundation for the theory of comparing statistical experiments within Markov categories by stating and proving the classical Blackwell-Sherman-Stein Theorem. Our version not only offers new insight into the proof, but its abstract nature also makes the result more general, automatically specializing to the standard Blackwell-Sherman-Stein Theorem in measure-theoretic probability as well as a Bayesian version that involves prior-dependent garbling. Along the way, we define and characterize representable Markov categories, within which one can talk about Markov kernels to or from spaces of distributions. We do so by exploring the relation between Markov categories and Kleisli categories of probability monads.
@article{fritz2023representable, title = {Representable {M}arkov categories and comparison of statistical experiments in categorical probability}, author = {Fritz, Tobias and Gonda, Tom{\'a}{\v{s}} and Perrone, Paolo and Rischel, Eigil Fjeldgren}, journal = {Theoretical computer science}, volume = {961}, pages = {113896}, year = {2023}, doi = {10.1016/j.tcs.2023.113896}, publisher = {Elsevier}, } -
Dilations and information flow axioms in categorical probabilityTobias Fritz, Tomáš Gonda, Nicholas Gauguin Houghton-Larsen, Antonio Lorenzin, Paolo Perrone, and Dario SteinMathematical Structures in Computer Science, 2023We study the positivity and causality axioms for Markov categories as properties of dilations and information flow in Markov categories, and in variations thereof for arbitrary semicartesian monoidal categories. These help us show that being a positive Markov category is merely an additional property of a symmetric monoidal category (rather than extra structure). We also characterize the positivity of representable Markov categories and prove that causality implies positivity, but not conversely. Finally, we note that positivity fails for quasi-Borel spaces and interpret this failure as a privacy property of probabilistic name generation.
@article{fritz2023dilations, title = {Dilations and information flow axioms in categorical probability}, author = {Fritz, Tobias and Gonda, Tom{\'a}{\v{s}} and Houghton-Larsen, Nicholas Gauguin and Lorenzin, Antonio and Perrone, Paolo and Stein, Dario}, journal = {Mathematical Structures in Computer Science}, volume = {33}, number = {10}, pages = {913--957}, year = {2023}, doi = {10.1017/S0960129523000324}, publisher = {Cambridge University Press}, } -
Absolute continuity, supports and idempotent splitting in categorical probability2023Markov categories have recently turned out to be a powerful high-level framework for probability and statistics. They accommodate purely categorical definitions of notions like conditional probability and almost sure equality, as well as proofs of fundamental results such as the Hewitt–Savage 0/1 Law, the de Finetti Theorem and the Ergodic Decomposition Theorem. In this work, we develop additional relevant notions from probability theory in the setting of Markov categories. This comprises improved versions of previously introduced definitions of absolute continuity and supports, as well as a detailed study of idempotents and idempotent splitting in Markov categories. Our main result on idempotent splitting is that every idempotent measurable Markov kernel between standard Borel spaces splits through another standard Borel space, and we derive this as an instance of a general categorical criterion for idempotent splitting in Markov categories.
@article{fritz2023absolute, title = {Absolute continuity, supports and idempotent splitting in categorical probability}, author = {Fritz, Tobias and Gonda, Tom{\'a}{\v{s}} and Lorenzin, Antonio and Perrone, Paolo and Stein, Dario}, year = {2023}, } -
Monotones in general resource theoriesTomáš Gonda and Robert W SpekkensCompositionality, 2023A central problem in the study of resource theories is to find functions that are nonincreasing under resource conversions - termed monotones - in order to quantify resourcefulness. Various constructions of monotones appear in many different concrete resource theories. How general are these constructions? What are the necessary conditions on a resource theory for a given construction to be applicable? To answer these questions, we introduce a broad scheme for constructing monotones. It involves finding an order-preserving map from the preorder of resources of interest to a distinct preorder for which nontrivial monotones are previously known or can be more easily constructed; these monotones are then pulled back through the map. In one of the two main classes we study, the preorder of resources is mapped to a preorder of sets of resources, where the order relation is set inclusion, such that monotones can be defined via maximizing or minimizing the value of a function within these sets. In the other class, the preorder of resources is mapped to a preorder of tuples of resources, and one pulls back monotones that measure the amount of distinguishability of the different elements of the tuple (hence its information content). Monotones based on contractions arise naturally in the latter class, and, more surprisingly, so do weight and robustness measures. In addition to capturing many standard monotone constructions, our scheme also suggests significant generalizations of these. In order to properly capture the breadth of applicability of our results, we present them within a novel abstract framework for resource theories in which the notion of composition is independent of the types of the resources involved (i.e., whether they are states, channels, combs, etc.).
@article{gonda2023monotones, title = {Monotones in general resource theories}, author = {Gonda, Tom{\'a}{\v{s}} and Spekkens, Robert W}, journal = {Compositionality}, volume = {5}, year = {2023}, doi = {10.32408/compositionality-5-7}, publisher = {Episciences.org}, }
2021
-
De Finetti’s theorem in categorical probabilityTobias Fritz, Tomáš Gonda, and Paolo PerroneJournal of Stochastic Analysis, 2021We present a novel proof of de Finetti’s Theorem characterizing permutation-invariant probability measures of infinite sequences of variables, so-called exchangeable measures. The proof is phrased in the language of Markov categories, which provide an abstract categorical framework for probability and information flow. The diagrammatic and abstract nature of the arguments makes the proof intuitive and easy to follow. We also show how the usual measure-theoretic version of de Finetti’s Theorem for standard Borel spaces is an instance of this result.
@article{fritz2021finetti, title = {De {F}inetti's theorem in categorical probability}, author = {Fritz, Tobias and Gonda, Tom{\'a}{\v{s}} and Perrone, Paolo}, journal = {Journal of Stochastic Analysis}, volume = {2}, number = {No. 4, Article 6}, doi = {10.31390/josa.2.4.06}, year = {2021}, } -
Resource theories as quantale modulesTomáš GondaUniversity of Waterloo, 2021PhD ThesisWe aim to counter the tendency for specialization in science by advancing a language that can facilitate the translation of ideas and methods between disparate contexts. The focus is on questions of "resource-theoretic nature". In a resource theory, one identifies resources and allowed manipulations that can be used to transform them. Some of the main questions are: How to optimize resources? What are the trade-offs between them? Can a given resource be converted to another one via the allowed manipulations? Because of their ubiquity, methods used to answer them in one context can be used to tackle corresponding questions in new contexts. The translation occurs in two stages. Firstly, methods are generalized to the abstract language. Then, one can determine whether potentially novel contexts can accommodate them. We focus on the first stage, by introducing two variants of an abstract framework in which existing and yet unidentified resource theories can be represented. Using these, the task of generalizing concrete methods is tackled in chapter 4 by studying the ways in which meaningful measures of resources may be constructed. One construction expresses a notion of cost (or yield) of a resource. Among other applications, it may be used to extend measures from a subset of resources to a larger domain. Another construction allows the translation of resource measures from one resource theory to another. Special cases include resource robustness and weight measures, as well as relative entropy based measures quantifying minimal distinguishability from freely available resources. We instantiate some of these ideas in a resource theory of distinguishability in chapter 5. It describes the utility of systems with probabilistic behavior for the task of distinguishing between hypotheses, which said behavior may depend on.
@phdthesis{gonda2021resource, title = {Resource theories as quantale modules}, author = {Gonda, Tom{\'a}{\v{s}}}, year = {2021}, school = {University of Waterloo}, note = {PhD Thesis}, }
2018
-
Almost quantum correlations are inconsistent with Specker’s principleQuantum, 2018Ernst Specker considered a particular feature of quantum theory to be especially fundamental, namely that pairwise joint measurability of sharp measurements implies their global joint measurability. To date, Specker’s principle seemed incapable of singling out quantum theory from the space of all general probabilistic theories. In particular, its well-known consequence for experimental statistics, the principle of consistent exclusivity, does not rule out the set of correlations known as almost quantum, which is strictly larger than the set of quantum correlations. Here we show that, contrary to the popular belief, Specker’s principle cannot be satisfied in any theory that yields almost quantum correlations.
@article{gonda2018almost, title = {Almost quantum correlations are inconsistent with {S}pecker's principle}, author = {Gonda, Tom{\'a}{\v{s}} and Kunjwal, Ravi and Schmid, David and Wolfe, Elie and Sainz, Ana Bel{\'e}n}, journal = {Quantum}, volume = {2}, pages = {87}, year = {2018}, doi = {10.22331/q-2018-08-27-87}, }