I have a new paper on arxiv today, Recognizing Partial Cubes in Quadratic Time. The previous time bound (for an \( n \)-vertex \( m \)-edge graph) was \( O(mn) \); this paper improves it to \( O(n^2) \) via a combination of bit-parallelism and a fast all-pairs shortest path algorithm I'd previously written about.

Although the new paper is written mostly in the terminology of graph theory, in order to make sense of the shortest path part I needed to import some terminology from media theory, a way of looking at structures equivalent to partial cubes in terms more closely related to finite state machines. Media theory was initially developed by my UCI colleague in social science, Jean-Claude Falmagne, for applications including modeling voter preferences and states of knowledge of human learners; I've been working with Falmagne and Sergei Ovchinnikov on a monograph describing this theory. I have to view this new result as a success for the media theoretic viewpoint, as I think that viewpoint was crucial in coming up with the shortest path component of the algorithm.

(The previous paper, "Algorithms for media", has a mildly convoluted history, by the way: after failing to interest my fellow algorithms researchers in its results, I presented it at a mathematical social sciences conference, the International Conference on Ordinal and Symbolic Data Analysis (OSDA), held at UCI in 2003, but that conference didn't have a proceedings; instead, there was a special issue of a journal devoted to the papers from the conference, to which it was submitted and duly accepted. But then the journal's editor died, and the complications from the resulting backlog have led to a situation where it may be another two years before the special issue actually appears...)