What Happens in Berkeley Stays in Berkeley

In a few hours, I'll have my flight to Oakland and then head over to Berkeley to spend most of September in residence at the institution formerly known as MSRI as part of the semester on Algorithms, Fairness, and Equity!

During this period, I'll spend a couple of days at ICERM for a workshop on mathematical neuroscience. I'll return close to the end of September for the start of our new school year (and will spend my first full day back figuring out what I'll do for the next day's lecture in my graduate-level mathematical-modeling course).

The `PrickRank' Algorithm

One way to gather information is to purposely write an incorrect 'factual' statement on social media.

People love to correct others (often obnoxiously, but at least one acquires info).

Google has PageRank, and social-media platforms like Twitter have this `PrickRank algorithm'.

(This monicker is destined to become a classic, just like FIPO.)

New XKCD: "Differentiation and Integration"

Today's XKCD, about the algorithmic difference between symbolic differentiation and integration, is superb!

My favorite step of integration is "burn the evidence". ;)

Algorithms in the Form of IKEA Instructions

I think my life could not possibly have been complete without seeing algorithms presented in the form of IKEA instructions. I am highly amused. :)

This is brilliant: Common algorithms explained in the style of IKEA instructions. https://t.co/BIHCed5o0T pic.twitter.com/wTd1DMY2GR

— Thomas Roth (@StackSmashing) March 17, 2018

(Tip of the cap to Lior Pachter.)

Conway's Game of Life In Real Life (on an Ocellated Lizard)

Wow! This is amazing!

Here is the blurb on the Facebook post that goes with the Physics Today article (though I added the hyperlink): The ocellated lizard develops an intricate, ever-changing pattern of black and green spots when it matures. Now researchers have determined that the patterns on the animals' backs update according to a well-defined algorithm: Over a period of a month or so, a given scale will change color—from green to black or black to green—with a probability that depends on the colors of the scales around it. In essence, the reptile is the embodiment of a cellular automaton, a type of discretized model made popular by John Conway’s Game of Life and used to simulate the spread of wildfires, the firing of neurons, and other phenomena.

Physics Today's article is about a recent article in Nature called "A living mesoscopic cellular automaton made of skin scales".

Pokémon Go and the Traveling Salesperson Problem

I should have posted this article about Pokémon Go and the Traveling Salesperson Problem a couple of weeks ago when I first saw this blurb.

I thought about it again today when I posted the link as comments on posts by a couple of Facebook friends (who are both also former undergrad students of mine from Somerville College).

Tales from the ArXiv: ¡No Mas!

The algorithm proposed in this paper has the acronym "NoMas".

I am amused. Usually the "¡No Mas!" algorithm is what you apply when you're desperate. (The associated computational problem is NP-hard, of course.)

A Spectral Navigation Algorithm

Clearly, some users of London's transportation system are using a spectral algorithm for navigation.

(Tip of the cap to Sang Hoon Lee.)

"A Method Based on Total Variation for Network Modularity Optimization Using the MBO Scheme"

One of my papers just came out in final form. Here are the details.

Title: A Method Based on Total Variation for Network Modularity Optimization Using the MBO Scheme

Authors: Huiyi Hu, Thomas Laurent, Mason A. Porter, and Andrea L. Bertozzi

Abstract: The study of network structure is pervasive in sociology, biology, computer science, and many other disciplines. One of the most important areas of network science is the algorithmic detection of cohesive groups of nodes called "communities." One popular approach to finding communities is to maximize a quality function known as modularity to achieve some sort of optimal clustering of nodes. In this paper, we interpret the modularity function from a novel perspective: we reformulate modularity optimization as a minimization problem of an energy functional that consists of a total variation term and an l_2 balance term. By employing numerical techniques from image processing and l_1 compressive sensing --- such as convex splitting and the Merriman-Bence-Osher (MBO) scheme --- we develop a variational algorithm for the minimization problem. We present our computational results using both synthetic benchmark networks and real data.


The really cool thing about this paper is what it does for "technology translation". We reformulate the modularity quality function in a way that relates it to compressive-sensing-like problems. One can thereby adapt methods from the latter to use for modularity optimization. One of the best compliments that we have received about this paper thus far occurred right after posting it on the arXiv: Somebody from the image-processing community told us that our paper was written in a language such that he could finally understand what people were doing with graphs. Given the goals of the paper, that was exactly what I wanted to hear!

Tales from the ArXiv: Baby Names and Random Walks

Well, how about that: using things like PageRank and other random-walk algorithms to come up with baby names. It's crazy, but I kind of dig it. :) Also, I these somebody wants an Ig Nobel prize (in Peace?)...

You can try it for yourself at the Nameling website.

Achievement Unlocked: Break Expedia's Shortest-Path Algorithm

No, Expedia, if I try to go between Ithaca and Newark with stops first to Philadelphia and then to Boston, it is not ok to insist that I do Ithaca->Newark->other city->Philadelphia when I try to go directly from Ithaca to Philly.

Actually, there was additional shortest-path failing besides that (like insisting that particular direct flights that exist for some searches don't exist for others).

Expedia really needs to hire some graph theorists!

After several failed attempts and significant frustration, I basically went and bought the tickets I wanted with Orbitz instead.

Anyway, this is what I get for trying to arrange an SFO -> Clarkson -> Cornell -> Rutgers -> SFO trip, because all three of those colleges are in the middle of bloody nowhere, except with slightly different nowheres. (That said, I am very excited about this academic trip. I will visit collaborators at Clarkson, I will be starting at a collaboration at Rutgers, and I will be visiting Cornell for the first time since I left when I graduated and will be giving a talk in the colloquium for the program from which I graduated. Awesome!)

The Impending War Against Algorithms

Apparently, there is going to be a war against algorithms. Guess which side I'm on? :P

(Actually, the article makes some important points, and I could certainly provide some comments from my own experiences.)

Finally, with this blog entry, I have reached a milestone. This is blog entry number 2500. Man, I produce a lot of text...

(Tip of the cap to whoever controls Matlab's Facebook account.)

TWSS (That's what she said.)

Now there is a computer algorithm whose purpose is to analyze algorithmically whether '(That's what she said.)' (TWSS) would be funny if added to the end of a sentence. I shit you not.

Sometimes I love computational linguistics...

(Tip of the cap to Puck Rombach.)

LOLCAT Method

That's right. There is apparently a LOLCAT method, which is a particular implementation of the Gillespie Algorithm.

That is just wrong.

(Tip of the cap to Liam Pomponi.)

Can one patent a community detection method?

One can patent a community detection method? What?

Will somebody please explain this to me?

Update: The patent apparently belongs to Huberman and Wu (familiar names, and now I know what community detection method it's based on). You can find the details here. In the 6 years since the patent was filed and when it was rewarded (in January 2010), the method has become completely out of date. Still, WTF?