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.
Benjamin Merlin Bumpus (he/him) (Apr 26 2024 at 17:11):Dear colleagues,
I am pleased to announce a new conference series focused on the interactions of categorical abstractions and algorithms. The conference will run from the 12th to the 16th of August and it will be held at the University of Florida (Gainesville, FL). Abstract submission is now open and you can find details of the conference here. I look forward to seeing many of you there!
The Abstract Methods in Multivariate Algorithmics (AMMA) is an international workshop bringing together two mathematical communities: (1) researchers in parameterized (multivariate) complexity theory and (2) researchers in applied topology and category theory. The two communities share many core goals such as understanding compositional systems and compositional algorithms and the systematic confinement of emergent complexity (such as combinatorial explosion). The workshop will consist of a blend of invited and contributed talks as well as tutorials on parameterized complexity and applied category theory aiming to bridge the mathematical and linguistic gap between the two communities.
The topics may include but are not limited to:
Sheaves and dynamic programming
Well-quasi-ordering and encountered-instance algorithmic frameworks beyond worst-case analysis
Universal obstructions in graph structural width metrics and a general theory of such metrics
Abstract approaches to second-order Myhill-Nerode congruences and beyond
Diagram-completion paradigms in parameterized complexity such as solution diversity,
Transfer learning and dynamic input
General theories of purposeful kernelization
Parameterizing on quantization
Inductive gradients in parameterized algorithms
Problem-specific well quasi-ordering and functorial approaches to parameterized complexity classification
Abstract views of input normal forms such as graphs as lineal topologies
Abstract models of computation appropriate to truly linear FPT (O(n) + f(k)) algorithmics
Abstract models of graphs arising from data points plus metric knobs, and their natural decompositions.
Amar Hadzihasanovic (Apr 27 2024 at 07:09):Hey, not to be critical, but as somebody who comes from the categorical side and is interested in approaching the complexity side -- and I don't think it's a huge number of us -- I find very little that is familiar or recognisable to me in that list of topics.
Perhaps there's a different community of applied category theorists that I'm unaware of (in the US?), and to whom this does speak, but my immediate reaction is that if you want to bridge a "linguistic gap", you are not throwing hooks in equal measure towards the two sides.
Amar Hadzihasanovic (Apr 27 2024 at 07:22):For example, because a lot of category theory is done in European computer science departments that are "Theory B"-leaning, it is very likely that applied category theorists that are interested in complexity theory are more familiar with logical and semantic approaches such as implicit computational complexity — I am aware that this is perceived as Eurotrash by many in America, but in my opinion it would be a natural place where to look for a point of contact; but then again maybe I don't have a good picture of what other subcommunities exist
Morgan Rogers (he/him) (Apr 27 2024 at 14:31):Amar Hadzihasanovic said:
as somebody who comes from the categorical side and is interested in approaching the complexity side -- and I don't think it's a huge number of us -- I find very little that is familiar or recognisable to me in that list of topics.
I second that!
Damiano Mazza (Apr 27 2024 at 16:24):Yes the list of topics seems to contain extremely specific subjects and lots of technical keywords, I wish I understood what they mean! I am very interested in connexions between categories and complexity, but I am only vaguely familiar with parametrized complexity, I suppose that's why I'm lost...
Damiano Mazza (Apr 27 2024 at 16:33):Adding to @Amar Hadzihasanovic's comment, the kind of applied category theorists that I have in mind when I think of complexity are, for example, those attending the Structure Meets Power workshop series. My impression is that AMMA is quite orthogonal, but it wouldn't be a bad idea to make the two communities interact!
Benjamin Merlin Bumpus (he/him) (Apr 29 2024 at 18:27):Hi Amar, Morgan and Damiano. Thanks for the comments. I guess you're hitting the nail on the head: at the moment there is little work being done at the intersection of parameterized complexity theory (PCT) and category theory, but many in the PCT community feel like the time is ripe for an algebraic organisation of the field.
@Amar Hadzihasanovic as you point out, most interactions of CT with computer science are more leaning towards theory B. This conference is trying to change that. My hope is that AMMA will provide a space for these two communities to speak to each other. Our plan is to have two "tutorial" sessions: one for PCT and one for ACT so that we can start bridging the linguistic divide. The topics we listed are merely examples of concepts that the PCT community would really like more theory for, so, if you don't recognise them, that's great: hopefully you'll join us for the conference and help us figure out how to categorify them! :grinning_face_with_smiling_eyes:
@Damiano Mazza I agree with your assessment that AMMA shares similarities with structure meets power. Although they have different flavors (AMMA is not so tightly tied to model theory, for instance), it would be good to have much more cross-pollination between the communities.
Kevin Carlson (Apr 29 2024 at 18:29):I guess a concrete question is how people from the ACT side should decide what kind of talks to contribute, given that there's little ACT work so far close to the topics you're interested in!
Benjamin Merlin Bumpus (he/him) (Apr 29 2024 at 18:41):That's a great question. I think that people in ACT can contribute in two ways:
From the perspective of people in the PCT community: it's hard to formulate questions to category theorists if they aren't aware of the kinds of things that category theory can already do.
As an example, together with my collaborators, I have recently been studying time-varying data and dynamic programming algorithms using category-theoretic (and sheaf-theoretic) tools. This has been very well received in the parameterized complexity community where many people have started asking about what sorts of things category theory can do for them.
If you have any ideas or suggestions about topics that you think would be of interest to people in complexity theory, please get in touch. Also feel free to ask any more questions! :tada:
Kevin Carlson (Apr 29 2024 at 18:44):Yeah, your work is very naturally the best example of overlap so far. Thanks for the fleshing-out!
Benjamin Merlin Bumpus (he/him) (Apr 29 2024 at 18:51):No problem at all!
I'm really excited about building bridges between these communities. The aim is to create a space where we can all come together and share concepts and start a dialogue about compositionality and how to make sense of it in ways that are simultaneously categorically elegant and computationally useful. :partying_face:
Ryan Wisnesky (Apr 29 2024 at 19:52):In database theory, combined complexity is useless because all problems are exponential. So theorists study "data complexity" - how runtime scales when queries are parameters and data size varies, and query complexity - how runtime scales when data is a parameter and query size varies. This works extremely well because in practice, queries tend to be very small and data tends to be very large. If I understand AMMA correctly, it is pursuing a similar strategy but for additional things besides queries and databases (pro -functors and pre-sheaves, if you will). So I'm wondering/hoping if results of the form "categorical abstraction X is exactly AMMA abstraction Y" are welcome?
Benjamin Merlin Bumpus (he/him) (Apr 29 2024 at 20:00):Hi Ryan, yes this sort of work would definitely be welcome!
Amar Hadzihasanovic (Apr 30 2024 at 08:53):@Benjamin Merlin Bumpus (he/him) Just to clarify, I completely sympathise with your goals and I think it's a shame that there isn't much contact between CT and “Theory A”-complexity -- I did not mean to suggest at all that the aim of the conference should be modified.
Rather, like others have pointed out, I was left confused as to what ACtheorists were expected to contribute; and, at the same time, if contributions from ACtheorists are expected, I thought it would be natural to try to "fish" them out of those who have already been interested in complexity theory, even if it was from a “Theory B”-perspective.
Amar Hadzihasanovic (Apr 30 2024 at 08:56):For example, I think that a nod to something very general like “Functorial approaches to quantitative bounds” or something like that would have reassured me that this was not necessarily “for somebody else” :D
Benjamin Merlin Bumpus (he/him) (May 01 2024 at 18:23):Hi Amar, thanks for the message! That’s a good suggestion, I’ll see that it’s added to the website!
I hope to see you in Florida :hibiscus: for AMMA!