# Latest Posts

• ## Trees in JavaScript

Tags: fun

This is a fun project I started one day that I wanted to relax, and I started thanks to the coding train.

Daniel Shiffman is a fantstic energetic and sympathic programmer doing “creative coding” in JS. It is a real pleasure to follow it’s tutorial and they are always very inspiring.

So I started this tutorial :

Right now it looks like this and I may had a wind that would perturbe the calm and change the colors, one day. Try it!

• ## Jellyfish project

Tags: fun

I’m currently attending the MPRI (Master Parisien de Recherche en Informatique) and we are loving the course on Scientific visualization and computer Graphics.

This course is taught by Damien Rohmer and Julien Tierny and is graded on an article presentation and a project (and an exam because the MPRI require it), and I would advise anyone who has the opportunity to take this course !

For the project we could do anything we wanted as long as it involved notion seen in the course.

With my friend Rémi Dupré we decided to model a scene underwater with jellyfish. It was his idea but mainly because I love jellyfish…

He handled the structure of meshes the creation of the scene in povray and I took care of designing the shape of the jellyfish.

Here is the Github repository and few pictures of the evolution of the project.

• ## Cat gif gallery

Tags: fun

The link to the so called gif library. I’ve been a fan of cat gif for quite a while now…

Eventhough gif is one of the most inefficient format for small video, I just love seeing a cat do something stupid in a loop.

I did this with a small script a friend did photo2html, to have quickly a minimalist static gallery of picture. I modified it to accept gif format, to avoid recomputing all thumbs and finally to create a html to give a gif impression from a mp4 format (much lighter). Here is one example:

I’m sure he disaproves my usage of the tool, but I really like photo2html!

• ## A recap of 3 articles of FOCS 2018

I had the chance to volunteer at the FOCS 2018 conference and here are 3 articles that I specially enjoyed and I give a short summary of them here.

### Bloom Filters, Adaptivity, and the Dictionary Problem

The dictionary problem considers a big dictionary $S$ on which you want to be able to know if a word $x$ is in $S$. The entire dictionary, because of its size, is usually saved remotely and you want to avoid querying it as much as possible. By using an approximate membership query data structure (AMQ) you can answer pre-queries that always answer PRESENT if $x \in S$ but also has false positive.

This paper proposes to use Bloom filters to create an adaptive filter (the filters adapts to an $\epsilon$ probability of having a false-positive), this method gives very good guarantees on false positives without significant space cost. Their contributions are 2 main results:

• When no feedback can be obtain on positive queries, adaptivity is impossible.
• It is possible to maintain an adaptive AMQ for the same cost as a non adaptative AMQ.

You can find the final paper here.

### Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication

Determining matrix multiplication’s complexity is a fundamental problem in theoretical computer science. The naive algorithm is in $\mathcal{O}(n^3)$ and the famous Strassen algorithm runs in $\mathcal{O}(n^{2.8074})$. The problem is to find the minimum $\omega$ such that matrix multiplication (MM) can be solved in time $\mathcal{O}(n^{\omega})$, more specifically, to know whether $\omega=2$… The best bound on $\omega$ so far is close to $2.3$.

This paper first unites the two main approaches : Laser method of Strassen, and the Group theoretic approach of Cohn and Umans. This new technique, based on zeroing out some variable of the tensor, is called the \textbf{Solar method}. Then, they introduce two more general methods, one based on monomial degeneration, the Galactic method, and the other where any degeneration is allowed, the Universal method.

After introducing those 3 methods, the paper shows that to find a method where $\omega$ could potentially be equal to 2, you have to search for a Universal method because the Solar and Galactic method aren’t powerful enough to provide such a small lower bound.

You can find the final paper here.

### Beating the integrality ratio for s-t-tours in graphs

The Travelling Salesman Problem (TSP) is well known and the s-t path variant of the TSP (shortest tour from $s$ to $t$ that goes through all vertices) has one advantage, it has an well-known 1.5 approximation-ratio. In this paper by detailing special cases of ears configuration and having a details analysis of those cases they beat the approximation ratio 1.5, and get a 1.497 approximation ratio.

An example of a well-oriented ear-decomposition.

You can find the final paper here.