Oxford, UK. 2019 July 22 – 26
Dear scientists, mathematicians, linguists, philosophers, and hackers,
We are writing to let you know about a fantastic opportunity to learn about the emerging interdisciplinary field of applied category theory from some of its leading researchers at the ACT2019 School. It will begin in January 2019 and culminate in a meeting in Oxford, July 22-26.
Applied category theory is a topic of interest for a growing community of researchers, interested in studying systems of all sorts using category-theoretic tools. These systems are found in the natural sciences and social sciences, as well as in computer science, linguistics, and engineering. The background and experience of our community’s members are as varied as the systems being studied.
The goal of the ACT2019 School is to help grow this community by pairing ambitious young researchers together with established researchers in order to work on questions, problems, and conjectures in applied category theory.
Who should apply?
Anyone from anywhere who is interested in applying category-theoretic methods to problems outside of pure mathematics. This is emphatically not restricted to math students, but one should be comfortable working with mathematics. Knowledge of basic category-theoretic language—the definition of monoidal category for example— is encouraged.
We will consider advanced undergraduates, Ph.D. students, and post-docs. We ask that you commit to the full program as laid out below.
Instructions on how to apply can be found below the research topic descriptions.
Senior research mentors and their topics
Below is a list of the senior researchers, each of whom describes a research project that their team will pursue, as well as the background reading that will be studied between now and July 2019.
Miriam Backens
Title: Simplifying quantum circuits using the ZX-calculus
Description: The ZX-calculus is a graphical calculus based on the category-theoretical formulation of quantum mechanics. A complete set of graphical rewrite rules is known for the ZX-calculus, but not for quantum circuits over any universal gate set. In this project, we aim to develop new strategies for using the ZX-calculus to simplify quantum circuits.
Background reading:
- Matthes Amy, Jianxin Chen, Neil Ross. A finite presentation of CNOT-Dihedral operators. arXiv:1701.00140
- Miriam Backens. The ZX-calculus is complete for stabiliser quantum mechanics. arXiv:1307.7025
Tobias Fritz
Title: Partial evaluations, the bar construction, and second-order stochastic dominance
Description: We all know that 2+2+1+1 evaluates to 6. A less familiar notion is that it can partially evaluate to 5+1. In this project, we aim to study the compositional structure of partial evaluation in terms of monads and the bar construction and see what this has to do with financial risk via second-order stochastic dominance.
Background reading:
- Tobias Fritz, Paolo Perrone. Monads, partial evaluations, and rewriting. arXiv:1810.06037
- Maria Manuel Clementino, Dirk Hofmann, George Janelidze. The monads of classical algebra are seldom weakly cartesian. Available here.
- Todd Trimble. On the bar construction. Available here.
Pieter Hofstra
Title: Complexity classes, computation, and Turing categories
Description: Turing categories form a categorical setting for studying computability without bias towards any particular model of computation. It is not currently clear, however, that Turing categories are useful to study practical aspects of computation such as complexity. This project revolves around the systematic study of step-based computation in the form of stack-machines, the resulting Turing categories, and complexity classes. This will involve a study of the interplay between traced monoidal structure and computation. We will explore the idea of stack machines qua programming languages, investigate the expressive power, and tie this to complexity theory. We will also consider questions such as the following: can we characterize Turing categories arising from stack machines? Is there an initial such category? How does this structure relate to other categorical structures associated with computability?
Background reading:
- J.R.B. Cockett, P.J.W. Hofstra. Introduction to Turing categories. APAL, Vol 156, pp 183-209, 2008. Available here .
- J.R.B. Cockett, P.J.W. Hofstra, P. Hrubes. Total maps of Turing categories. ENTCS (Proc. of MFPS XXX), pp 129-146, 2014. Available here.
- A. Joyal, R. Street, D. Verity. Traced monoidal categories. Mat. Proc. Cam. Phil. Soc. 3, pp. 447-468, 1996. Available here.
Bartosz Milewski
Title: Traversal optics and profunctors
Description: In functional programming, optics are ways to zoom into a specific part of a given data type and mutate it. Optics come in many flavors such as lenses and prisms and there is a well-studied categorical viewpoint, known as profunctor optics. Of all the optic types, only the traversal has resisted a derivation from first principles into a profunctor description. This project aims to do just this.
Background reading:
- Bartosz Milewski. Profunctor optics, categorical View. Available here.
- Craig Pastro, Ross Street. Doubles for monoidal categories. arXiv:0711.1859
Mehrnoosh Sadrzadeh
Title: Formal and experimental methods to reason about dialogue and discourse using categorical models of vector spaces
Description: Distributional semantics argues that meanings of words can be represented by the frequency of their co-occurrences in context. A model extending distributional semantics from words to sentences has a categorical interpretation via Lambek’s syntactic calculus or pregroups. In this project, we intend to further extend this model to reason about dialogue and discourse utterances where people interrupt each other, there are references that need to be resolved, disfluencies, pauses, and corrections. Additionally, we would like to design experiments and run toy models to verify predictions of the developed models.
Background reading:
- Gerhard Jager. A multi-modal analysis of anaphora and ellipsis. Available here.
- Matthew Purver, Ronnie Cann, Ruth Kempson. Grammars as parsers: Meeting the dialogue challenge. Available here.
David Spivak
Title: Toward a mathematical foundation for autopoiesis
Description: An autopoietic organization—anything from a living animal to a political party to a football team—is a system that is responsible for adapting and changing itself, so as to persist as events unfold. We want to develop mathematical abstractions that are suitable to found a scientific study of autopoietic organizations. To do this, we’ll begin by using behavioral mereology and graphical logic to frame a discussion of autopoiesis, most of all what it is and how it can be best conceived. We do not expect to complete this ambitious objective; we hope only to make progress toward it.
Background reading:
- Fong, Myers, Spivak. Behavioral mereology. arXiv:1811.00420.
- Fong, Spivak. Graphical regular logic. arXiv:1812.05765.
- Luhmann. Organization and Decision, CUP. (Preface)
School structure
All of the participants will be divided up into groups corresponding to the projects. A group will consist of several students, a senior researcher, and a TA. Between January and June, we will have a reading course devoted to building the background necessary to meaningfully participate in the projects. Specifically, two weeks are devoted to each paper from the reading list. During this two week period, everybody will read the paper and contribute to a discussion in a private online chat forum. There will be a TA serving as a domain expert and moderating this discussion. In the middle of the two week period, the group corresponding to the paper will give a presentation via video conference. At the end of the two week period, this group will compose a blog entry on this background reading that will be posted to the n-category cafe.
After all of the papers have been presented, there will be a two-week visit to Oxford University from 15 – 26 July 2019. The first week is solely for participants of the ACT2019 School. Groups will work together on research projects, led by the senior researchers.
The second week of this visit is the ACT2019 Conference, where the wider applied category theory community will arrive to share new ideas and results. It is not part of the school, but there is a great deal of overlap and participation is very much encouraged. The school should prepare students to be able to follow the conference presentations to a reasonable degree.
How to apply
To apply please send the following to act2019school@gmail.com
- Your CV
- A document with:
- An explanation of any relevant background you have in category theory or any of the specific projects areas
- The date you completed or expect to complete your Ph.D. and a one-sentence summary of its subject matter.
- Order of project preference
- To what extent can you commit to coming to Oxford (availability of funding is uncertain at this time)
- A brief statement (~300 words) on why you are interested in the ACT2019 School. Some prompts:
- how can this school contribute to your research goals
- how can this school help in your career?
Also, have sent on your behalf to act2019school@gmail.com a brief letter of recommendation confirming any of the following:
- your background
- ACT2019 School’s relevance to your research/career
- your research experience
Questions?
For more information, contact either
- Daniel Cicala. cicala (at) math (dot) ucr (dot) edu
- Jules Hedges. julian (dot) hedges (at) cs (dot) ox (dot) ac (dot) uk
Flies
It was a hot evening and, as is usual at that time of the year, there were quite a few flies buzzing around us. Understandably, I was annoyed, as they were interfering with my meditation.
“Master,” I said, “You keep telling me that everything in this world has a purpose, but I can’t figure out the purpose of these flies. All they do is break my concentration. Can we move indoors already, behind the screens, so that we can continue the lessons in peace?”
The Master looked at me the way he usually does when I say something that shows my lack of understanding — which unfortunately happens a lot.
“The flies are here to teach us about meditation,” he said.
“How so?” I said. “Are you trying to tell me that I should be able to quiet my mind even when there’s constant interference?”
“That would be the ultimate goal,” said the Master, “but for now I’d like you to observe the way these flies move. Can you do that?”
“Of course, Master,” I said and started watching the flies criss-crossing the air in front of me.
“What do you see?” asked the Master after a while.
“I see them zig-zagging constantly. They never seem to fly in a straight line for longer than a fraction of a second.”
“You are very astute, my Disciple,” said the Master. “Now, why would you say they’re doing that?”
“I think they are doing that to avoid being caught” I said. “Those flies that were, long ago, flying in straight lines were eliminated by predators, and only those that employed more elaborate movement schemes survived long enough to produce offspring. Evolution in action!” I said not without some pride at my cleverness.
“Quite so, my Disciple,” said the Master, “quite so…”
“But suppose,” he continued, “that, in some other universe, there is a colony of flies that live confined within the boundaries a hostile environment. Their life is short and full of suffering. But there is a benevolent being that can set individual flies free, to live a happy and productive life. The trouble is that she has to catch them first. And, in the beginning, it was easy, since they were all flying in straight lines. Almost all. The benevolent being was able to remove the straight-flying flies and make them happy. But there remained a few flies that, for one reason or another, kept zig-zagging. They survived long enough to produce offspring, some of which also kept zig-zagging. Soon enough, all flies in that hostile and unhappy environment developed this new survival strategy that prevented them from escaping their horrible fate. That’s evolution in action, too.”
“That’s a pretty sad story,” I said. “It shows that evolution is a cruel mistress. It doesn’t care if we are happy or not, as long as we produce offspring.”
“But what does it have to do with meditation?” I said, a little confused.
“The flies are our thoughts,” said the Master.
The Pipe
It was a pleasant evening and I was enjoying the warm breeze coming from the mountains bringing with it the smell of pine and something else.
“Why are you smoking a pipe, Master? It’s bad for your health.”
“This is not a pipe,” said the Master.
“This is most definitely a pipe. You must have bought it in a pipe shop,” I said.
“This is not a pipe,” said the Master.
I thought for a moment.
“Oh, I see. You are making reference to the famous painting by Rene Magritte, right? Ceci n’est pas une pipe! But what Magritte meant was that it wasn’t a pipe–it was a picture of a pipe. He played on our confusion between the object itself and its representation. But here you are holding an actual pipe.”
“What makes you think it’s a pipe?” asked the Master.
“Well, I can look up the definition of a pipe and you’ll see that it describes the object you are holding. Do you want me to do that?” I asked.
“Please do,” said the Master.
I pulled out my tablet and started tapping.
“What’s the wi-fi password for today, Master?” I asked.
“That which cannot be named,” said the Master.
“Oh, I know that one,” I said and continued tapping. I stopped after a few tries and looked up.
“I tried Tao and Dao, upper- and lowercase, but it didn’t work. Is it ‘the Tao,’ with ‘the’?”
“You are much too clever, my Disciple,” said the Master.
“Oh, you mean it’s literally ‘that which cannot be named’?” I started tapping again.
“Okay, here it is. According to the OED, a pipe is…” I hesitated for a moment.
“Wait, you don’t really want me to read the definition,” I said.
“No,” said the Master.
After a moment of silence, I said:
“You have corrected me, Master, because by naming the pipe I focused on just one small aspect of it. Its relationship to other pipes. By doing that I ignored its relationship to you, to me, to our conversation, to this lovely sunset, to Magritte and–now I get it–to the Tao.”
“But, Master, I’m confused,” I said after a while. “When you say that ‘The Tao that can be named is not the eternal Tao,’ you are giving it a name, aren’t you? You are calling it the Tao.”
“This is not a name,” said the Master.
“I have the feeling that if I say that this is indeed a name, I would be hitting a dead end,” I said.
We sat there for a moment while I was organizing my thoughts. Then it occurred to me.
“By calling it the Tao, you are not separating it from everything else, because the Tao is in everything. Neither are you ignoring its relationship to yourself or to me, because you are the Tao and I am the Tao. And the lovely sunset, and the pipe, and Magritte, it’s all the eternal Tao.
“This is not the Tao,” said the Master.
Fallout
“I watched a movie last night,” I said. “And it made me think.”
“Movies often make us think,” said the Master. “Good movies, like life itself, ask a lot of questions, but rarely provide answers.”
“Well, that’s the thing, Master” I said. “Maybe you know the answer to this question, or maybe you can steer me towards the answer. I’m sure this problem has been analyzed before by many people much wiser than yours truly.
“It’s a problem of moral nature. In the movie, agent Hunt faces a dilemma. His friend is in immediate mortal danger. Hunt can save him, but at the risk of endangering the lives of thousands of innocent people. He makes a choice, saves the friend but, in the process, the terrorists get hold of plutonium, which they use to make nuclear bombs. Of course, in the movie, he’s ultimately able to avert the disaster, disabling the bombs literally one second before they’re about to go off.
“Sorry if I spoiled the movie for you, Master.”
“Don’t worry, I’ve seen the movie,” said the Master.
“So what do you think, Master? Was agent Hunt acting recklessly, risking uncountable lives to save one?”
“And what’s your opinion?” asked the Master.
“I think the answer is clear. It’s just simple math: one life against thousands. I would probably feel guilty for the rest of my life for sacrificing a friend, but what right do I have to risk thousands of innocent lives?”
“You say it’s simple math,” said the Master. “I presume there is an equation that calculates the moral value of an act, based on the number of lives saved or lost.”
“It’s not an exact science, but I guess one could make some rough estimates,” I said. “I’ve read some articles that mostly deal with pulling levers to divert trolleys. So this seems like one of these problems, where your friend is tied up on one track, and thousands of people on another. A runaway trolley is going to kill your friend, and you pull the switch to divert it to the other track, possibly killing thousands of people.”
“If this is simple math, then why do you say you’d feel guilty? Shouldn’t you feel satisfied, like when you solve a difficult equation?”
“I don’t know. I think I would always speculate: What if? What if I saved my friend and, just like in the movie, were able to avert the disaster? I’d never know.”
“And what if you saved your friend’s life and the bomb exploded?” asked the Master.
“I guess I’d feel terrible for the rest of my life. And I would probably be the most despised person on Earth.”
“And what if that explosion prevented an even bigger disaster in the future?” asked the Master.
“And what if that bigger disaster prevented an even bigger disaster?” I asked. “Where does this end? Are you saying that, since we cannot predict the results of our actions on a global scale, then there is no moral imperative?”
“Would that satisfy you?” asked the Master.
“No, it wouldn’t!”
“Would you like to have a small set of simple rules to guide all moral decisions in your life?” asked the Master.
“When you put it this way, I’m not sure. I think there’s been many attempts at rule-based ethics, and they all have exhibited some pretty disastrous failure modes. It vaguely reminds me of the Goedel’s incompleteness theorem. No matter what moral axioms you choose, there will be a situation in which they fail.
“On the other hand, rejecting the axioms may lead to an even bigger tragedy, like in the case of Raskolnikov.”
“Do you see similarities between Raskolnikov and agent Hunt?” asked the Master.
“They both reject the ‘Thou shalt not kill’ commandment. They both feel intense loyalty to their friends and family. But Raskolnikov had a lot of time to think about his choices, he even published an article about it; whereas Hunt acted impulsively, following his gut feelings. One was rational, the other irrational.”
“But you said that Raskolnikov had no axioms,” said the Master. “So how could he rationally justify his actions?”
“I see your point,” I said. “He was trying to do the math. Solve the ethical equation. His hubris was not in rejecting the accepted axioms, but in believing that he can come up with a better set. So, in a way, agent Hunt had the advantage of being a moral simpleton.”
“He was the uncarved wood,” said the Master.
Bartosz Milewski's Programming Cafe 