Misc. update + possible flamewar

Posting has been and will be sparse over the next month or so as I transition to my new location (starting a postdoc at Weizmann).

What I'm working on: a tantalizing decoupling conjecture and a concentration bound for adaptive Markov processes (with Anthony Brockwell). Ask me about these.

Thoughts on leaving Pittsburgh: it's a shame I only met some of the people so late. Seems like in my last months at CMU I made a whole slew of new friends and colleagues -- anywhere from fellow mountain bikers (and I've got fresh scars to prove that) to fellow mathematicians, philosophers, and shmoozers. Where have you guys been for the past 5 years? A better question is where have I been: stuck in my office. I'm not sure there's necessarily a moral here (if I'd done more shmoozing and less work I'd probably still be stuck in that office) -- but it's always sad to see what one has been missing out on.

And now for the flamewar: Cosma and I were discussing The Bell Curve over a beer (or two... or three...). Now smearing Herrnstein and Murray's book as pseudo-scientific racist drivel is a favorite past-time of the Left (and not having read it isn't much of a deterrent). Cosma points out that conservatives can also pile on. In 2005, Murray wrote a lengthy and copiously documented rebuttal (well, more like a synopsis of the debate that their book had been generating for 11 years). Two must-read books for all equality-across-all-groups ideologues are Steven Pinker's The Blank Slate and Nicholas Wade's Before the Dawn.

There is no doubt that free scientific inquiry is severely curtailed on certain topics. Just try getting a grant to do climate research if you dare question anthropogenic global warming. The Larry Summers affair illustrates that even "mild, speculative, off-the-record remarks about innate differences between men and women" can get a university president fired. Yet differences between ethnic groups and the sexes do exist as a matter of verifiable empirical fact (please take the time to read Pinker and Wade before calling me names).

Once again, I'm only too glad that the "controversy" generated by math is of the easily dismissed crackpot type, not the type that costs one his career.

Serious attempts at P?=NP ?

Here's a question I'm hoping my readers will help out with. It seems that every week someone comes out with a "proof" that P=NP, and only slightly less frequently that P!=NP. Most of these are written by amateurs who don't even understand the problem.

Have there been any attemps by reputable mathematicians to resolve the issue? Lindenmann had produced several flawed proofs of Fermat's last theorem a century before Wiles got it right, and he was certainly no amateur. Does anyone know of any credible proof attempts, with subtle, nontrivial mistakes?

Student projects

The semester is over, the grades should be in by now, and most of my students from FLAC are graduating. One of the components of the course was a research project, during which the instructors mentor the students on an individual basis. This has been quite a rewarding experience, since I managed to get four of my students interested in some deep and fascinating problems in automata theory, with connections to my own work. I note that all the students I mentored did a fine job and a couple of them taught me new things. But in this post, I'd like to showcase the projects with the strongest connection to automata theory and machine learning.

Jeremiah Blocki is that brave soul who took on the notorious problem #3. First, here is that long-overdue writeup where I define the universal regular kernel. In his paper, Jeremiah gives closed-form expressions for K_n(x,y) for short x and y, as well as proving some simple lower bounds on the complexity of K_n.

Vinay Chaudhary became interested in my work with Corinna Cortes and Mehryar Mohri on learning piecewise testable languages with the subsequence kernel. Aside from understanding our somewhat involved word-algebraic proof of linear separability, Vinay had to learn a whole bunch of subtle machine-learning notions, essentially on his own. Having gained a command of margins, support vectors, embeddings and kernels, he embarked on an investigation of the empirical margin of piecewise testable languages. Vinay produced a excellent piece of research, with some tantalizing leads.

Matthew Danish considered a problem that I'd attempted many moons ago and put aside -- namely, one of characterizing the languages that one obtains by taking finite Boolean combinations of modular n-grams. (A modular n-gram is the set of all strings in which a given contiguous substring occurs k mod n times.) Matt also had to master abstruse concepts such as syntactic monoids and morphisms, and produced a solid paper.

Jonah Sherman decided to aim high and attempt the star-height problem. I remember how mesmerised I was by this problem when I first encountered it some four years ago. When Jonah had asked me about its importance, I replied that if we can't answer such natural questions about regular languages then we are in dire need of better tools! That was good enough for him, and he dove into some rather dense semigroup theory, even rediscovering the rather nontrivial result that all languages recognized by finite commutative monoids have star height of at most one. Impressive work done by a college junior, check it out!

Joined the club

This morning I defended my thesis and have been promoted from mere Leo to Dr. Leo, thus upgrading this blog to the status being run exclusively by PhD's. The quality of the posts should improve accordingly -- stay tuned!

Riesz norms

Let be a vector space endowed with a norm . A norm is called absolute if for all , where is applied componentwise and monotone if whenever componentwise.

Norms having these properties are also called Riesz norms; the two conditions are equivalent for finite-dimensional spaces (see Horn and Johnson).

What about infinite-dimensional spaces? Does anyone have an example of a normed where the norm is satisfies one of the conditions but not the other? What about a function space?

For I think I have a proof that the two conditions are equivalent (by a handwavy appeal to Lebesgue's Dominated Convergence theorem). For function spaces, I suspect there's a counterexample. But this is all random 4am musing -- so please catch me if I'm disseminating lies!

Total variation revisited

This is a follow-up on my earlier post on the total variation distance. As I already mentioned, my visit to Stanford and Berkeley were immensely useful, not least because of an opportunity to meet with the experts in a field to which I aspire to contribute. In that earlier post on total variation, I gave some characterizations and properties of TV, fully aware of the low likelihood that these are original observations. Sure enough, the relation

has been known for quite some time; see the book-in-progress by Aldous and Fill, or the one by Pollard.

The relation

also seems to be folklore knowledge; I have not seen a proof anywhere and give a simple (non-probabilistic) one here (Lemma 2.6). Amir Dembo suggested that I re-derive this in a probability-theoretic way, via coupling. Here it is.

Recall that if and are probability measures on then
,
where the infimum is taken over all the distributions on , having marginals and , resp., and the random variables are and are distributed and . Any such joint measure on is called a coupling and one achieving the infimum is called a maximal coupling.

Applying this to our situation, let us define the random variables . Let be a maximal coupling of and , and define similarly for and . Notice that is a (not necessarily maximal) coupling of and . Then

.