lidsblog

Large-Scale and Decentralized

Germans seem to like engineering-related TV commercials.  For example, when I was at École Centrale in 2006, Christian Wachinger, a German student who was also visiting, was quite amused by this Volkswagen commercial that "unpimp[ed] ze auto."  Also, there is an IBM commercial that has been airing recently in the US featuring buzzword bingo.  It seems that this commercial has been out in Germany for a few months and become popular; the German version can be seen here. 

The ivory tower is not an impenetrable defense from buzzwords.  My officemate Pat was recently quipping that one of us should propose to work on small-scale centralized algorithms, the thing to do now being large-scale, decentralized or distributed algorithms. 

Large-scale distributed algorithms are often defined on or described via graphs. 

Some of the students in SSG, nicknamed graphniks by Alan, spend some of their time looking at inference in large-scale graphical models via efficient message-passing algorithms.  Inference is the problem of estimating unobserved nodes X from observed nodes Y in a graphical model by computing marginal conditional densities (X_i|Y), or statistics of those marginal conditional densities such as mean and variance.  Belief propagation, an algorithm for inference is inherently distributed as the procedure involves passing messages -- functions computed locally at nodes, details of which are not described here -- along edges of the graphical model in an iterative fashion.

Part of Devavrat Shah's research agenda is also message-passing algorithms, in particular to solve problems such as matching, independent set, and scheduling.  Message-passing algorithms are used in the decoding of low-density parity-check codes, which were developed by Bob Gallager. 

On Tuesday, Lieven Vandenberghe gave a talk entitled, "Chordal sparsity in normal graphical models and semidefinite programming" at the LIDS colloquium.  He described interior point matrix optimization methods that make use of the junction tree, where the matrix in question is an adjacency matrix of a graph.  On Thursday, Éva Tardos gave a talk on games in networks during a CSAIL colloquium.  She first discussed congestion games in which agents do not cooperate and make their own choices in a decentralized manner.  Then she discussed buying and selling games on trade networks in which there is a little bit of cooperation or collusion.  One of her main points was that algorithmic game theory needs to start dealing more with cooperation.  Oh snap! German engineering in da house, ya!  What?  Oh.  Belgian and Hungarian engineering in da house, ya!

Price is Right

Many would argue that probability theory as we conceive of it today began through the work of the French mathematicians Fermat and Pascal, who came to the problem at the request of Chevalier de Mere, a nobleman with, as noblemen are wont to have, a penchant for dice.

The intimate relationship between gaming and applied mathematics continues to this day.  An algorithm that solves Sudoku also solves problems in X-ray diffraction microscopy.  Monte Carlo methods are all over the place, for example in learning, as an alternative to gradient descent optimization, and for performance evaluation. 

I don't know about others, but for me, one good thing about Rosh Hashanah, Columbus Day, snow days, and the like was the opportunity to watch The Price is Right.  Of the innumerable pricing games, several can be analyzed in terms of probability theory, game theory, etc.  Did waking up late and coming on down to watch The Price is Right play a role in my ending up at LIDS?  I don't know.  Did it influence the naming of an algorithm in my master's thesis after Plinko?  Yes.

So why bring up The Price is Right now?  It has been written that, "Unless you've been living under a rock, you know that Bob Barker's final turn as host of 'The Price Is Right' will air Friday, June 15."  This Friday will mark the end of an era just as last Friday's graduation and LIDS commencement reception marked the end of an era. 

At the reception, Vincent, in addition to honoring the graduates, instructed them to donate 10% of their income above $100,000 and 50% above $1,000,000 to LIDS.  If the cadre of LIDS members attending ISIT has perfected applied Monte Carlo methods, Vincent should be in store for a large donation later this month.