What I’m Reading: Quick Takes on Three Algorithms

Here are three diverse items from the world of algorithms within the last month that I found interesting.

The first is the Objective Revision Evaluation Service (ORES) from Wikimedia Foundation, a machine-learning based web service that acts as an “algorithmic editing assistant” to classify edits into “good”, “needs review”, and “damaging” categories – an interesting application of machine learning to a social platform.  Interestingly (but perhaps not surprisingly), the accuracies of the various classifiers are very language-dependent.

The second is an article on Uber’s (and Lyft’s) “algorithmic management” technologies, which contains pointers to a couple of interesting research papers on the subject that are also worth reading.  It is a fascinating snapshot of the new digital economy, where algorithms have economic, sociological, and policy implications.

Finally, from the world of theoretical computer science, the big news is Prof. László Babai’s claim of a quasipolynomial time algorithm for graph isomorphism.  The result, as he says himself in his seminar talk, is strictly of theoretical interest.  But – if proved correct – it would enhance our understanding of computational complexity significantly.  Graph isomorphism is a tantalizing problem: known to be in NP; not known to be NP-complete; and despite a strong belief that it is P, there is no proof of it yet.  Hence all the excitement!  Keep in mind that the work still has to be peer-reviewed, so it may be some time before the dust settles.  And no, this algorithm does not show that P = NP.