preprintContextads as Wreaths; Kleisli, Para, and Span Constructions as Wreath Products
We introduce contextads and the Ctx construction, unifying various structures and constructions in category theory dealing with context and contextful arrows -- comonads and their Kleisli construction, actegories and their Para construction, adequate triples and their Span construction. Contextads are defined in terms of Lack--Street wreaths, suitably categorified for pseudomonads in a tricategory of spans in a 2-category with display maps. The associated wreath product provides the Ctx construction, and by its universal property we conclude trifunctoriality. This abstract approach lets us work up to structure, and thus swiftly prove that, under very mild assumptions, a contextad equipped colaxly with a 2-algebraic structure produces a similarly structured double category of contextful arrows. We also explore the role contextads might play qua dependently graded comonads in organizing contextful computation in functional programming. We show that many side-effects monads can be dually captured by dependently graded comonads, and gesture towards a general result on the `transposability' of parametric right adjoint monads to dependently graded comonads.
paperA Fibrational Theory of First Order Differential Structures
- 2024
- Matteo Capucci, Geoffrey Cruttwell, Neil Ghani, Fabio Zanasi
- To appear in Fundamental Structures in Computational and Pure Mathematics
- https://doi.org/10.48550/arXiv.2409.05763
We develop a categorical framework for reasoning about abstract properties of differentiation, based on the theory of fibrations. Our work encompasses the first-order fragments of several existing categorical structures for differentiation, including cartesian differential categories, generalised cartesian differential categories, tangent categories, as well as the versions of these categories axiomatising reverse derivatives. We explain uniformly and concisely the requirements expressed by these structures, using sections of suitable fibrations as unifying concept. Our perspective sheds light on their similarities and differences, as well as simplifying certain constructions from the literature.
preprintAlgorithmic and Extremal Obstructions Through the Language of Cohomology
We model problems as presheaves that assign sets of certificates to input instances, and we show how to use presheaf Čech cohomology to capture the precise ways in which local solutions fail to patch into global ones. Applied to problems like Vertex Cover, Cycle Cover, and Odd Cycle Transversal, our framework exposes emergent phenomena such as hidden cycles or the inflation of small, local solutions. This approach not only rephrases classical results like König's Theorem in cohomological terms, but also reveals how to systematically account for failures of compositionality. Although our main focus is on presheaves of sets, the methods generalize naturally to Abelian presheaves, suggesting a rich interplay between graph theory, cohomology, and complexity. This work represents a first step toward a systematic, sheaf-theoretic theory of algorithmic structure and related obstructions.
paperOrganizing Physics with Open Energy-driven Systems
- 2024
- Matteo Capucci, Owen Lynch, David Spivak
- EPTCS (Proceedings of ACT 2024)
- https://doi.org/10.4204/EPTCS.429.16
Organizing physics has been a long-standing preoccupation of applied category theory, going back at least to Lawvere. We contribute to this research thread by noticing that Hamiltonian mechanics and gradient descent depend crucially on a consistent choice of transformation -- which we call a reaction structure -- from the cotangent bundle to the tangent bundle. We then construct a compositional theory of reaction structures. Reaction-based systems offer a different perspective on composition in physics than port-Hamiltonian systems or open classical mechanics, in that reaction-based composition does not create any new constraints that must be solved for algebraically.
The technical contributions of this paper are the development of symmetric monoidal categories of open energy-driven systems and open differential equations, and a functor between them, functioning as a "functorial semantics" for reaction structures. This approach echoes what has previously been done for open games and open gradient-based learners, and in fact subsumes the latter. We then illustrate our theory by constructing an n-fold pendulum as a composite of n-many pendula.
paperOn a fibrational construction for optics, lenses, and Dialectica categories
Categories of lenses/optics and Dialectica categories are both comprised of bidirectional morphisms of basically the same form. In this work we show how they can be considered a special case of an overarching fibrational construction, generalizing Hofstra's construction of Dialectica fibrations and Spivak's construction of generalized lenses. This construction turns a tower of Grothendieck fibrations into another tower of fibrations by iteratively twisting each of the components, using the opposite fibration construction.
preprintOn Quantifiers for Quantitative Reasoning
We explore a kind of first-order predicate logic with intended semantics in the reals. Compared to other approaches in the literature, we work predominantly in the multiplicative reals \( [0,\infty ] \), showing they support three generations of connectives, that we call non-linear, linear additive, and linear multiplicative. Means and harmonic means emerge as natural candidates for bounded existential and universal quantifiers, and in fact we see they behave as expected in relation to the other logical connectives. We explain this fact through the well-known fact that min/max and arithmetic mean/harmonic mean sit at opposite ends of a spectrum, that of \(p\)-means. We give syntax and semantics for this quantitative predicate logic, and as example applications, we show how softmax is the quantitative semantics of argmax, and Rényi entropy/Hill numbers are additive/multiplicative semantics of the same formula. Indeed, the additive reals also fit into the story by exploiting the Napierian duality \( -\log \dashv 1/\mathrm {exp} \), which highlights a formal distinction between 'additive' and 'multiplicative' quantities. Finally, we describe two attempts at a categorical semantics via enriched hyperdoctrines. We discuss why hyperdoctrines are in fact probably inadequate for this kind of logic.
talkSoftmax is Argmax, and the Logic of the Reals
- 2024
- Matteo Capucci
- MSP101
- Slides
- Video
I will report some work in progress on the semiotics of softmax. This is an operator used in machine learning (but familiar to physicists way before that) to normalize a log-distribution, turning a vector of (thus, a function valued in) logits (i.e. additive reals) into a probability distribution. Its name is due to the fact it acts as a 'probabilistic argmax', since the modes of a softmax distribution reflects the minima (by an accident of duality) of the function. I will show an attempt to make this statement precise, by exhibiting the semantics of a 'very linear logic' on the *-autonomous quantale of extended multiplicative reals. In this logic, additive connectives are also linear, but are still in the same algebraic relation with the multiplicative ones. I will show how to define quantifiers, and thus softmax. If time permits, I'll show a construction of an enriched equipment of relations in which softmax should be characterizable as a Kan lift, in the same way argmax is characterized as a Kan lift in relations.