![[Berkeley Seminar] Michael Arntzenius (Topos Institute) | A perfect join algorithm? @ToposInstitute](https://i.ytimg.com/vi/ambisA2jegA/maxresdefault.jpg)
Uploaded September 2026 | Updated September 2026, 2 weeks ago
Title: A perfect join algorithm? Answering queries in optimal time: Yannakakis’ algorithm
Abstract: If we have a query over some database, how fast can we find all answers for it? If we don’t assume any additional structure (such as indexes on the database), the best possible time is O(IN + OUT): that is, the size of the input (the database) plus the size of the output (the matches for the query). Since we didn’t assume anything about the structure the database is in, any part of it could be relevant, so we have to read the entire database; and by definition we have to write the entire output. Is this achievable? It is, for a particular class of queries: the α-acyclic queries. In this talk I’ll explain how to view queries (and databases) as labelled hypergraphs, define α-acyclicity, and show why and how it allows us to answer queries in linear time using Yannakakis’ algorithm (YA). If I have time, I may: - explain more practical variants on YA such as TreeTrackerJoin - explain the fractional edge cover bound on a query/hypergraph, and how to achieve it using worst-case optimal joins, which handle cyclic queries. - (unlikely) explain further generalizations such as hypertree decompositions of queries.
Date: Aug 4, 2026
Title: A perfect join algorithm? Answering queries in optimal time: Yannakakis’ algorithm
Abstract: If we have a query over some database, how fast can we find all answers for it? If we don’t assume any additional structure (such as indexes on the database), the best possible time is O(IN + OUT): that is, the size of the input (the database) plus the size of the output (the matches for the query). Since we didn’t assume anything about the structure the database is in, any part of it could be relevant, so we have to read the entire database; and by definition we have to write the entire output. Is this achievable? It is, for a particular class of queries: the α-acyclic queries. In this talk I’ll explain how to view queries (and databases) as labelled hypergraphs, define α-acyclicity, and show why and how it allows us to answer queries in linear time using Yannakakis’ algorithm (YA). If I have time, I may: - explain more practical variants on YA such as TreeTrackerJoin - explain the fractional edge cover bound on a query/hypergraph, and how to achieve it using worst-case optimal joins, which handle cyclic queries. - (unlikely) explain further generalizations such as hypertree decompositions of queries.
Date: Aug 4, 2026
![[Berkeley Seminar] Michael Arntzenius (Topos Institute) | A perfect join algorithm?](https://i.ytimg.com/vi/ambisA2jegA/mqdefault.jpg "[Berkeley Seminar] Michael Arntzenius (Topos Institute) | A perfect join algorithm?
Title: A perfect join algorithm? Answering queries in optimal time: Yannakakis’ algorithm
Abstract: If we have a query over some database, how fast can we find all answers for it? If we don’t assume any additional structure (such as indexes on the database), the best possible time is O(IN + OUT): that is, the size of the input (the database) plus the size of the output (the matches for the query). Since we didn’t assume anything about the structure the database is in, any part of it could be relevant, so we have to read the entire database; and by definition we have to write the entire output. Is this achievable? It is, for a particular class of queries: the α-acyclic queries. In this talk I’ll explain how to view queries (and databases) as labelled hypergraphs, define α-acyclicity, and show why and how it allows us to answer queries in linear time using Yannakakis’ algorithm (YA). If I have time, I may: - explain more practical variants on YA such as TreeTrackerJoin - explain the fractional edge cover bound on a query/hypergraph, and how to achieve it using worst-case optimal joins, which handle cyclic queries. - (unlikely) explain further generalizations such as hypertree decompositions of queries.
Date: Aug 4, 2026")
![[Berkeley Seminar] Kevin Carlson | Does it matter whether there are infinite sets?](https://i.ytimg.com/vi/bHKvT1ZACLY/mqdefault.jpg "[Berkeley Seminar] Kevin Carlson | Does it matter whether there are infinite sets?
Title: Does it matter whether there are infinite sets?
Abstract: This talk is mostly an exposition of a bit of philosophy and a bit of math due to JP Mayberry, included by but not necessarily co-limited to (1) the claim that yes, Virginia, you actually do want a foundation (2) that its set theory (3) that this has to be given in the naive Euclid-style sense of the axiomatic method (4) that what this foundation founds is, mainly, the modern structuralist sense of the axiomatic method (so that set theory and category theory are friends after all!) (5) that youre supposed to actually believe the axioms in a traditional Euclid-style axiomatic system (6) that, actually, its not hard to give an explanation of set theory that leads to you actually believing all the axioms (7) EXCEPT the so-called axiom of infinity, which is profoundly non-obvious (8) but highly fruitful so could we really get away without it? (9) a beginning of an anti-Cantorian set theory (so every set is finite) in which nonetheless you seem to have a good chance at doing modern math.
Well...Who cares? I suggest that you might care if you are (a) someone who programs, no doubt having noted that your data structures are actually always finite (b) someone who deals with large objects such as the category of all sets in your math. Mayberrys anti-Cantorian set theory has a clearer treatment of how we ought to correctly approach big objects than any other treatment I know.")
![[Berkeley Seminar] Dennis Chen | Cartesian polynomial monads in HoTT](https://i.ytimg.com/vi/bw3F3iUXBas/mqdefault.jpg "[Berkeley Seminar] Dennis Chen | Cartesian polynomial monads in HoTT
Title: Cartesian polynomial monads in HoTT
Date: November 13, 2024
Abstract: Modern math has shown the necessity of higher categories and higher structures. Infinite coherence data arises quite naturally as one considers various types of topological spaces and homotopy theory, as well as modern treatments of algebraic geometry. One can see simple versions of this problem already when looking at path composition in a topological space. Path composition is not strictly associative, but only associative up to a higher cell. One promising method of presenting higher structures is the development of homotopy type theory, which formulates spaces (up to homtopy equivalence) as its basic objects. However one major obstacle is notating the infinite coherences of infinity categories in homotopy type theory. This is due to the autophagy problem: how can one talk about algebraic structures on types, if the algebraic structures themselves are encoded as types? Here we discuss a solution to the problem by Finster, Allioux, and Sozeau by axiomatizing the nature of polynomial monads, hence allowing themselves certain computational equalities. They then go on to use these polynomial monads to discuss higher structures including higher categories. Essential to their method is Baez and Dolans slice construction, which is able to capture infinite coherences of polynomial monads even if one starts from very strict, classical polynomial monads. This integration of HoTT with polynomial monads I believe is incredibly interesting and could prove to be a very useful foundation/computational system.
https://topos.site/events/berkeley-seminar/")
![[Oxford Seminar] David Corfield | Charles Peirce, inference, and category theory](https://i.ytimg.com/vi/c6-rGLK1Mps/mqdefault.jpg "[Oxford Seminar] David Corfield | Charles Peirce, inference, and category theory
Oxford Seminar, 20th of February 2025
The American philosopher Charles Saunders Peirce (1839-1914) had much to say about the nature of intellectual enquiry. In the realm of deductive logic, category theorists have made important use of his string-diagrammatic logical calculus. But Peirces interests in inference extended beyond deduction to induction and abduction. In this talk I shall be exploring the thesis that we can understand this triple in terms of the category-theoretic notions of composition, extension and lift. We will also touch on his broader semiotics and his account of concept formation.")
![[Berkeley Seminar] Gabriel Goren-Roig | Arboreal coreflections](https://i.ytimg.com/vi/cBtySZMrtgA/mqdefault.jpg "[Berkeley Seminar] Gabriel Goren-Roig | Arboreal coreflections
Title: Arboreal coreflections
Abstract: Arboreal categories are categories of objects with an intrinsic, tree-like process structure giving rise to a bisimilarity relation between objects. This relation can then be transported along an adjunction into an “extensional” category, whose objects are usually relational structures. In this way, the main examples of these so-called arboreal adjunctions recover logical equivalence for various fragments of infinitary first-order logic. This abstract framework provides a solid foundation for game comonads and has been used to obtain extensions and variations of substantial resource-sensitive model-theoretic results such as Rossman’s equirank preservation theorem. However, a key open question is whether we can systematically chart the landscape of the correspondence between logics and arboreal adjunctions.
In this talk, we explore this landscape by focusing on coreflective arboreal adjunctions. As is well known, the theory of (co)monads simplifies greatly in the idempotent case and, accordingly, known idempotent game comonads correspond to variants of basic modal logic, which sit on the lower end of the expressive power spectrum. After reviewing the definition of arboreal categories, we will introduce the concept of a “seed”: a full subcategory of structures generating an arboreal coreflective subcategory via colimit. We will explain some results that help us identify seeds and hence move towards a potential classification theorem. In particular, we will leverage density comonads to characterize coreflective subcategories without explicitly constructing the coreflector. Finally, we will show some examples of arboreal categories that can be obtained employing our results.
Date: July 2, 2025
https://topos.institute/events/berkeley-seminar/")
![[Oxford Seminar] Virginie Debauche | The Path-Complete Formalism for Switched Systems](https://i.ytimg.com/vi/cckhqPmiVuw/mqdefault.jpg "[Oxford Seminar] Virginie Debauche | The Path-Complete Formalism for Switched Systems
Oxford Seminar, 17th of April 2025
TITLE: The Path-Complete Formalism for Switched Systems: Stability and Beyond
ABSTRACT: Switched systems play a crucial role in modern engineering thanks to their ability to capture complex behaviours involving transitions between different operational modes. However, analyzing their stability remains a challenging task due to the intricate interplay between discrete switching and dynamics. This complexity calls for sophisticated mathematical tools. While Lyapunov theory remains a cornerstone of stability analysis, traditional methods often fall short when applied to switched systems, prompting ongoing efforts to extend the theory to better accommodate their unique characteristics.
This talk presents the framework of path-complete Lyapunov functions, which offers a fresh perspective by integrating combinatorial structures to represent switching behaviour. Specifically, a path-complete Lyapunov function comprises two components: a combinatorial element, represented by an automaton (a directed graph) that encodes admissible switching sequences, and an algebraic element, consisting of a collection of Lyapunov functions—one for each node in the graph. The graph edges govern how these Lyapunov pieces interact and decrease across transitions. This framework is particularly appealing for the analysis of switched systems because it allows for the construction of tailored, nonstandard, and less conservative stability criteria, all while mitigating the combinatorial complexity that often burdens classical optimization techniques.
While originally introduced for stability analysis, the path-complete Lyapunov framework has been recently extended to encompass constrained switching systems, stabilization via switching sequence and control Lyapunov function design, and safety through path-complete barrier functions. This talk will highlight these recent developments and their unifying role within the framework.")
![[Oxford Seminar] Owen Lynch | An introduction to the geolog project](https://i.ytimg.com/vi/d6xMeIxsCM4/mqdefault.jpg "[Oxford Seminar] Owen Lynch | An introduction to the geolog project
Oxford Seminar, April 2 2026
Speaker: Owen Lynch
Full Title: An introduction to the geolog project
Abstract: Within the ARIA program, a number of researchers are working on a project called geolog. Geolog has some ambitious goals and some controversial theses; in this talk we will give an overview of these goals and theses alongside an intro to some of the math and computer science that we are using to attempt to achieve the goals and confirm the theses.")
![[2-torial] Categorical algebraic geometry, Part 2](https://i.ytimg.com/vi/dZKDEhOhz8E/mqdefault.jpg "[2-torial] Categorical algebraic geometry, Part 2
2-torial, July 28 2026
You can find accompanying notes and other information on this video at https://topos.institute/work/lectures/2-torials/2026-07-28_hosgood_geometry/
Speaker: Tim Hosgood
There are many approaches to algebraic geometry, and many different ways to arrive at the subject. Here were going to take an incredibly specific and biased approach: what if you already love 2-categories and want to be able to say the phrase fpqc sheaf as quickly as possible, but not /too/ quickly? In this series of exercises we will build towards an understanding of *relative algebraic geometry*, which allows us to work in arbitrary (nice) symmetric monoidal categories.")
