Research on graph algorithms
In 2016, I did a master’s internship with Christoph Dürr and Nguyễn Kim Thắng. We tried to design an approximation algorithm for the online node-weighted Steiner forest problem. Our approach didn’t work, but we improved our understanding of the difficulty of the problem.
- Slides of the defense
- Internship report / master’s thesis: under revision, available at some point in the future
During this internship, I also started investigating (independently of my advisors) a connection between edge-colored graphs and linear logic proof nets. The slides above outline some of my first rough ideas on this topic, including questions on sub-polynomial complexity classes. A more mature preprint on this topic will be made available soon.
Programming contest stuff
My own stuff:
- The AI which won Prologin 2013.
- Solutions for the Google Code Jam 2014 and for TaupIC 2011.
- Submissions in Haskell for Google Paris Hash Code 2014 (with Robin Morisset and Jonathan Laurent). Here’s an explanation in French; see the result for yourselves :-D
- My username in the Google Code Jam is coproduit.
I designed algorithmic exercises for Prologin 2015 and 2016, see here.
These are the best algorithms lecture notes ever. A way more pleasant read than CLRS!
Here are some implementations of simple algorithms. (Not very interesting…)
What is the “essence” of the simplex algorithm, and how are its various variants (satisfiability of linear inequalities, effective Farkas Lemma, etc.) related?
Is there a simple combinatorial algorithm for (min-weight) perfect matching which doesn’t rely on blossoms? (It turns out that there is one for finding a unique perfect matching.)
How does duality in optimization (Lagrangian, conic, or linear…) relate to negation in logic / category-theoretic duality?