You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.
Martin (Aug 13 2024 at 12:03):I'm working on complexity theory for databases, which is what led me to ACT: I'm trying to see whether category theory can say something interesting about my problems.
There is a notion of dynamic complexity formulated by Immermann and Patnaik. Essentially, for a relational database that is subject to change, auxiliary relations are maintained in another database over the same domain with the intention to help answering a query. When an update to the database (for simplicity, an insertion or deletion of a tuple) occurs, every auxiliary relation is updated through a first-order query that can refer to the database as well as to the auxiliary relations. The typical example is maintaining an st- graph (say, representing users of a social network who follow and unfollow one another over time) and trying to answer the query "is t reachable from s"?
The class of all queries maintainable in this way with first-order update formulas, is called Dyn-FO.
The actual formalization can be a bit finicky: see e.g. the introductory sections of this survey for one approach.
I believe this complexity class may admit a good categorical interpretation, and this would allow questions like the inexpressibility of certain problems within this class to be formulated and perhaps answered via sheaf theory and such, but I don't yet see how to carry this out. Am I barking up the wrong tree?
Emilio Minichiello (Aug 13 2024 at 12:53):This is the kind of question I am very interested in! I’ve been studying categorical database theory, but have been learning some complexity theory lately. Feel free to DM me
Emilio Minichiello (Aug 13 2024 at 13:31):Some possibly related work that may be of some interest: