I am pleased to announce that the following paper is accepted as a brief announcement at SPAA 2010: Brief announcement: Lower bounds on communication for sparse Cholesky factorization of a model problem. Laura Grigori, Pierre-Yves David, James Demmel and Sylvain Peyronnet. In the paper we derive bounds on communication for sparse Cholesky factorization $latex A = LL^T$ . We focus our analysis on matrices whose graphs satisfy a property, from which a lower bound on the number of flops of the Cholesky factorization can be derived. More information? read the paper!

Je suis très content d’annoncer aujourd’hui que deux articles ont été acceptés récemment. Je suis d’autant plus content qu’il s’agit dans les deux cas de travaux effectués en grande partie par des étudiants en thèse au sein de notre équipe. par ailleurs, l’article sur SpotRank annonce l’arrivée dans la « grande famille » des auteurs d’articles scientifiques de mon frère Guillaume, donc encore une bonne nouvelle. Bref,voici les titres et abstracts : SpotRank: A robust voting system for social news websites. Thomas Largillier, Guillaume Peyronnet and Sylvain Peyronnet. WICOW 2010. abstract: We address the problem of designing a robust voting system for […]

On le sait tous, les algorithmes de classement basés sur l’utilisation d’un rang induit par une popularité « linkificatrice » sont biaisés d’avance à cause des méchants spammeurs qui obtiennent des liens de manière plus ou moins morale depuis des pages plus ou moins pertinentes. Bien sûr de nombreuses méthodes ont été mis au point dans le but de déclasser l’effet des « mauvais » liens : TrustRank, AntiTrustRank, Topical pagerank, Weighted Pagerank etc… Mais la question qu’on peut globalement se poser est la suivante : peut-on repérer quels sont les liens crédibles ? On peut également se demander si […]

Today I am writing a very small post to encourage you (my beloved readers) to directly go to Richard Lipton’s blog to read this very good post The 3 percent solution. Richard Lipton (professor of Computer Science at Georgia Tech) is talking about a question that arises in its mind about the role of theory w.r.t. real world problems. Indeed, using again and again $latex \cal O$ notation to assess the interest of our work, don’t we loose something? I often tell to my students that the choice of a sorting algorithm in practice does not only depend on the […]

Together with Alexandre Borghi and Jérome Darbon, we wrote a paper entitled Exact Optimization for the $latex l^1$-Compressive Sensing problem using a Modified Dantzig-Wolfe method. the paper is available as a UCLA CAM Report here: cam09-101.pdf Here is the abstract: This paper considers the $latex l^1$-Compressive Sensing problem and presents an efficient algorithm that computes an exact solution. The idea consists in reformulating the problem such that it yields a modified Dantzig-Wolfe decomposition that allows to efficiently apply all standard simplex pivoting rules. Experimental results show the superiority of our approach compared to standard linear programming methods. Comments are more […]

To find the beginning of the triangular adventure, you should read this post. To prove the lemma we use the following theorem that I am not proving in this post (if you want the proof, just let me know). Theorem Consider $latex N$ urns each filled with $latex m$ balls, and the following process: pick a ball in an urn chosen uniformly at random until the chosen urn is empty. The probability that one had to pick more than $latex O(N^{\frac{m-1}{m}})$ balls tends to a nonzero constant as $latex N$ goes to infinity. Proof (of the lemma) To each triangle […]

A few years ago, I worked together with Yves Verhoeven on the problem of testing triangular properties. We did some proofs, wrote a few pages but decided not to publish our work (since it is far from being optimal, and also far from being really interesting). However I think that this is worth a few lines in this blog. It is clearly more technical than the average post of my blog, so don’t force yourself into reading it. Let $latex K_n=(V,E)$ be the complete graph on $latex n$ vertices and $latex S$ be a set. Let $latex \phi:V\times V\rightarrow S$ […]

A friend recently asked me to explain her the concept behind MapReduce. The last time we saw each other, I had no time to do that, so I now use my  blog for this purpose. Map and reduce are particular functions that can be found we in numerous functional languages (such as python, ocaml, etc.). Map is a function that takes as input an other function, let’s say $latex f$ and a data structure (most of the time a sequence), that calls the function $latex f$ on each of the structure’s items and returns a list of the return values. […]

This is the last of the three posts about recommendation systems, the first can be found here, the second here. In order to validate the effectiveness of our approach we decided to make an experiment with actual products and users. For this purpose we collected from a french medias reviews website krinein a sample of 4400 movies.  From these 4400 movies, we selected uniformly at random 160 of them. This was the data set for our experiment. We then extract uniformly at random from this data set 9 movies. These 9 movies were our witness products set. Our methodology was […]

This is the second post about recommendation systems, the first one can be found here. It is pretty obvious that the goal of a recommendation system is to provide users with « good » products. I am going to first introduce our notations and then explain what is a good recommendation in our framework. In the work done with Sebastien hemon and Thomas Largillier, we consider that users belong to a set $latex \mathcal{U} = \{ u_{1} \cdots u_{m} \}$ of $latex m$ distinct users and that products come from $latex \mathcal{P} =\{ p_{1} \cdots p_{n} \}$, a set of $latex n$ […]