Triangulation, Everywhere!

Before my MSc in Theoretical Computer Science, I took another one in Mathematics in Paris 6 and Paris 7 University. I knew I'd need more maths for the PhD subject we were thinking of. 

My dissertation for this maths master is here, and I'll build up on it now.

This dissertation is about a paper of my then supervisor, Paul-André Melliès, in which he extends an important concept in theoretical computer science -- finitary monads. Monads are used to model what we call effects, some subtle behaviours of programming languages that require good care to analyse and verify.

As for finitary monads: these are monads whose value on all objects can be computed from their values on finite objects.

In the paper I studied for this MSc dissertation, Paul-André had accomodated concepts in category theory (but coming from ideas of algebraic topology) to capture a more general notion of monads. It's all about identifying which objects will generate all the results.

In algebraic topology (well, rather in what me may call the "historic branch" now), the study of the space is based on a preliminary representation of it as a simplicial complex. In other words, you see where you could fit points, lines, triangles, pyramids...

Up to some deformation, and under some conditions, a space can be reconstructed from an associated simplicial complex.

But this means that all you need is: the generic idea of point, line, triangle, pyramid... and then you make copies, and glue them together appropriately. A bit of deformation if needed, and here's your space!

Homology studies simplicial complexes, to find out what can be said about a space from them. It's very often (at least in jokes) about finding holes in a space -- I also remember an interesting MPRI course in 2011 or so, by Eric Colin de Verdiere, on similar approaches but via graph embeddings.

Divide and Conquer. I recently was in a work meeting in which we had various expositions of the notion of divide and conquer. For some reason, I realised that a similar mechanism is here at play: build a value, from what you have for all values that are strictly lesser than it in some ordered structure.

So I'd consider the following: the divide and conquer approach works when you can glue together values for subproblems, to solve your original problem.

But if you see that via this algebraic and topological eye, couldn't there be here an adaptation of the notion of homology?

Homology, adapted, could allow us to:

1. Estimate how much a given problem resists to divide and conquer approaches,

2. And perhaps characterise in a second step the subdivisions that lead to obstructions to this approach.

In general, I'd suggest thinking more often about this. Can my result be obtained from solutions for smaller inputs? If not, where does it fail? Is it often? Can I combine divide and conquer where it works, with some more computationally expensive approach where it does not?