Absolutely Regular

VHEMT follow-up

2010-10-02T19:01:00.000-07:00

First, let me say that I hadn't expected an idle musing to prompt what's become the most active comment thread so far on an otherwise obscure and rarely updated blog. In defense of VHEMT, I'd like to point out that it's a fairly benign form of a rather sinister movement. As Exhibit 1, below I'll post in full the comments of Anonymous (due the the length, the really juicy parts were clipped from the comment text). Imprisonment, forced sterilization -- it's all in there, enjoy. For Exhibit 2, consider Pollute and Die clip released by the 1010 campaign. They seem to have crossed a line here -- "snarling, wicked, homicidal misanthropy" is a fair characterization of this stunt. The reaction was one of such unanimous disgust that these people were compelled to issue a (weak) retraction.

These people are too easily dismissed as inconsequential raving lunatics. Occasionally, we're rudely reminded that all this talk of mass-murder isn't mere talk.

------------------- Anonymous's comment -------------------

sorry, i posted it to another forum of similar title...anyway if you want something to knaw on give it a thorough read...

***The Global Non-transferable 0.5 limit plan***

The basis of the argument...

1) we are approximately 50% over global carrying capacity as a species.

2) one child can carry the biological records for two...where a second child assumes the burden of the necessary reduction in population be an involuntary forfeiture of the biological records of two other individuals...

3) under awareness of said earth system stress levels, and loss of specification, many may voluntarily forfeit the passing of their biology as a means of preserving species on the brink, and securing planetary health, while insuring the right of humans to breed, should they choose to, remain an accessible option....in order that this wish be respected, these voluntary forfeitures must not be allowed to become a birth credit to be assumed by any existing parent, maternal, paternal, or both, in the case of a second potential child.

In order that human rights be observed:

The following proposal sites the rights of children not yet created as per 1) that they may not be born into a world that cannot adequately support them, or if this world can arguably support them, that one may site a degraded world relative to that which the potential child’s forbears enjoyed would be the child’s inheritance…

The following proposal sites the right of humans to procreate as per 2), while imposing limits to protect the rights of others who may choose to employ this right…

The following proposal sites the right to chose not to reproduce, as per 3)

Proposed proceedings to safe guard these rights are as follows, and are to be applied equally on a global scale to all members of the human populous.

Initial Proceedings:

all male parents of existing children, that are not already fixed, would need to schedule an appointment to address the situation, or face issuance of a warrant for their arrest for obstruction of justice and associated fines....

all female parents of two or more existing children that are not fixed, would need to schedule an appointment to address the situation, or face issuance of a warrant for their arrest for obstruction of justice and associated fines....

all female parents of fewer than two existing children, should be informed that weather though abstinence, birth control, selection of a fixed male partner, or any other means, they may wish to avoid fines and procedures.

Protocol:

Post conception the suspected father would be incarcerated until such a

time that it can be determined beyond question that he indeed is the

father...If he is not the father; he is free to go... The woman

then would be incarcerated until such a time as she could provide sufficient information to bring the father of her child into custody. Upon determination, the father of the child would undergo vasectomy before being released...

Should the mother choose to terminate the pregnancy in the first trimester, the father would be released unaltered. If the mother does not choose to terminate the pregnancy within the first trimester, this becomes a default decision to carry the child to term under the fore mentioned proceedings.

In any cases of a potential child, by a parent of an existing child, paternal, maternal or both, the offender(s) would have the choice of aborting the child or being put to death. The former decision inclusive of fines: for a father potentially twice ,for assuming what should rightfully be the woman's choice, and for a mother potentially twice, as a means of securing finance for the tubal she would receive in post.

Should any geographical region reach a state of equilibrium within it’s boundaries, the populous will have the option of applying for revokeable immunity.

The Voluntary Human Extinction Movement

2010-09-13T14:07:00.000-07:00

Have you heard of The Voluntary Human Extinction Movement? Their basic premise is that we should save the earth by not having any more children. I'm still not 100% sure this isn't a joke, but if it is, it's definitely on the elaborate side. What with the website translated into 17 languages, plus films and comics -- it's hard not to come to the conclusion that, at the very least, these guys take themselves seriously.

And yet the lack of self-awareness is surreal, bordering on (and occasionally crossing into) the comical. Consider their Why Breed chart (scroll down). It starts with the premise that "the search for a rational, ethical reason for creating one more human today goes on without success" and proceeds to list the various pretexts people give for having children, expose the true motivation behind each one, and offer helpful alternatives -- all in a convenient three-column format.

Some of these are jaw-droppingly idiotic (pretext: "Pregnancy and childbirth are life experiences"; suggestion: "Rent pregnancy simulator". Huh? Is that a meta-joke?). Others are dutifully cribbed from the multikulti book (pretext: "Want a child with our bloodline"; true motivation: "Ego extension. Racial identity"; suggestion: "Recognize value of people with different genetic makeups").

But this one is telling: "God wants us to." One might naively assume that the VHEMTers are hard-core atheists, but a moment's reflection suggests that this can't be the case. Why would a true atheist give a rat's behind about the future of the earth, after his own death? Make no mistake, this is a religious cult. Unsurprisingly, the VHEMTer rebuttal to G-d's commandment is a direct call to convert: "Seek true nature of God, whatever you perceive God to be." They don't say this directly, but Wiccanism seems to capture their creed best: "Stop. Having. Babies."

I have no interest in dialogue with these people (I shouldn't even be taking the time to blog about them). But I am mighty curious to know how they'd respond to my silver-bullet argument:

There are two kinds of people in this world: those who will sign on to the VHEMT agenda and those who will not. Which group does the future belong to? What does this say about the effectiveness of the VHEMT agenda?

Smart spam?

2010-07-07T10:27:00.000-07:00

Occasionally I'll get comments that are clearly spam (since this blog is rarely updated, feel free to replace "occasionally" with "rarely"). Ordinarily, I delete them without a second thought. Two recent comments, however, gave me reason for pause.

I am talking about this and this. These comments are a bit of a mystery to me. First, note that they are not only syntactically but also semantically more or less well-formed. They are even vaguely relevant to the post's content! So a natural hypothesis might be that they were written by humans. But then why the obviously spammy aliae (aliases) --- "buy sildenafil citrate" and "generic viagra"?

Explanations welcome...

Ode to my students + moralizing

2010-01-13T02:49:00.000-08:00

First, two tales of hubris and folly. The recursion theorem was a big success with my students. We don't usually teach it in this course, but my students went through the standard material like pie and were hungry for more. Other than a ridiculously easy proof of the undecidability of the halting problem, the recursion theorem yields a slick proof that L_min is not in RE (good luck approaching that one without this tool). Riding a euphoric wave of success, I thought I'd improvise a proof that L_min is not in coRE. I thought I had a clever proof using the fixed-point theorem, but it turned out to be wrong. After spending a couple of days in search of a proof, I turned to mathoverflow (an amazing resource!) where Ryan Williams produced a correct proof.

Second, during the last lecture, a student asked if every undecidable language in RE is complete for RE under mapping reductions. I thought the answer should be true, and tried to prove this during the break. Needless to say, I failed to find a proof. After speaking with Menachem Kojman, I learned that in fact the answer is false; this follows froom the Friedberg-Muchnik theorem.

There are two morals to this story:
1. I was blessed with amazing students this semster.
2. Sometimes (if one is lucky!) innocent-sounding questions that come up in undergraduate lectures turn out to be deep, difficult research problems. By all means attempt to tackle them, but keep in mind this caveat.

Show that L_min is not in coRE

2010-01-09T14:59:00.000-08:00

So I taught the recursion theorem and showed (as in Sipser) that the language L_min, consting of all minimal Turing machine descriptions, is not recursively enumerable (RE). The argument goes like this: suppose to the contrary that L_min is in RE, with some enumerator E. Define the Turing machine B, which obtains its own description [B] via the recursion theorem, waits until E generates a program C that is longer than [B], and then simulates the behavior of C. The contradiction results from the assumption that E only generates minimal programs and the construction of B as a program that's shorter than some "minimal" program!

Now I want to show that L_min is not in coRE (meaning that its complement is not in RE). This has turned out to be quite a bit trickier, at least for me! I believe I have a proof, but I welcome solutions from the readers.

A cheating Quine?

2010-01-02T12:48:00.000-08:00

So I'm teaching a course on automata theory -- again. (A brief personal update: I've started a faculty position at BGU, got married and had a baby -- not in that order.)

I want to teach the recursion theorem this week. The theorem states that no matter what Turing machine one is designing, one can always assume that it has access to its own description.

To me, this always seemed painfully obvious. Once you accept that Turing machines and programs (in MATLAB, say -- to be concrete) are equivalent, the argument comes down to writing a program that can print its own code.

At first, writing a program that prints itself might seem impossible. After all, any sort of program that says PRINT X will be longer than the string X (because it contains X and the PRINT instruction) -- and so X can't be the program's whole description!

Indeed, such a simple strategy for a self-printing program is doomed to failure. However, who says the program must quote itself within itself verbatim? Maybe it can encode a description of itself in some compressed form, and execute a routine that decompresses and prints that description. Indeed, many such programs exist -- they are known as quines (after the great logician and philosopher Quine).

But it seems to me that these quines, while clever, are working too hard. Consider the following simple MATLAB function:

function quinecheat
fid = fopen('quinecheat.m','r');
str = char(fread(fid))';
% remove double line-skips:
str = strrep(str,[char(13) char(10)],char(10));
fclose(fid);
fprintf('%s\n',str);
return

If you save the code above as the MATLAB file 'quinecheat.m' and call quinecheat from the MATLAB command window, you will get a printout of the code.

On the one hand, you can do this in just about any programming language -- and any Turing machine T can assume it's being simulated on some universal Turing machine U and move U's tape head to the beginning of T's description. Also, I believe that this trivial "proof" of the recursion theorem retains the theorem's full power. For example, here is a simple proof that the halting problem is undecidable. Suppose to the contrary that some matlab function H inputs other matlab programs and outputs 1 if the input program halts (and 0 otherwise). Now consider the matlab function D which obtains its own description [D] and calls H([D]). If H([D])=1, D goes into an infinite loop; otherwise, D halts. We've reached our contradiction!

And yet I can't help but feel that I'm cheating somewhere. Is my program quinecheat a valid example of a self-printing program? Is the technique I am suggesting a valid alternative proof of the recursion theorem?

A silver bullet argument

2009-12-13T01:41:00.000-08:00

Whenever someone claims to have a "silver-bullet" argument on a controversial issue (such as climate change, abortion, etc), it should set off a red-light alert. A "silver-bullet" argument is something like a mathematical proof, only involving social issues. It's the kind of argument that any sane, rational person can agree with -- regardless of his values, preferences, etc. Presumably, having heard such an argument, any sane, rational person can't help but to agree with the conclusion.

So I just heard such an argument -- all 9.5 minutes of it. And I'm still not agreeing with the conclusion that drastic taxation and regulation is needed to stop global warming NOW. So... am I insane? Irrational? Or... could it be that the argument has holes?

Let's play a game. I don't care what your stance is on global warming science and policy. Just for fun, point out as many logical fallacies as you can in this vampire-slaying, inexorably compelling super-argument.

New paper up

2009-07-08T07:49:00.000-07:00

Check it out.

UPDATE:
Here's another one.

I suppose I should say a word or two to get you to click. Both involve automata and probability, but in rather different ways. I know the suspense must be killing you by now -- all the answers are only a click away!..

UPDATE II: That first paper has a mistake, discovered by Dana Angluin and Lev Reyzin. It has been pulled from submission. The mistake seems fixable and possibly already fixed. Developing...

UPDATE III: (Dec. 13, 2009) A new paper is up by Dana Angluin, David Eisenstat, Lev Reyzin and yours truly. Among other results, it shows that learning DFAs in the way I suggested (by sampling random ones and invoking AdaBoost) is impossible since one can embed parity in random DFAs.

A reverse Jensen inequality for exponentials

2009-06-01T12:43:00.000-07:00

Let x_1, ... x_n be real numbers and t_1, ... t_n be nonnegative numbers summing to 1.

A trivial consequence of Jensen's inequality is that

exp(t_1 x_1 + ... + t_n x_n) <= t_1 exp(x_1) + ... + t_n exp(x_n).

I claim that in the other direction, we have the following:

t_1 exp(x_1) + ... + t_n exp(x_n) <= exp( diam(x) + t_1 x_1 + ... + t_n x_n)

where diam(x) = max_i x_i - min_i x_i is the diameter of {x_1, ..., x_n}.

Any proof ideas? (Unlike my previous goof-ups, I can actually prove this one.)

concentration of exchangeable processes

2009-05-17T01:45:00.000-07:00

Having thoroughly embarrassed myself in the previous post, let me shoot for something half-way redeeming.

Let X_1, X_2, ... be a sequence of {0,1}-valued random variables. We say that the process {X_i} is exchangeable if every finite-dimensional joint distribution is invariant under the permutation of indices. The de Finetti theorem characterizes the exchangeable processes as mixtures (possibly uncountable) of Bernoulli processes. Note that this is only true for infinite sequences -- there are well-known examples of finite exchangeable sequences that cannot be extended even by 1 (see Diaconis for a fascinating discussion).

Now exchangeable processes are in general not concentrated. Indeed, the measure P on {0,1}^n with P(00...0)=P(11...1)=1/2 (i.e., a mixture of two degenerate Bernoulli processes) is exchangeable but not concentrated.

However, I claim the following:

1. if P is a mixture of Bernoulli processes whose biases are bounded within
0<=a<=b<=1, and f:{0,1}^n -> R is 1-Lipschitz w.r.t. the normalized Hamming metric,
we have
P(f - Ef > t) <= exp(-2n(t-d)^2) where t < d =b-a and the bias of a Bernoulli process is P(X=1). Note that this recovers the ordinary McDiarmid bound, for which b=a, trivially.

2. if P only assigns positive probability to sequences with at most k ones,
we have
P(f - Ef > t) <= exp(-2n(t/2k)^2) ) for any f:{0,1}^n -> R that is 1-Lipschitz w.r.t. the normalized Hamming metric.

The proofs are standard and apparently not worthy of writing up -- but let me know if you try it and get stuck. Have these appeared in literature?

Tighter Hamming ball volume?

2009-05-04T02:18:00.000-07:00

Let C(n,k) be the binomial coefficient "n choose k". We want to bound the sum of these, with k ranging from 0 to d. This is equivalent to bounding the volume of the n-dimensional Hamming ball of radius d. Denote this number by B(n,d).

A well-known bound (appearing, for example, in the Sauer-Shelah-VC lemma) is

B(n,d) <= (en/d)^d .

We are pretty sure that it can be sharpened, for example by writing a (1/2) in front of the RHS. (We actually think it can be sharpened by better than a constant.)

Thus has to be known. Anyone have a reference? Thanks in advance!

2 inequalities

2009-04-24T05:41:00.000-07:00

1.

Let mu and nu be two Bernoulli measures on {0,1}, with biases p and q, respectively. Thus,
mu({1})=p=1-mu({0})
nu({1})=q=1-nu({0})

Let P and Q be the n-fold products of mu and nu, respectively. Thus, P and Q are two probability measures on {0,1}^n.

Show that
||P-Q|| <= n|p-q|
where ||.|| is the total variation norm (and <= is a poor man's way of writing \leq in plain text).

2.

Now assume that q = 1/2; thus Q is the uniform measure on {0,1}^n.

Show that
||P-Q|| <= C n^(1/2) |p-1/2|

where C>0 is some fixed universal constant. (Hint: Pinsker's inequality might come in handy.)

Are these novel or already known?

Back by popular demand

2008-12-18T02:55:00.000-08:00

My anxious readership has been flooding me with emails, demanding to know if I'm still alive and why I quit blogging. (Just kidding. Is anyone still reading this thing?)

A good chunk of my time has been occupied by administrative activity (job search), as well as personal matters (both good and bad).

I regularly attend two courses: one by Gideon Schechtman and one by Itai Benjamini.

Here is a nice "paradox" from Gideon's first lecture. Consider the 2x2 square = [-1,1]^2. In each quadrant, inscribe a unit circle. Let S_2 be the largest circle about the origin not intersecting any of the inscribed unit circles. Let R_2 be its radius; compute R_2 (it's easy!).

Now repeat the same in n dimensions: divide [-1,1]^n into 2^n orthants, inscribe a unit ball in each one, and let R_n be the radius of the maximal ball about the origin that does not intersect any of the inscribed balls. It shouldn't take you more than 2 minutes to come up with a formula for R_n -- the basic 2-dimensional intuition carries over to higher dimensions.

However, to anyone not familiar with high-dimensional geometric phenomena, something very surprising should happen. I won't give it a away here, but feel free to discuss in the comments. This sort of "paradox" probably has a name -- anyone know what it is?

CS/politics -- dispelling the myth

2008-10-25T12:32:00.000-07:00

I know that the blog's subtitle is "A math/computer science research blog", and that I haven't had a research post in months. I also know that this is the last place you want to turn to for politics.

The point of this post isn't really to weigh in on the upcoming US election -- I have nothing original to say about politics (it's hard enough to find original things to say in math/cs). My goal here is to dispel a false impression you might have gotten if you peruse math/cs blogs. You might naturally come to the conclusion that every mathematician/computer scientist is left-leaning and favors Obama.

You'd be wrong, though. One brave soul -- namely, Lev at Yale -- is willing to go against the current and argue in favor of McCain. Read his piece here. You owe it to yourself to step out of the echo chamber and hear a refreshing dissenting voice.

My exchange with Derbyshire

2008-10-03T05:04:00.000-07:00

which he has kindly allowed me to post, is below. I'll address the comments in the previous post after Sabbath.

NRO diary
7 messages

Aryeh Kontorovich

Fri, Oct 3, 2008 at 1:54 AM

To: gxnmvw7e

Dear Mr. Derbyshire,

your recent NRO diary has prompted me to write a blog post:
http://absolutely-regular.blogspot.com/2008/10/non-apologia.html

I assure you this is not hate-mail from an offended Christian!

All the best,
-Aryeh

John Derbyshire <>

Fri, Oct 3, 2008 at 2:13 AM

To: Aryeh Kontorovich <>

Thank you, Aryeh. I really didn't get any of that, though.

>>there is absolutely no logical reason to prefer materialism over a belief in a higher power

But there is: it's called "Occam's Razor"

And why is there anything mysterious about humans caring for their
children? All the higher animals care for their children. It's called
n-a-t-u-r-e.

Best,

JD

[Quoted text hidden]

--
John Derbyshire
[Old website] http:\\www.olimu.com
[New website] http:\\www.johnderbyshire.com

Aryeh Kontorovich <>

Fri, Oct 3, 2008 at 2:26 AM

To: John Derbyshire <>

Thank you for the prompt reply! I think the readers would be rather interested to see your reply -- may I post it in the comments?

Re: Occam's Razor. This is perfectly fine and good for understanding and predicting natural phenomena (and indeed, is a perfectly natural hypothesis selection criterion in science, with some rigorous mathematical justification). For morality and ethics, the scientific method is woefully inadequate.

Re: n-a-t-u-r-e. Not so fast. Natural human instincts (such as for food and sex) are easily subverted by modern technology to serve pure hedonism (cf. junk food, contraception, pornography). Why doesn't every atheist spend his life on a womanizing drug binge?

Cheers,
-Aryeh

[Quoted text hidden]

John Derbyshire <>

Fri, Oct 3, 2008 at 2:34 AM

To: Aryeh Kontorovich

Sure. Use as you like. Just spell my name right.

On Thu, Oct 2, 2008 at 8:26 PM, Aryeh Kontorovich
wrote:
> Thank you for the prompt reply! I think the readers would be rather
> interested to see your reply -- may I post it in the comments?
>
> Re: Occam's Razor. This is perfectly fine and good for understanding and
> predicting natural phenomena (and indeed, is a perfectly natural hypothesis
> selection criterion in science, with some rigorous mathematical
> justification). For morality and ethics, the scientific method is woefully
> inadequate.

Sez who? Seems perfectly adequate to me.

>
> Re: n-a-t-u-r-e. Not so fast. Natural human instincts (such as for food and
> sex) are easily subverted by modern technology to serve pure hedonism (cf.
> junk food, contraception, pornography). Why doesn't every atheist spend his
> life on a womanizing drug binge?

It's an empirical fact that they don't. Perhaps they are just better
in touch with their nature than you believers.

The empirical fact is, in fact, even worse for your case than that.
The less religion, the more morality. Religious nations (India,
Nigeria, Mexico) have worse stats om crime, dysfunction, HIV, etc.
that irreligious ones (Norway, Japan, New Zealand). The most
religious subgroup of the US population is Af-Ams; the leasst
religious, E-Asian Americans. Guess which way the crime/HIV/etc.
stats go?

If it's morality you want, hang out with unbelievers!

JD

[Quoted text hidden]

Aryeh Kontorovich

Fri, Oct 3, 2008 at 2:48 AM

To: John Derbyshire <>

Sure. Use as you like. Just spell my name right.

did I misspell your name in the post or correspondence? My sincere apologies (though I haven't been able to locate an error after several cursory glances).

> Re: Occam's Razor. This is perfectly fine and good for understanding and
> predicting natural phenomena (and indeed, is a perfectly natural hypothesis
> selection criterion in science, with some rigorous mathematical
> justification). For morality and ethics, the scientific method is woefully
> inadequate.

Sez who? Seems perfectly adequate to me.

Well, the Nazis had used the scientific method to determine that a human ceases to live outside a certain temperature and pressure range. Scientifically, those were sound experiments. Science tells us what we can do. Morality tells us what we should do.

It's an empirical fact that they don't. Perhaps they are just better
in touch with their nature than you believers.

Actually, if you look at the demographics in America and Europe, you'll see that the believers make much better breeders than the non-believers. Say what you will about Muslims, but they certainly seem to be beating the rational, logical westerners at this game.

The empirical fact is, in fact, even worse for your case than that.
The less religion, the more morality. Religious nations (India,
Nigeria, Mexico) have worse stats om crime, dysfunction, HIV, etc.
that irreligious ones (Norway, Japan, New Zealand). The most
religious subgroup of the US population is Af-Ams; the leasst
religious, E-Asian Americans. Guess which way the crime/HIV/etc.
stats go?

If it's morality you want, hang out with unbelievers!

I certainly wasn't defending all religions as morally virtuous (I was merely defending religious faith from the conflation with superstition). As far as moral superiority, I am only prepared to defend Judaism.

-AK

John Derbyshire <>

Fri, Oct 3, 2008 at 1:08 PM

To: Aryeh Kontorovich <>

On Thu, Oct 2, 2008 at 8:48 PM, Aryeh Kontorovich
>> > Re: Occam's Razor. This is perfectly fine and good for understanding and
>> > predicting natural phenomena (and indeed, is a perfectly natural
>> > hypothesis
>> > selection criterion in science, with some rigorous mathematical
>> > justification). For morality and ethics, the scientific method is
>> > woefully
>> > inadequate.
>>
>> Sez who? Seems perfectly adequate to me.
>
>
> Well, the Nazis had used the scientific method to determine that a human
> ceases to live outside a certain temperature and pressure range.
> Scientifically, those were sound experiments. Science tells us what we can
> do. Morality tells us what we should do.

You lose a point there for being the first to say "Nazi". Don't you
know the damn rules?

>> It's an empirical fact that they don't. Perhaps they are just better
>> in touch with their nature than you believers.
>
> Actually, if you look at the demographics in America and Europe, you'll see
> that the believers make much better breeders than the non-believers. Say
> what you will about Muslims, but they certainly seem to be beating the
> rational, logical westerners at this game.

Yes. Religious belief contributes to fitness (in the technical
biological sense -- increases your genome's chances of passing on its
material).

And this proves ... what? That evolution is a haphazard business,
that sooner or later heads in a wrong direction. Which any biologist
could have told you. Biologist's joke: "To a first approximation, all
species are extinct." It's actually about 99.9 percent.

>
>> The empirical fact is, in fact, even worse for your case than that.
>> The less religion, the more morality. Religious nations (India,
>> Nigeria, Mexico) have worse stats om crime, dysfunction, HIV, etc.
>> that irreligious ones (Norway, Japan, New Zealand). The most
>> religious subgroup of the US population is Af-Ams; the leasst
>> religious, E-Asian Americans. Guess which way the crime/HIV/etc.
>> stats go?
>>
>> If it's morality you want, hang out with unbelievers!
>
>
> I certainly wasn't defending all religions as morally virtuous (I was merely
> defending religious faith from the conflation with superstition). As far as
> moral superiority, I am only prepared to defend Judaism.

That old thing? I'll give it another 3,000 yrs, then -- pfffft!

--

[Quoted text hidden]

Non-apologia

2008-10-02T16:34:00.000-07:00

One of my favorite commentators, John Derbyshire, is an unabashed atheist. Though his salvos are mostly aimed at his former faith of Christianity, I suspect that he is an equal-opportunity kafir. I admire Mr. Derbyshire for his razor-sharp wit and unwavering intellectual honesty, and so it is with great caution that I venture to point out a lapse in his reasoning. Namely, he seems to conflate religion with "rank superstition". (Again, technically the statement applies only to Christianity, but I doubt Mr. Derbyshire's judgement of, say, Jewish ritual observance would be any more flattering.)

As an observant Jew, I believe with perfect faith that the world was created by an infinitely wise and all-powerful Creator, who endowed men with souls and free will and who demands that we choose to behave in accordance with His laws, as revealed to us on Mount Sinai (the requirements are a great deal less exacting for non-Jews). But the point of this note is not to defend my beliefs or to try to gain converts. Rather, it is to attempt to understand the distinction between "superstition" and other -- "valid", "legitimate", "rational" -- beliefs. Merriam-Webster's definition of superstition is a good start: "a belief [...] resulting from ignorance [...] trust in magic or chance [...] a false conception of causation [...] a notion maintained despite evidence to the contrary". That certainly doesn't sound very attractive. So what's the antidote to superstition? Mr. Derbyshire doesn't really propose one, but if I might put words into his mouth for a moment, I would hazard positivism or materialism.

But of course, as any philosopher of epistemology will tell you, there is absolutely no logical reason to prefer materialism over a belief in a higher power. Recently, a very intelligent friend of mine (let's call him W) demanded a logical justification for my adherence to Judaism. I told him that every man must answer for himself the fundamental question along the lines of, "Is there meaning to life? Did a Creator create us for a purpose?"

In my experience, most atheists avoid a logically consistent and intellectually honest answer. Many of them go through life doing all the "right" things -- work, marriage, children -- yet if pressed, have a hard time justifying their actions. Childrearing is a major burden, which certainly cannot be justified on the basis of short-term pleasure. Yet I suspect many people have children out of some vague sense that they're "supposed to" -- without the conscious realization that they are fulfilling some greater purpose. Indeed, there are millions of atheists whose answer to the meaning-of-life question would be an emphatic NO. Yet examining the way many of these so-called atheists choose to live their lives, one can't help but wonder if they're actually scrupulously following some sacred text. How many of them have children? How many justify it solely based on Darwinian genetics?

I claim that such people are being less than intellectually honest. They have some vague sense of purpose in life, but are unwilling to admit that, as it would undermine their "atheist" credentials.

Who can blame them? A positive answer to the meaning-of-life question opens some intimidating doors. If we are created with a purpose, we must seek to discover this purpose and strive to fulfil it. That could entail hard work and major sacrifices!

"But isn't God just a story you're telling yourself for comfort?" my friend W asked. "No," I told him. "To me, this has the feel of compelling, undeniable reality."

How does any of know that we are not, in reality, just a brain in a vat? The short answer is that we have absolutely no way of knowing. One could just as well claim that positivist reality is a story we tell ourselves for comfort. And as long as we're choosing which stories to tell ourselves -- without any objective logical basis for any of them! -- we have to judge these stories by some other criterion than the scientific method. Indeed, there are lots of "stories" out there, and why I picked the "Judaism" one is a long story in itself. But let's dispense once and for all with the fallacious notion that religious belief is somehow illogical or irrational.

Learning paradox

2008-07-09T09:05:00.001-07:00

Consider the standard PAC learning model. We have a concept class C over an instance space X, as well as a probability distrubution P on X. After observing a labeled sample of size m, and finding an f in C consistent with this sample, we will know that with high probability the generalization error of f is bounded by something like

(*) sqrt(d / m) + confidence term,

where d is the VC-dimension of the concept class C [the confidence term isn't the interesting part here -- it appears in all generalization bounds of this type, and goes to zero as 1/sqrt(m)]. Intuitively, this bound says that if we managed to explain the observations by picking a model from a "simple" class, we can be confident that our predictions will be good. Explanations by more complex models are less informative. In the trivial case, C= 2^X and VC-dim(C)=|X|
-- so achieving zero sample error tells us nothing about generalization error.

However, one might reason as follows. Suppose I receive a labeled sample and find a classifier f in C that achieves zero sample error. Now what's stopping me from re-defining my concept class? I'll define a new concept class C' = {f} that contains a single concept -- f! Its VC-dimension is trivially zero. As far as my prediction is concerned, it doesn't matter whether I learned using C or C' -- in either case, I'll pick the classifier f. But the VC-dimension of C might be large, giving me a poor generalization guarantee (*), while VC-dim(C') = 0, which is as good as things can be!

What's wrong with this reasoning?

Cheating on tests

2008-02-04T13:25:00.000-08:00

Various youngsters share their favorite test-cheating techniques here. What struck me was the high overhead and low information content of their devices. All of their tricks have the capacity to hold a few words of text, or maybe a paragraph at best. Is this what exams in schools have become -- the rote regurgitation of a set number of words? Wouldn't it be easier to just memorize the darn words?

Computable numbers paradox

2007-12-30T20:57:00.000-08:00

Here's a delicious paradox, due to Sylvain Cappell. Consider the class of the computable real numbers -- i.e., those reals for which there is a Turing machine that is guaranteed to produce the nth decimal digit in finite time. This is a well-defined and countable subset of the reals; let's denote it by T.

Being countable, the elements of T may be enumerated and arranged in an array of digits where the (i,j)th entry is the jth digit in the expansion of the ith element of T. You can probably guess what's coming next -- we're going to apply Cantor diagonalization to this list and obtain a new real number r, not in T.

It seems we have a nasty paradox on our hands. On the one hand, Cantor diagonalization is a well-defined, constructive, algorithmic process -- so constructing r out of T should be a cinch. On the other hand, by assumption, T is an exhaustive list of all the computable numbers -- so r should not be computable. So which is it -- is r computable or not?

Discussion is welcome in the comments. I'll close by that I would've loved to use this question on my automata theory undergrads.

Update: I was being sloppy in attribution; please see comments.

I suppose I'm flattered

2007-11-22T15:09:00.000-08:00

that a professional philosopher would quote an entry from this blog and deem it worthy of rebuttal. I'm too busy/tired to read the piece, much less comment on it. A cursory scan, however, suggests that

1. I stand by my original claims
2. Stemhagen is kinder (i.e., less nasty) to me than I was to him

This blog has been kind of on hold for a while. I know I promised people research tips, but I'm stuck on a problem and feel myself unworthy of dispensing research advice. Especially with people like Tao in the blogosphere (he has plenty of high quality advice for mathematicians at all stages of their careers).

So... if anybody is itching to re-start that math-education-ethics-platonism discussion, now's your chance. I'll check back in a day or so.

Update: A co-blogger had a stronger stomach than me, and read enough to find the following nugget:
"Some argue that mathematics class ought to more explicitly consider those on the socio-economic margins and our social system's role in this marginalization."
I'm suddenly reminded why I was nasty to begin with.

Misc.rand.various.sundry

2007-11-07T06:13:00.000-08:00

This is cool.

This is not.

As for my last two papers (uploaded last night) -- you decide.

Research updates

2007-10-24T07:43:00.000-07:00

I seem to have resolved, affirmatively, an open question I'd posed in Sec. 6.5.3 of my thesis -- namely, whether for (just about) any mixing matrix there's a measure achieving those mixing coefficients. I haven't written up a proof yet, but looks like it'll make a cute little result. Here's a very short writeup (no proof); let me know if you want to hear more.

Got an interesting conjecture regarding mixing coefficients of random fields. I can see this one having far-reaching implications but unfortunately see no proof...

[Update: that random field mixing conjecture is wrong. Maximal graph degree is too crude a measure of connectivity -- seems like some sort of path counting is necessary...]

Bemused metablogging

2007-10-21T10:19:00.000-07:00

So Scott calls Al Gore "the Churchill of climate change" -- this despite the fact that the fact that Gore's science is so shoddy that a British High Court ruled that his film can't be shown to schoolchildren. I would love for this to be a bad case of a malfunctioning irony meter (mine), but I fear the worst. (Was Churchill also a shameless hypocrite?)

Then sneaky old Aaronson goes ahead and links to a something this, thus ensuring that readers like me will continue to return and wade through the standard liberal tripe for the occasional (well, ok -- frequent) gem.

[Update: Seems I've been sloppy, both in facts and in rhetoric. The above was meant as a friendly jab (didja notice the not-so-veiled compliment?) though I can see how it might be taken for an ad hominem attack. Also, as Kenny and others point out, my claim about the film not being allowed to be shown isn't accurate. See here for more information.]

How to Win a Nobel Peace Prize

2007-10-13T13:30:00.000-07:00

Glad to see the prize regain its old prestige. Can't we separate the prizes in category #1 from #2 and #3?

Update: C'mon, people. This is an article bashing Al Gore. And the whole Peace Prize sham. Isn't anyone going to get pissed off enough to react? Or have I scared all those types away a long time ago?..

More math psychology

2007-10-10T13:17:00.001-07:00

Did I really let almost a month elapse without posting? Must be because my life is so wild and exciting. Um, yeah.

Here's a question that's been occupying me for a while -- non-mathematicians' perception of probability. What does a man on the street mean when he says a coin has a 50% chance of landing on heads?

The most likely interpretation is frequentist: if you flip the coin a whole lot of times, you'll see heads about half the time, on average. (How many times is a lot? What does on average mean here? Read my thesis -- at least the section on the Law of Large Numbers.)

But what about one-time events? What does it mean that there's a 30% chance of rain tomorrow? (Tomorrow will only happen once, so any talk of averages is meaningless.) Heck, what does the meteorologist mean by that probability?

Cosma helped me resolve the latter quite satisfactorily in private correspondence (so satisfactorily, in fact, that I feel dumb ever having asked the question). But I turn to the readers:

1. can you make rigorous mathematical sense out of the meteorologist's 30% chance of rain prediction?

2. can you ask your non-mathematician friends what that prediction means to them?

Is There Anything Good About Men?

2007-09-11T06:13:00.001-07:00

I know I'm behind on posting about the things I promised I'd post about; rest assured that I'm behind on work stuff as well.

So in the meantime, read this fascinating piece by Roy F. Baumeister. There's too much incisive analysis in there to give a brief sound bite; you'll just have to read the whole thing. Discussion welcome in the comments.

I like to tell myself that if people didn't send me such pointers I'd be 50% more productive...

Psychology of Mathematical Reasoning

2007-09-01T04:36:00.000-07:00

Recently, I've found myself needing to explain what it is that mathematicians do. Sometimes I say, "we add really big numbers". You'd think people would laugh (or at least give an incredulous look) -- but how many times have you heard a layman casually comment how "math people" deal with "numbers"?

Actually, number theory is a nice vehicle for giving layfolk a taste of what math is about. Everybody knows about naturals and primes (and if they don't, and you're a mathematician who's been put on the spot, it's something you can explain in under a minute). So I tell people, look: there are obviously infinitely many naturals (for any number there's always a bigger one) and there are also infinitely many primes -- but this latter fact is less obvious and requires proof.

Here is where I've run into unexpected troubles. People have no problem accepting the infinitude of the naturals, but what they have trouble appreciating is that it's not obvious that the primes are infinite. "C'mon -- there are infinitely many numbers, so of course there are infinitely many primes!" I've heard this response from more than one person. "Now wait a minute" I protest. The primes are a subset of the naturals, so a priori, they have every right to be a smaller subset. "OK, gimme an example of a finite subset of the naturals". I'm happy to provide the example {1,2,3,4,5}. "Yeah, but you've constructed it as a finite set, so it doesn't count" is the sort of reply I get.

What seems to be happening is that to an untrained intuition, any subset of the naturals defined by a property without explicit bounds appears to be obviously infinite. Has anyone else encountered this phenomenon? Alexandre? Can my mathematician readers try this out on some non-math friends (no need to obtain signed consent forms) and let me know what you find?

Finally, does anyone have a simple example of a "nontrivially finite" subset of the naturals? That is, a set defined by a (simple!) property P that makes no reference to explicit bounds, yet P is provably finite?

Extreme-point fallacy

2007-08-24T06:13:00.000-07:00

First, some administrative notes. Thanks to the readers for the feedback. I got requests for research advice and explanations of techniques from my thesis; I promise to post on both topics shortly.

Do take a look at Daniel's problem in this comment thread. It combines the features of being theoretically interesting and challenging while also being of great practical importance. If anyone has thoughts or literature pointers, please do share them with me or Daniel!

And here's a little teaser to see who's awake. Let D be a subset of R^n of the nicest possible kind: a finitely generated compact convex polytope. Thus, D is nothing more than the convex hull of finitely many points. Let f and g be two convex functions mapping D to R. A mathematician (let's call him Hermann) would like to prove that
f(x) <= g(x)
for all x in D. Now Hermann reasons as follows. He knows (from reading Papadimitriou and Steiglitz, for example) that an affine function achieves its extreme values on the extreme points of a convex domain. From this he concludes that a convex function achieves its maximal values on the extreme points of a convex domain (can you also make this deduction? Hint: the epigraph of a convex function lies above its derivative.). "Aha!" he exclaims. "All I need to do is check that f(x) <= g(x) on the extreme points of D. But there are finitely many of these -- they're just the corners of the polytope!"

You'll agree that verifying f(x)<=g(x) on the finitely many corners of D is, in general, a much simpler task than doing this for all of D. Is there something wrong with Hermann's reasoning, however?

[This is in no way meant to imply that any mathematician named Hermann ever claimed anything of this sort!]

Blog update & open thread

2007-08-17T10:38:00.000-07:00

After months of cluelessness, I finally figured out how to make recent comments appear in that tab you now see on the right; many thanks to the anonymous commenter! No more digging through old posts to see who's left a comment (I've occasionally discovered comments on several week old posts.) Any idea how to make that "recent comments" list longer than 5 (blogger doesn't seem to give me that option)?

Following Daniel's suggestion, I'll make this an open thread. Post your problems (open or solved), tell some jokes, start flamewars -- it's all good! [I've never had to remove a comment or "moderate" in general, but don't push me...]

A CMU undergrad (CS) asks for some generic research advice and I promise to devote a post to this shortly.

Trip report + misc.

2007-08-15T07:47:00.000-07:00

Back in Israel; it's good to be home. Now that the travels are over, I can look back and say "it wasn't that bad" -- but that's not what I would've told you when I was within a hair of getting arrested for refusing to give up my toothpaste at an airport security screening.

My submission got a "distinguished contribution" award at MLG (in lieu of "best paper" since these are extended abstracts). The analysis and probability workshop at Texas A&M was very intense, reminding me yet again how little of my so-called field I know.

"Meaty" content has been sparse here but I have a good excuse. I'm trying to switch gears from a problem-solving to a paper-writing mode. This requires less creativity and more discipline, but is absolutely indispensable -- both for one's career and for keeping oneself honest.

There's no shortage of high-quality, educational and entertaining material on the web (check out the links on the right), thus I feel no pressure to "deliver" to any readership. Speaking of which, if you're a regular reader of this blog, how about leaving a comment? Just so I know the blog has regular (or any) readers. [Not that a lack of readers has ever discouraged me from writing.] Also, feel free to use the comments to make suggestions regarding what you'd be interested in seeing here. Well enough chit-chat. Back to work.

Blogging from the road

2007-08-01T00:32:00.000-07:00

I'm writing from Florence, Italy, where I'm attending the Mining and Learning with Graphs workshop. The paper I'm presenting is the Universal Kernel one. On the off-chance you're reading this and attending the workshop, say hi!

Then it's off to Texas for Concentration Week, namely: "Probability Inequalities with Applications to High Dimensional Phenomena". My talk: Obtaining measure concentration from Markov contraction. Slides will be online soon. [I'm intentionally blurring the distinction between Leonid and Aryeh (they're really the same name); hopefully, this won't cause confusion. Rule of thumb: if we're speaking English, use Leo. If we're speaking Hebrew, Aryeh. If we're speaking Russian, you know what to call me.]

A Chernoff paradox?

2007-07-24T07:09:00.000-07:00

The multiplicative Chernoff bound states that if X is the average of n independent, 0-1 random variables X_i, each with mean p, then

P(|X-p| > tp) < 2exp(-npt^2 / 3).

In other words, the empirical average of independent binary random variables is exponentially concentrated about their true mean. The probability that we're off by a muliplicative factor of t is subgaussian in t. There is a catch, however: rare events are difficult to estimate. Thus, if p is tiny, the bound becomes quite loose. Indeed, if you're flipping a coin whose probability of heads is 10^-6, you can easily see a thousand flips without a single head.

But what about the following "trick" to beat Chernoff? Since X_i=1 is a rare event, let us define Y_i = 1-X_i. Now Y, the average of Y_1,...,Y_n, has expected value p'=1-p, which is large if p is small. So instead of obtaining a loose bound for X in terms of p, we obtain a good bound for Y in terms of p' -- yet X and Y are related in a very simple way. Does this trick really work or have I cheated somewhere?

Made it

2007-07-17T03:03:00.001-07:00

to Weizmann and slowly settling in. Wrapping up some old projects and excited to start some new ones. Stop by Ziskind room 302 and say hello. FYI: my name is אריה in Hebrew.

On the Origin of Languages

2007-06-29T11:50:00.000-07:00

Re-reading the intriguing book by Merritt Ruhlen: On the Origin of Languages: Studies in Linguistic Taxonomy. The basic premise is that contrary to widespread belief, the tools of comparative linguistics can be applied beyond the Indo-European family to reconstruct the roots of a world proto-language. Though it sounds far-fetched at first, Ruhlen makes a compelling case for his methodolgy, and gives some world-etymologies that I can't resist from reproducing below. It gives me particular satisfaction to see these ancient roots manifest themselves in the languages I read, write and speak: Russian, English, Hebrew, Latin. The asterisk indicates an unattested form.

KAMA 'hold (in the hand)'. Ruhlen gives the Proto-Afro-Asiatic root *km, from which we get the Arabic kamasa 'seize, grasp'. Could the Hebrew חמש 'five' be related (as in, the five fingers of the hand)? The Indo-European cognate is *gemo, which appears in Russian as жму 'I press'.

My favorite: MANA 'to stay (in a place)'. Proto-Afro-Asiatic: *mn, which manifests in Hebrew as אמן. This root means 'true, enduring', and is borrowed by many Indo-European languages as amen. Of course, the I-E family has this root occurring natively as well -- as the Proto-IE *men. The Latin manere will be more familiar to English speakers as remain.

Another favorite: MENA 'to think (about)'. Hebrew: מנה 'to count'; English: mind, mental; Russian: мнить.

I'll close with the colorful PUTI 'vulva'. Hebrew speakers will immediately recognize this as פות, via the Proto-Afro-Asiatic *pwt 'hole, anus, vulva'. Speakers of Romance languages might be pleased to learn that when they curse a woman as puta(-na), they're invoking an ancient root, dating back tens of thousands of years!

A final note, and an appeal to my more professional linguist readers. Ruhlen writes: "the Indo-European family has been established beyond doubt," and this has been my belief ever since I began to amateurishly dabble in comparative linguistics. However, I recently had an argument with a computational linguist/computer scientist/mathematician who claims that the IE-family is "merely" a hypothesis, and a rather controversial one at that. Does anyone know of a reputable linguist who doubts the common origin of the so-called Indo-European languages, and questions the basic structure of reconstructed Proto-IE?

Update: More world etymologies are available online.

Update II: To be fair and balanced, I'm linking to a harsh critique of Ruhlen and his methods, with a hat tip to Cosma.

Shameless self-promotion

2007-06-14T07:08:00.000-07:00

Some good news on the publications front. My paper with Kavita Ramanan has been accepted (with minor revisions) to the Annals of Probability. If you just want the main idea (actually, a much simpler proof of a more general form of the main result), this is the paper to read.

Another recent acceptance is my Universal Regular kernel extended abstract, to appear in MLG'07. It's a short 4-page writeup, and if you can resolve the issue of computing K_n, I guarantee you fame and fortune.

I'm hanging out at the FCRC conference (Mehryar is presenting our Rational Kernels paper with Corinna at COLT). So if you're around, find me and say hi, and most definitely come to Mehryar's talk on Thurs. at 2:40. I'll try and blog about the conference a bit later, but we always have Scott to count on.

Thesis online

2007-06-11T02:11:00.000-07:00

After abusing our department coordinator's patience beyond all common decency, I've stopped making revisions on my thesis. I know, I know -- a week from now I'll casually glance at it and see something I'll want to change. But major OCD notwithstanding, enough is enough. I'm putting it online for public perusal; don't all rush in to download it all at once now. As always, questions and comments are more than welcome.

Idea for Sci-Fi story

2007-06-09T09:11:00.000-07:00

How can you tell if the reality you experience is "real" or is just a giant computer simulation? Philosophers realized long ago that of course you cannot; Hofstadter and Deutsch make the a posteriori obvious point that the question itself is meaningless. Any physical process may be viewed as a computation and therefore a "simulation".

But what if we allow the possibility of simulator malfunctions? Address errors, memory leaks, unknown-error-must-shut-down type things. What would it feel like to be in a simulation that suddenly displayed such artifacts? Parts of your universe are working fine as before, but you might locally observe very strange discontinuities and irregularities.

There are sophisticated theories of spacetime defects that I lack the mathematical apparatus to understand (any quantum gravitists want to help out?). Might any of these defects be explicable as computer bugs in the universal simulator? Could one at least get a decent sci-fi story out of this? I'm sure this vein has been already explored -- can anyone point me to a good story? Anyone up the the task of writing one?

Misc. update + possible flamewar

2007-05-29T13:47:00.000-07:00

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 ?

2007-05-21T12:33:00.000-07:00

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

2007-05-16T23:44:00.000-07:00

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

2007-05-10T21:01:00.000-07:00

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

2007-05-08T00:47:00.000-07:00

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

2007-05-03T00:48:00.000-07:00

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

.

עם ישראל חי

2007-04-26T12:02:00.000-07:00

A major mazal tov to my co-bloggers Aaron and Steve on the birth of their sons. Other friends of mine with recent births are Anat & Oren and Tamar & Maxim. In the touchy-feely, lovey-dovey spirit of a baby post, can you guys link to some ridiculously cute baby pictures?

Breakdown of discrete intuition

2007-04-22T19:56:00.000-07:00

Most of the classical inequalities -- Jensen, Hölder, Cauchy-Schwartz -- work for integrals just as well as for sums. In fact, it's best to think of these as integral inequalities with respect to a positive Borel measure (which includes the Lebesgue and the counting measures as special cases, and subsumes both sums and integrals). This can keep our intuition from being excessively taxed; I, for one, prefer to reason about sums and carry that intuition over to integrals. Are there instances where that intuition can fail?

Indeed there are, as Michael Steele shows us in Exercise 8.3 of his book. In part (a), we're asked to show that for all nonnegative sequences , we have

(the solution is given in the book, but readers are invited to attempt this one cold). In part (b), we're admonished against the careless conclusion that for (integrable) , we have

-- does anyone have an example where the latter fails?

A heuristic to guide one's intuition is the following principle of Hardy, Littlewood, and Pólya, called "homogeneity in ." That is, one considers as a formal symbol and checks the order to which an expression is "homogeneous in ." In this case, the lhs is homogeneous of order 2 while the rhs is homogeneous of order 3. According to the heuristic, this incompatibility destroys the integral analog. Anyone have more such examples where the integral analog fails? Could there be a general theorem lurking around?

I wasn't going to

2007-04-17T21:24:00.000-07:00

touch the tragic events at Virginia Tech with a ten-foot pole. People much better informed and more articulate than I are all over this; go to Instapundit for updates and spot-on commentary. However, being in the academia, I feel an obligation to occasionally shout out against the insanity that has become ivory tower conventional wisdom.

Just yesterday someone was in my office telling me how it's impossible to get guns in Japan, and how even the criminal gangs have to manufacture special-purpose bats. So much for that tripe.

I have no desire to turn this into a gun control flamewar; if you're going to comment to the effect that more gun control could've prevented this tragedy, at least entertain me by explaining how it's Bush's fault (and bonus points if you manage to link this to the Israel lobby).

I'm writing about the general powerlessness and impotence fostered by a paternalistic government and eagerly accepted by the cud-chewing masses. Read this article by a Virginia Tech grad student. Money quote:

I am licensed to carry a concealed handgun in the commonwealth of Virginia, and do so on a regular basis. However, because I am a Virginia Tech student, I am prohibited from carrying at school because of Virginia Tech's student policy, which makes possession of a handgun an expellable offense

I am in the same boat. I have a concealed carry permit, have had extensive safety and tactical training, and am even an instructor. Not that this is of any use on campus, where firearms are limited to the omnipresent and omnipotent police. Every time a student gets mugged or assaulted (every month or so, on average), campus police send out a report, with the helpful advice "If confronted by an assailant, don't resist. If he wants your wallet, purse or backpack, give it up." Not a word about carrying even a sub-lethal weapon such as pepper spray. Just give the bad guy what he wants and hope for the best.

Tragedies like this can be prevented if ordinary citizens are allowed to defend themselves instead of being infantilized. A Virginia Tech professor told that student whose article I linked to, "I would feel safer if you had your gun." In a similar vein, my Rabbi has specifically allowed me to carry my pistol in his house, even on Shabbat (when ordinarily carrying items like keys and a wallet is prohibited). As long as idiots like this continue to be the voice of campus officials, we can expect more attacks on soft targets such as schools -- whether isolated acts of insane individuals, or planned terrorist attacks.

[Update May 11, 2007] At least I wasn't kicked out of my school for expressing these views...

Fear and (self) loathing in Pittsburgh

2007-04-16T11:30:00.000-07:00

... and I'm not even talking about my thesis-writing, which is somewhat behind. I am talking about J. Michael Steele's book, The Cauchy-Schwarz Master Class: An Introduction to the Art of Mathematical Inequalities. As someone who's made inequalities his bread and butter over the past couple of years, I figured this would be mandatory reading. Even with Steele's enlightening (and wryly humorous) explanations, this is definitely not light reading. Many of the challenges -- even with the hints -- are pretty darn hard, and I'm terrified to think how I'd approach these without the hints. Then again, there's a reason why some of these inequalities have names like Cauchy, Schwartz, and Hilbert attached to them... In the words of my officemate, "I'll become a better person after working through this book." Probably true for most of us.

A clique bound on coloring numbers?

2007-04-15T12:28:00.000-07:00

We assigned the problem of showing that 3COLOR is NP-complete, meaning that unless P=NP, there is no polynomial time algorithm to determine whether a given graph is 3-colorable. The classical reduction is from 3-SAT, via some clever gadgets.

One student had the idea that clique numbers could be used to resolve graph coloring questions. This is partly right: if a graph contains a K4 (a 4-clique), it is certainly not 3-colorable. What about the other direction?

Well, let's put it this way: testing whether a graph contains a K4 is a polynomial-time procedure (the brute-force search is O(n^4)). So either we've just proved P=NP, or... there exist graphs that don't contain a K4, yet are not 3-colorable. Can anyone exhibit one?

A neat analysis problem

2007-04-11T11:13:00.000-07:00

I'm in thesis-writing crunch-mode, and though there's lots I could blog about, I simply don't have time. Take a look at this problem posted by Guy Gur-Ari, a student at the Hebrew University in Jerusalem:

Let f:[0,1]->R be a real function such that f has a limit at each point.
Does f have at least one continuity point?

It's definitely a good one to work out (try it before you go to his blog for the solution), and check out the rest of his blog while you're at it!

Update: on the topic of analysis, I ordered and am skimming Counterexamples in Analysis -- a must-read for any student of mathematics, though to my relief I seem to already be familiar with most of these. Here's a good one: give an example of a nonconstant function f:R->R that is periodic but has no smallest period. Anyone?

חג כשר ושמח

2007-04-02T00:18:00.000-07:00

No need to be alarmed -- just a standard Passover greeting. Blogging will continue with absolute regularity.

Contraction bounds spectral gap?

2007-04-01T01:56:00.000-07:00

Let A be a column-stochastic matrix. Compute its (complex) eigenvalues, take absolute values, sort in decreasing order, and let lambda2 be the second value on the list (the first is always 1, by Perron's theorem). Lambda2 is (closely related to) the spectral gap of the Markov kernel corresponding to A.

Let theta be max TV(x,y), where x and y range over the columns of A and TV(x,y) is 1/2 the L1 distance of the two vectors x and y. Theta is also called the (Doeblin) contraction coefficient of the Markov operator induced by A.

It's easy to see that lambda2 and theta are numbers between 0 and 1. Here is a simple example where lambda2=0 while theta=1:

0 0 0
0 1 1
1 0 0

It seems that we always have lambda2 <= theta, but I don't have a proof of this. I also can't imagine that I'm the first to observe this -- can someone point me to a reference? Maybe suggest a proof?

Update: thanks to David Aldous and Cristopher Moore for telling me how to prove this (well-known) fact. I won't elaborate, since nobody else seems to care, but if anyone does, let me know and I'll post a proof. I'd be thrilled to see an elementary proof (i.e., one not relying on Perron-Frobenius), so consider that a challenge!

A challenge to the AI-deniers

2007-03-31T22:56:00.000-07:00

Forget global warming and intelligent design. The real debate is whether or not (strong) AI is possible. Now this isn't much of a debate for myself or most people I encounter in my academic circles. We read Dennett and Hofstadter while still in diapers, and use "dualist" as some sort of slur. Of course, occasional dissent does creep in. At a recent openhouse for newly admitted PhD students, I was talking to several colleagues and was surprised when one -- a respected machine learning theorist -- was willing to stick out his neck against AI. Without quite committing to dualism, his argument (if I recall correctly) was along the lines of Penrose's; if I may paraphrase, consciousness is just too freaky to be explained by classical mechanics, and so must be swept under the quantum gravity rug. My friend Gahl (I surmise from our conversation) is basically being indoctrinated to reject strong AI in her freshman class.

So, I thought I'd use this space to give a strong AI opponent (or several) an opportunity to defend their views. Tell us why machines will never think or be conscious. Is it the missing ghost? Something magical about neural tissue? A mis-application of Godel's theorem?

Have I caricatured your stance? Here's your chance to set the record straight!

Is math tautological?

2007-03-26T13:59:00.000-07:00

Scott throws the following teaser:

One example is the surprisingly common view that "all mathematical propositions are tautologies," and therefore can’t convey any new information

and of course I can't help but take the bait. As you surely recall from this discussion, I'm a firm Platonist:

Pythagoras's theorem is a statement about objects that have no width, mass, or time duration. It is not a statement about depressions in sand, sticks, or strings. [...] The fact that in a right triangle, the sum of the squares of the legs equals the square of the hypotenuse was true long before Pythagoras or even planet Earth was around; that it was discovered by some humans (long before Pythagoras, actually) has no bearing on its validity.

However, I had also dug myself into a bit of a hole:

Yes, the boundary between "discovery" and "invention" is indeed blurry; I am not sure I can give a meaningful answer to whether chess was invented or discovered.

And now, thanks to Scott, I think I can dig myself out of that hole. We are going to define two realms: E (for Euclid) and B (for Borges). E contains all the mathematical "tautologies". Thus, if you seed E with the definition of a group, E will also contain all the facts about groups, including the theorems we've discovered, ones we've yet to discover, ones we'll never discover, and ones that are true but unprovable. B is a much more boring set -- it is the collection of all possible statements, true and false, about anything. It includes a statement and proof of Pythagoras's theorem (and its negation with a false proof), a description of the game of chess (and its infinite variations), as well as lots of pure gibberish.

Now I can make a meaningful distinction between invention and discovery. We discover elements of E, but invent elements of B. We discover mathematical truths, but invent proof techniques. The game of chess belongs squarely in B, and thus is an invention.

And what bearing does this have on Scott's comment? Well, E consists of self-contained truths, or tautologies. We can only access a tautology via a proof. The heart of math isn't making true statements, it's finding clever proofs!

Paul Cohen ז"ל + language, human and otherwise

2007-03-26T01:22:00.000-07:00

The discussion following Scott's post on the passing of Paul Cohen has segued into learnability of automata and languages, a topic I take a keen interest in. I've left some comments. Check it out!

Geometry question resolved + debriefing

2007-03-22T10:22:00.000-07:00

First, I should note that the margin question came up in my work with Corinna Cortes and Mehryar Mohri; see our ALT'06 and (to appear) COLT'07 papers.

Next, a shameful admission: I seem to have forgotten how logical contrapositives work. As Avrim reminds me, the perceptron algorithm will terminate in O(1/gamma^2) steps if the data are separable by a margin of at least gamma. Let me quote Avrim:

what you show is that any separator must have w_n that is exponential in w_1, and that furthermore, flipping the sign ofw_1 makes the separator inconsistent. That implies that for any consistent separator, there is an exponentially small change in its angle that makes it inconsistent, which means it has an exponentially small margin.

Finally, a bit of philosophy of math. One should resist the temptation to run numerical simulations, taking the time to think things through with pen and paper first.

Progresss on the margin problem

2007-03-21T21:45:00.000-07:00

Avrim Blum alerts me to something I should've remembered from his class -- one can force a perceptron to make exponentially many mistakes (i.e., achieve an exponentially small margin) with a properly concocted decision list. In fact, digging up my solution to his '04 final exam problem, here is such an example. Assuming my readers think in MATLAB (much as Scott thinks in BASIC), consider the following function:

function [X,Y] = badmargin(n)
X = eye(n);
for k=2:2:n
X(1:1+n-k,k:n) = X(1:1+n-k,k:n) + eye(n-k+1);
end
X = [[X;zeros(1,n)] ones(n+1,1)];
Y = (-ones(n+1,1)).^([2:n+2]');
return

Here's the output [X Y] for n=9:
1 1 0 1 0 1 0 1 1 1
0 1 1 0 1 0 1 0 1 -1
0 0 1 1 0 1 0 1 1 1
0 0 0 1 1 0 1 0 1 -1
0 0 0 0 1 1 0 1 1 1
0 0 0 0 0 1 1 0 1 -1
0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 1 1 -1
0 0 0 0 0 0 0 0 1 1

(the vectors x in {0,1}^9 are treated as rows, and the labels y = +/-1 are appended at the end).

Using badmargin(n), for n=2 to 20, to generate labeled data sets and running SVM on these, we get the following plot:

which is highly suggestive of exponential decay. It remains to actually prove that this explicit construction achieves exponentially small max-margin. Any takers?

Elementary Maurey's theorem + ode to interaction

2007-03-20T22:07:00.000-07:00

Maurey's theorem (rather, one of them) states that if P is the Haar (i.e., normalized counting) measure on S_n (the group of all permutations on n elements) and d is the normalized Hamming metric on this group, then

P(f-Ef > t) <= exp(-nt^2 / 8),

where f:S_n -> R is 1-Lipschitz w.r.t. d. See Schechtman's paper for a proof; it is done via the notion of metric space length.

In our conversation at Berkeley, Jim Pitman suggested a simple way to parametrize uniformly random permutations as an independent process. At each step i, 1<=i<=n, you uniformly pick an integer between 1 and i as the location in which to insert the next element. Thus we can recover Maurey's theorem in a simpler way, and with better constants, via McDiarmid's inequality:

P(f-Ef > t) <= exp(-2nt^2),

where P and f are as above. At first I couldn't believe it would be this simple, but Gideon tells me that I'm right.

The greater moral of this story is that I should talk to people more. I can't overstate the value of this blog as a research tool -- look no further than the high quality discussions here, here, here, and here (and this isn't counting the email exchanges that some posts generate). But you can't count on the experts to always stumble on your blog post -- nothing beats talking to one in person!

Miscellanea

2007-03-12T23:27:00.000-07:00

Slow blogging this week as I'm in California, giving talks at Stanford and Berkeley (yeah, it's the same talk; they're both probability seminars and this is essentially my thesis talk). Swing by if you can!

Geometry of DFAs

2007-03-06T12:49:00.000-08:00

As before, define to be the set of all deterministic finite-state automata (DFAs) on states over some fixed alphabet . As usual, we require that every DFA start in state 1, meaning that . Define the following metric on : for , let be their symmetric-difference DFA -- meaning that accepts precisely the strings that are either in or in but not in both. Constructing such an automaton is easy, as is minimizing it. So, assuming is in minimized form, define , where is the number of states in a DFA. It is straightforward to verify that is a valid (pseudo-)metric on .

This notion came up in my conversation with Jason Franklin, who was looking for a natural metric on automata, for security-related reasons. I suggested the metric above, and I'm wondering if it's appeared anywhere in literature. It's a natural measure of the complexity of the language on which two DFAs disagree.

Any finite metric space has a well-defined length; the definition may be found in Schechtman's paper. Let be any finite metric space. For , define an -partition sequence of to be a sequence

of partitions of such that refines and whenever and, there is a bijection such that for all .
The length of is defined to be the infimum over all -partition sequences.

Bounding the length of has immediate applications to -concentration under the normalized counting measure on , as explained here.

I am interested in computing (really, upper-bounding) the length of . Any takers?

Geometry question

2007-03-02T14:06:00.000-08:00

Consider the binary hypercube B_d = {0,1}^d naturally embedded in R^d. I take some hyperplane H and slice B_d into two pieces, labeling the corners on one side of H positive and on the other side negative. Then I forget about H and find the maximum-margin hyperplane W that separates the positive corners from the negative ones. Define rho(d) to be the worst-case (i.e., smallest) margin obtainable in this way for dimension d. Formally,

rho(d) =
min_{all hyperplanes H}
max_{all hyperplanes W that induce the same dichotomy as H}
(the margin attained by W).

How does rho(d) behave? I recall some numerical simulations a couple of months ago suggesting that it can be exponentially small, on the order of 2^{-d}. Anybody out there aware of any known results? This would be really good to know!

Another crack at old Georg

2007-03-01T18:01:00.000-08:00

Just as our faith in Cantor grew in the last post, doubt is once again starting to creep in. I'm talking about the well-ordering principle, which says, unsurprisingly enough, that any set can be well-ordered. What this means for the reals is that there is a total ordering relation (which most emphatically is not the usual "less than" relation on R) -- let's denote it by x <' y -- that well-orders the reals. This relation induces the ordering
a <' b <' c <' ...
and every real number r will eventually appear in this chain.

Now the $1.64 question is: why can't we apply Cantor's diagonal argument to this well-ordering to construct a number that doesn't appear in the chain?

Go home, Cantor!

2007-03-01T14:28:00.000-08:00

Cantor's proof of the uncountability of the reals goes like this. Every real number in (0,1) has a unique nonterminating binary expansion [every word there is important; nonterminating means not ending in all zeros]. You show that the members if (0,1) are not countable by contradiction. If there were an exhaustive enumeration (i.e., 1-to-1 mapping between (0,1) and the naturals), we could always construct a new number by flipping the first bit of the first one, 2nd bit of the 2nd, one, and so on. Anyone seeing this for the first time should go look it up.

I have a student who insists he's broken Cantor's argument. Take the following list, he says:
.01111111....
.01011111....
.00111111....
.00011111....
.00001111....
.00000111...

and so on. If you construct a number by flipping the bits on the diagonal, you get
.1000000... = .0111111...
which is the first number on the list. Can someone explain why Cantor's theorem still holds? Ideally, the explanation would be provided by the student himself. What do you say, "D"? I gave you a hint after class...

A universal Turing kernel?

2007-02-27T14:39:00.000-08:00

At the end of my talk, someone asked why I focus exclusively on DFAs. After all, my result that any countable concept class over a countable sample space is linearly separable (in this sense) works equally well for push-down automata or even Turing machines. My first (mildly petulant) answer is that DFAs are the only automata I'm comfortable with and I won't be ready to move on to more powerful automata until someone resolves the star-height problem (at which point I'll grudgingly grant humanity the right to graduate on to higher machines).

Someone else was quick to suggested that the analogous kernel for Turing machines, T_n(x,y), would have to count the number of Turing machines on n states that accept both x and y -- and surely this is undecidable. But is that obvious? Might there not be some clever way of computing the kernel without solving the halting problem?

Turns out, there is not; this was shown by Jeremiah Blocki, a student in my class -- who, incidentally, has taken up the challenge of the notorious problem #3.

Proofs by induction

2007-02-26T09:42:00.000-08:00

When we teach proofs by induction in high school or early undergrad, they tend to be rather simple. Or rather, the induction tends to be "trivial" in the sense that it's obvious
1. what structure to do the induction over
2. how to decompose the claim for n+1 so as to invoke the inductive hypothesis

Examples of such simple uses of induction include proving the sum-of-squares-(cubes, etc.) formula, and proving that if a language L is context-free then so is its reversal L^R.

We the instructors somewhat lament this state of affairs, as it gives a misleading impression of induction. A student might dismiss induction as trivial and vacuous, or on the contrary, come away believing that induction is a magical, all-powerful tool that does proofs for you, relieving you of the burden of thought.

So we looked hard for examples of clever use of induction. Here's a good problem to start with:
Let f_p(n) be the sum of the first n powers of p:
f_p(n) = 1^p + 2^p + 3^p + ... + n^p.
For any given p (say, p=3), it is straightforward to verify (by trivial induction!) the f_3(n) is a 4th degree polynomial in n. It's a lot trickier to prove that for all p, f_p(n) is a polynomial in n of degree (p+1). Can you do it? No need to invoke Bernoulli numbers here -- we're not asking for the coefficients of that polynomial. There are a couple of elementary, self-contained proofs -- using clever induction! -- can you find one?

Actually, all of my difficult proofs have been by induction. Various concentration of measure results (Talagrand, Marton, yours truly) have induction at their core. It's a shame we can't present these in a typical undergraduate class (too much overhead), since their use of induction is rather non-trivial.

Do people have more examples of nontrivial proofs by induction?

Quantum disinformation

2007-02-22T20:58:00.000-08:00

Check out the discussion over at Scott's blog. It covers a wide range of topics, including: the (typically) shoddy mainstream journalistic coverage of technical material, the powers/limitations of quantum computing, and finally, something near and dear to my heart -- the nature and role of mathematical proofs.

Minimal consistent DFA revisited

2007-02-20T21:10:00.000-08:00

I'm glad we ended up putting this problem on the midterm (as extra credit). A handful of folks nailed it dead-on, but it's still causing confusion for some -- which means it's a good one to work out! Now that it's been assigned and graded, the readers are invited to say anything and everything they want about it in the comments.

BTW, the problem of finding the minimal consistent DFA is NP-hard; this fact more or less motivates the line of research I'll be presenting at this talk tomorrow (today).

Linear/convex programming in infinite dimensions?

2007-02-19T22:11:00.000-08:00

I'm sure I'll find the answer in Rudin's Functional Analysis, but perhaps a helpful reader will educate me and the rest; otherwise, what's the point of blogging?

Say we have a Hilbert space H -- so it's locally convex and the Krein-Milman theorem applies. Let K be a compact convex set in H. Is it still true that linear functionals achieve their maxima on extreme points of K? What about convex functionals? [I should really look up the latter in the last chapter of Borwein and Lewis.]

Seems like these should be true, but I've learned to mistrust my intuition in high (and a forteriori infinite) dimensions. Anyone have an answer handy?

Arbitrarily large vs. infinite

2007-02-18T14:05:00.000-08:00

Infinity is a subtle mathematical notion, which is logically related to -- but not synonymous with! -- the notion of "arbitrarily large". Actually, when dealing with limiting values of magnitudes, the two more or less coincide. When we say that the series
1 + 1/2 + 1/3 + 1/4 + ... = Infinity
what we mean is that no matter now big of an N you pick, I can always find enough terms in that series whose sum will exceed N. In this case, infinite really is shorthand for "increasing without bound" or becoming "arbitrarily large".

When dealing with cardinalities -- as opposed to magnitudes -- all bets are off. That was the crux of the closure under star question. [BTW, I think I've found the bug in Ivan's proof that closure under concatenation implies closure under star. The set U need not be a complete lattice. Otherwise, your argument could be used to show that the function f:Z->Z defined on the integers by f(x)=x+1 has a fixed point.] Set theory is rife with examples where some property P holds for arbitrary finite collections but not infinite ones:

in point-set topology, a finite (but not necessarily countable) intersection of open sets is open
in analysis, there are finitely (but not countably) additive measures
etc

There are techniques, most (all?) of them based on transfinite induction, for proving that P holds for infinite collections given that it holds for arbitrary finite ones. Knaster-Tarski is one; Hausdorff maximality principle and Zorn's lemma are other favorites. All are equivalent to the axiom of choice.

"Progressive" math

2007-02-17T19:26:00.000-08:00

Alexandre Borovik's blog is my usual source of examples of semi-literate math-is-being-used-for-evil hysteria. Staying true to this blog's mission statement, I sincerely endeavor not to excessively dilute the mathematical content with politics. I also make it a general principle to rebuke outrageous claims only if they are championed by a reasonably reputable source; life is too short to engage in reasoned intellectual discourse with every obscenity-shouting hobo in the street.

For this reason, though I had seen the unhinged, lunatic rants quoted here about a week ago, I didn't see fit to address them, basically relegating this to the hobo-in-the-street category. Brief synopsis: math has cryptographic and defense applications, and we all know these are tools of imperialistic oppression to keep down the working class, man. (I am hoping that the quote by Rabelais about the evil use of frontal lobes is meant to parody Ken Burch and Kevin Laddle, but one can't know for sure.)

Writer appreciation day: John Derbyshire

2007-02-15T22:32:00.000-08:00

This past December I was giving a talk at Princeton and was pleasantly surprised to find John Derbyshire's book lying on a coffee table in the math lounge in Fine Hall. I was even more pleased to see that this work had won the Euler Book Prize.

I am a big fan of Derbyshire, and encourage everyone to read his columns every now and again. If you've never heard of him, this interview will serve as a decent crash-course intro. Derbyshire is a writer of a rare breed, possessing all the erudition of a crusty academic and all the reckless, unapologetic calling-them-as-he-sees-them brutally refreshing honesty of a man who has nothing to fear from the PC commissars. He is eminently quotable; here are my personal favorites:

Let's face it, in the great 20th-century struggle between the state and the individual, the state has won, game, set, and match.
The fact is that political stupidity is a special kind of stupidity, not well correlated with intelligence, or with other varieties of stupidity.
Wherever there is a jackboot stomping on a human face there will be a well-heeled Western liberal to explain that the face does, after all, enjoy free health care and 100 percent literacy.

(since these came from comments on a thread, I'm going to ask Mr. Derbyshire to authenticate them).

Sure enough, he has his share of detractors -- what hard-hitting pundit does not? They roll out the usual accusations: racist, sexist, bigot, hater. To all the people losing sleep over John Derbyshire's alleged hatred: relax, he doesn't hate you. Knowing him, he probably doesn't give a damn about you.

Conservation of dimension and randomness

2007-02-15T10:07:00.000-08:00

Fix two integers 0 < n < m and consider the following seemingly unrelated questions:

(a) is there a function f:{0,1}^n -> {0,1}^m such that if its input X is uniformly random over the domain then f(X) is uniformly random over the range?

(b) is there a continuous bijection g:R^n -> R^m ?

The answer to both is negative. I'll give hand-wavy proof sketches and invite readers to fill in gaps (or point out logical lapses), or give pointers to clear, self-contained proofs. If (a) were true, we could arbitrarily amplify the randomness of some fixed-length input, obtaining lossless compression of arbitrarily long strings. If (b) were true, such a g could be uniformly approximated by differentiable functions, whose local Jacobian would have to be an invertible linear map from R^n to R^m.

Now, what do the two have in common? The first one violates "conservation of randomness" -- we get more random bits than we started out with, for free. The second one violates "conservation of dimension" -- we locally span a space of a higher dimension than what we started out with.

Update: If you take Cosma's class, you'll see an apparent violation of conservation of randomness. Define the logistic map F:[0,1] -> [0,1] by F(x) = 4x(1-x). Let N:[0,1]->{0,1} be the nearest-integer function. Draw x_0 uniformly at random from [0,1] and consider the sequence x_0, x_1, x_2,..., where x_{i+1} = F(x_i). It's easy to show that the sequence y_i = N(x_i) consists of iid Bernoulli variables. So it seems that with a single random draw of x_0, we got an infinite sequence of independent random variables for free. What's going on here?

More feminist math

2007-02-12T01:45:00.000-08:00

This started out as a comment to Alexandre Borovik's post but as I was writing it I decided it merits a post of its own.

I'd craft a strongly worded reaction to this garbage (the author compares sexual abuse to "math abuse"), but I hate to repeat myself.

I can only add that John Kellermeier's suggestion that mathematical education abandon its "right" answers and methods would be laughable if it weren't so frighteningly realistic.

This isn't to say that every problem has a unique answer or way of arriving at it. Some problems even have no known answers! But for pedagogical reasons, we tend to give youngsters well-posed, solvable problems that illustrate some specific correct technique.

Is Kellermeier really so humorless and out of touch as not to realize he's imitating Jack Handey?

Instead of having "answers" on a math test, they should just call them "impressions," and if you got a different "impression," so what, can't we all be brothers?

Except I guess you can't say "brothers" anymore. Is "siblings" sufficiently inclusive and diverse?

Concatenation implies star?

2007-02-12T01:25:00.000-08:00

Fix a finite alphabet -- let's take it to be {0,1} for simplicity. A language L is a collection of finite strings over {0,1}, i.e., L is a subset of {0,1}^*.

Let U be a family of languages. We say that U is closed under an operation if applying the operation to members of U always yields members of U. Suppose U is closed under concatenation -- that is, if L_1 and L_2 are in U then so is L_1 L_2 (the set of all strings with prefix in L_1 and suffix in L_2).

A student claimed in a homework problem that if U is closed under concatenation then it is closed under the star operation (L^* is the set of all strings obtained by concatenating n members of L, for n=0,1,2,...).

Is this true? Answers/discussion welcome in comments!

Sampling Lipschitz functions

2007-02-07T14:56:00.000-08:00

Fix a positive integer n and let F_n be the set of all functions
f:{0,1}^n -> [0,n]
that are 1-Lipschitz with respect to the Hamming metric. As a reminder, for two sequences x and y in {0,1}^n, their Hamming distance d(x,y) simply counts the number of indices in which they differ. The Lipschitz condition just means that
|f(x) - f(y)| <= d(x,y)
for all x and y in {0,1}^n. It's obvious that F_n is a compact, convex polytope in a finite dimensional space (that space being R^(2^n) ). How would you sample a function uniformly at random from F_n?

I have a method that I'm pretty sure is correct, but I'd love to generate some discussion...

Proofs & Math Pedagogy

2007-02-06T19:24:00.000-08:00

Alexandre Borovik's post reminded me of the good old days when I was a math undergrad and would pay an annual visit to my 6th grade Gifted&Talented math teacher. She let me teach a lesson, which proved popular enough that the following year I got two periods in a row. The class consisted of that rare breed of American 12-year-olds who are genuinely hungry for mathematical knowledge and can appreciate beauty and aesthetics when they see it. These kids, I remind you, have never seen calculus or trigonometry, and don't have a solid grasp of the real number field.

I would start out by writing three expressions on the board:
(a) 1 + 1/2 + 1/4 + 1/8 + ...
(b) 1 + 1/2 + 1/3 + 1/4 + 1/5 + ...
(c) 1 - 1 + 1 - 1 + ...

and ask them what each series sums to. Most had no difficulty getting (a) right, and many could even give a pictorial argument to support their answer. (b) gave them more trouble, and who can blame them? It's far from obvious, at first glance, how the harmonic series behaves; even using a computer and making plots, one would become frustrated by the slow divergence. I let the cat out of the bag by telling them that it does in fact blow up, but they'll have to wait for college and Baby Rudin to become really convinced. [Incidentally, as all intelligent 12-year-olds, they are fascinated and confused by the concept of infinity. I glossed over it at this point, saying that "infinity" in this case is shorthand for "increasing without bound" or becoming "as large as you want if you add up enough terms". We'll come back to it shortly!] But what to do about (c)? One hardly needs a computer simulation or a formal proof to see that something is not kosher about that expression. If (b) can be called a "number" in some extended sense, there is no sense in which (c) makes sense a number. So, lesson number one: just because we can write it down, in numbers and symbols, does not necessarily mean it's well-defined or makes sense.

I would go on to ask if anyone had heard of irrational numbers and could name an example of one. A few hands would go up -- "pi" would be the standard answer. Whether anyone knew why, or could formally define irrational numbers, is another matter. Well, we didn't prove pi's irrationality, but we did define rationals and irrationals, and more importantly, we'd see a rigorous proof of the existence of irrational numbers! For most of the kids, this was the first time seeing a formal proof, and by the looks on the faces, I could see that a paradigm shift was taking place. What a novel concept -- you don't just accept facts handed down from authority, but become convinced of them through a waterproof argument!

That would take about 45 minutes. In the next 45, I'd prove -- again, in full rigor -- Cantor's diagonalization theorem of the uncountability of the reals. There is absolutely nothing in the definition of cardinality or in Cantor's proof that is beyond the grasp of a 12-year-old. They were getting it; I can vouch for that. I have no idea why we make students wait until college to see this.

Concentration of Boolean functions?

2007-02-04T16:41:00.000-08:00

In the course of giving an invited talk at Mehryar Mohri's NYU machine learning class this fall, I gave the example of the parity function f:{-1,1}^n -> {-1,1} to illustrate how the concentration phenomenon can break down without a Lipschitz condition. The natural metric here is normalized Hamming and it's immediate that the parity function is not Lipschitz with respect to this metric (or rather its Lipschitz constant is 2n). On the other hand, under the uniform distribution on the discrete cube {-1,1}^n, we have
P(f=-1)=P(f=1)=1/2, while E[f]=0, which means that f is not concentrated about its mean (or any other constant).

Someone in the audience (unfortunately, I don't remember who) asked about the majority function. Totally in improvisation mode, I blurted out that perhaps the majority function is "almost Lipschitz" and one might be able to apply Kutin's generalization of McDiarmid's inequality. [Regarding the latter, I'm surprised this fine paper isn't getting more attention or seeing good applications. Or is it?]

Fast forward to this spring, when I'm sitting in on Ryan O'Donnell's very enjoyable class. We're seeing all sorts of characterizations of properties of Boolean functions in terms of their Fourier coefficients and related concepts. Given my one-track mind, I keep wondering if one can say something about the concentration of Boolean functions with low energy or degree.

Having thought about it for a bit, I see my hopes were naive. Take the simplest nontrivial function -- a dictator (that is, f:{-1,1}^n -> {-1,1} whose values depend only on a fixed single bit). As shown in homework 1, dictators have a rather simple Fourier decomposition. However, for a dictator, we have P(f=-1)=P(f=1)=1/2 and E[f]=0, so we can forget about concentration.

What about majority? The majority function has a more complex Fourier structure (could this be a future homework problem?). Some quick numerical trials indicate that when f:{-1,1}^n -> {-1,1} is the majority function, we have E[f] tending to 0 and P(f=-1), P(f=1) tending to 1/2. I haven't proved this (another possible exercise?), but if it's true then I hope whoever asked me that question reads this post!

A couple of afterthoughts. (1) A recent inequality of Kim and Vu allows one to prove concentration of polynomials with nonnegative coefficients. Since the Fourier expansion is a multivariate polynomial, one might be able to apply Kim-Vu to certain classes of Boolean functions. Is there a characterization of the Boolean functions having nonnegative Fourier coefficients?

(2) I was at first excited to see the Poincaré inequalities, as they are one method for proving concentration. But one must be careful, as Poincaré and log-Sobolev inequalities are really asserting a property of the probability measure, not any specific function. In particular, the Poincaré inequality on the discrete cube is telling us that the product measure on {-1,1}^n has exponential concentration with respect to the Hamming metric. But we already knew a stronger fact (subgaussian tails) via Chernoff bounds!

Update Feb 6: I feel a bit silly running numerics on the majority function and suggesting the observation that E[f] tends to 0 and P(f=-1), P(f=1) tend to 1/2 as an exercise. It's obvious.
Update II: An obvious point that I forgot to make is that it's a bit vacuous to talk about concentration of {-1,1} valued functions; this only makes sense if f_n:{-1,1}^n -> {-1,1} is approaching a constant. The original concentration question was actually about real-valued functions on the cube, but the simple reasoning above show that small Fourier coefficients do not imply concentration.

Characterizing total variation

2007-02-01T18:32:00.000-08:00

Let be a finite set and consider two probability measures (distributions) on , and . One can define many notions of "distance" between and , but a particularly important one (at least in my work) is the variational distance. By definition,

-- that is, we maximize over all subsets of the difference of the measures assigned by the two distributions. It is a well-known fact, routinely left as an exercize for the reader, that

where is just the norm of the difference , viewed as a vector in .

It is also well-known that
,
where the infimum is taken over all the distributions on , having marginals and , respectively, and the random variables are and are distributed and .

Let us define the (unnormalized) measure as the pointwise minimum of and . A somewhat lesser-known fact is that

(I have not seen this mentioned anywhere, but can't imagine that I'm the first one observing this). It easily follows that if and are minorized by some probability measure -- i.e., there is an for which holds pointwise, we have
.

Finally, here is a relation that has a chance of being novel. Consider two finite sets , with probability measures on and on . We will write for the product measure on (and similarly for ). Then
.

To the best of my knowledge, this "tensorization" result was first proved here, but I'd be very grateful if anyone would bring an earlier reference to my attention.

None of these are difficult to prove, but if pressed, how would you do it? I have a simple technique, based on a linear programming principle, that yields all of these pretty much effortlessly (see Lemma 2.6 in the linked paper for the idea). Any other simple proofs out there?

Friday meetings

2007-02-01T17:26:00.000-08:00

If we're supposed to meet on Fri, Feb 2, and you don't see your name below, please email me!

1:00 Salahuddin C.
1:30 Vinay C.
2:30 Jeremiah B.
3:00 David W.
3:30 Jonah S.

Reminder: my suggestions for projects can be found here. Try to have a clear idea of what you want to do before the meeting.

A neat problem

2007-01-27T13:35:00.000-08:00

communicated to me by co-blogger Steve Miller, which he's too busy to post. Two players, A and B, start out with $a and $b dollars, respectively -- where a and b are natural numbers. They flip a fair coin, and every time it comes up heads, A gives 1 dollar to B; for every tails, B gives 1 dollar to A. The game ends when one of the players has zero dollars (and the other one has a+b). What's the probability that player A wins?

I was able to guess the answer right away (Steve told this to me on the phone), but this is probably more luck than anything else, as these intuitions can often be misleading. In any case, an answer is worthless without a proof, which Steve tells me is not entirely trivial. Furthermore, we don't know what happens if the coin, instead of being fair, has bias p. Anyone out there know?

A harder analysis exercise

2007-01-27T11:51:00.000-08:00

... but absolutely essential for anyone wishing to deepen his understanding of the real line:

Let C be the standard Cantor set, a subset of the interval [0,1]. One can easily verify that this set is

uncountable
closed [i.e., all Cauchy sequences in C converge to points in C]
totally disconnected [i.e., contains no contiguous interval (a,b) ]
has Lebesgue measure 0 [i.e., its "total length" adds up to 0]

If these aren't obvious, it's definitely worthwhile to verify them; it's not hard. Note that for some time mathematicians were wondering if any set with properties (1) and (4) even exists.

Put E = [0,1] \ C; that is, E is the complement of C in the interval [0,1]. Then E is an open set in [0,1]. Now any open subset of the real line is a countable union of disjoint open segments; again, if this is news to you, do take the time to convince yourself. [A glossary of topological terms may be found here, but if you're seeing these terms for the first time, it might be too early to attempt this problem.]

Thus one might reason as follows: "Every open segment comprising E corresponds to two points in C. But the segments of E are a countable collection, while the points of C are uncountable - we have a contradiction." Resolve the apparent contradiction. You will be enlightened, or your money back.

Solutions/discussion welcome in comments.

Maybe I should've

2007-01-24T15:06:00.000-08:00

done this for my postdoc search?

[thanks for the note, Steve!]

An easy analysis exercise (+philosophy)

2007-01-24T06:05:00.000-08:00

I'm (unfortunately) not teaching a class on analysis, but if I were, I'd assign problems like this (as a warm-up, of course :)

Construct a family of measurable functions whose pointwise supremum is nonmeasurable. [Answers + discussion welcome in comments.]

This very simple exercise illustrates one of the key intuitions about measurability: the only way to obtain non-measurable objects from measurable ones is by some "uncountable process" -- uncountable unions, uncountable suprema, etc. Of course, the very construction of non-measurable sets depends on the axiom of choice, which is equivalent to the well-ordering principle, which manifests itself as Hausdorff's Maximality Principle or Zorn's Lemma; these all enable (uncountably) transfinite induction.

This post was prompted by my reading up on empirical process theory (just when I thought I was starting to get a solid grasp of it, I've discovered whole new oceans) -- mainly stuff by David Pollard and Michel Talagrand. Since uniform convergence involves taking suprema over function families, great care must be taken to ensure measurability (or outer measures must be used, but these create problems of their own). I hope to post on these topics in greater depth when I have time.

A FLAC exercise

2007-01-20T06:05:00.000-08:00

This one will almost certainly be assigned. Please do not post answers here.

For any finite state automaton A, deterministic or not, size(A) will denote its number of states.

Construct a family (sequence) of NFA's, {N_k}, such that size(N_k) is growing polynomially in k, while size(D_k) is growing exponentially in k, where D_k is the minimal deterministic automaton equivalent to N_k.

Hint: you may use the fact that the sum of the first k primes has polynomial growth, while the product of the first k primes has exponential growth.

Transgressing the Boundaries: Toward a Non-Hegemonic Feminist Mathematical Theory

2007-01-15T03:38:00.000-08:00

The title is an homage to Alan Sokal's witty demonstration of the vapidity of the whole postmodernism industry. I've always considered myself rather fortunate, as a mathematician, to engage in research safely outside the reach of the PC commissars. Yet every now and again the hydra thrusts one of its many heads into our pristine art; this time, under the heading of "social justice". I am not going to attempt to define justice here (I am not even sure that I can at all), but if there's one thing I'm sure of, it's that mathematics has nothing to do whatsoever with justice, or for that matter, with any aspect of the physical world. Sure -- physicists and engineers have used mathematical tools with great success to build scientific theories and neat gadgets. But math lives in its own separate Platonic world and we mere mortals can only hope for an occasional peek inside (much as no one "invented" electricity, there are no mathematical "inventions", only discoveries).

Which brings us to this pearl of wisdom (via Alexandre Borovik):

The content of mathematics is typically thought of as neutral. That is, to most, mathematics is considered a domain that is devoid of ethical-moral implications. One can use mathematics for whatever purposes one wishes, but the mathematics itself is not good or bad, it just is. If I am right and mathematics classrooms frequently teach powerlessness, then the notion that mathematics is essentially neutral needs to be revisited.

This reminds me of a Russian joke. A teacher in elementary school is explaining long division on the board. Suddenly, a KGB officer walks into the classroom and listens in for a while. During break, he walks over and exchanges a few quiet words with the teacher. When class resumes, the teacher announces, "Class, we've received directives from above: from now on, division will be done like this..."

I've been maintaining for years -- I believe it's my original observation -- that some of humanity's greatest atrocities were committed when people mixed the rational and the ethical spheres of reasoning. The rational/scientific sphere deals with measurable quantities and exact facts. It is a tool, completely devoid of ethics and morality: it can help you cure cancer or build a bomb -- your choice. The ethical/moral/religious sphere deals with questions such as, "What is the right thing to do?" When religion encroaches on matters of science, we get the Inquisition. When rationality overrides morality, we get Nazi experiments on humans.

It is a common philosophical mistake to endow inanimate objects with moral characteristics. A gun is not inherently good or evil -- it can be used to commit murder or save lives. It's a tool, like a hammer or a ruler. Only conscious sentient beings can be judged on a moral scale and labeled as good or evil.

The author of that piece -- Kurt Stemhagen -- makes two fundamental mistakes. First, he conflates mathematical constructions with their real-world applications. Second, he attempts to impose a moral rubric on an inherently a-moral realm of reasoning. (Teichmüller was a Nazi mathematician who actively persecuted Jews. Should we boycott the study of Teichmüller spaces?)

Visualizing Measure Concentration

2007-01-12T04:52:00.000-08:00

In the course of giving my talk at Weizmann, I made the usual point about trying to visualize measure concentration:

A word of caution for those attempting to visualize "measure concentration": imagining a narrowly peaked, one-dimensional distribution is tempting but wrong. This is a genuinely high-dimensional phenomenon.

I gave the example of the uniform distribution on the binary hypercube, {0,1}^n, which certainly exhibits the concentration phenomenon (via Chernoff bounds, for example) -- yet it's as flat as they come; there are no peaks here! Someone from the audience pointed out that if one looks at the distribution of a Lipschitz random variable f:{0,1}^n -> R, then it will indeed be peaked. This threw me off a bit, as it was correct and seemed to trivialize my point, which I knew had some non-trivial content.

Having thought about this off-line I've recovered that non-trivial point. For any measure on {0,1}^n there is a function f:{0,1}^n -> R whose induced random variable will be very peaked. It's also not hard to concoct very clumpy distributions which will induce peaked random variables for a wide class of functions f. The remarkable thing is that uniform distributions produce peaked Lipschitz random variables. Conversely, if one allows badly non-mixing measures on {0,1}^n, it's easy to construct non-peaked Lipschitz rv's. The philosophical take-home message is that while it's trivial to create "orderly" random variable in specific instances, it's quite remarkable to observe that a rich collection of random variables will acually be quite well-behaved under rather general conditions.

A FLAC exercise

2007-01-07T03:52:00.000-08:00

This exercise may or may not be assigned in the course I'm TAing this spring, but it's a good one to work out. It definitely had me confused at first, and I was in good company.

A teacher gives you a bunch of strings over some finite alphabet and labels each string as "positive" or "negative"; we'll refer to these labeled strings as the sample S. A deterministic finite-state automaton (DFA) is consistent with the sample S if it accepts the positive strings in S but not the negative ones. Let A0 be any DFA that is consistent with S and let A1 be the automaton obtained by minimizing A0 (by this point in the course you'll have learned efficient minimization procedures). Is A1 the smallest DFA that's consistent with S?

Please don't post the answer in the comments!

NLP revisited

2007-01-07T03:38:00.000-08:00

I almost certainly didn't do the field of Natural Language Processing justice. Fortunately, I've discovered some language-related blogs. The first two have more of a computational flavor. The last one, of a more philological bend -- called "Language Log" -- is now a permanent fixture in my "Other Interesting Stuff" section.

Logic

2007-01-05T06:45:00.000-08:00

While I have the attention of a cast of mathematicians, I was wondering if I any one of you could recommend a good introductory book on formal logics? I've obviously studied the basic logical concepts in various fora before (discrete math, AI, programming semantics), and I now know enough to get myself very confused. I don't have a good resource for really understanding the different flavors of logic: constructive, modal, etc. (I know this is a bit off topic, but it isn't completely unrelated to the topic of languages.)

Miscellanea

2007-01-03T12:45:00.000-08:00

If you're trying to physically locate me over the next two weeks, try room #3 in Ziskind building of the Weizmann Institute, in Rehovot, Israel -- where I'm being very kindly hosted by Gideon Schechtman. Blogging will be light due to the tight schedule (giving 3 talks: Jeruslem, Weizmann, Technion), but I'll try to report on interesting seminars that I heard (like the one today).

A quick note about the comments: they're unmoderated and no registration is required; I'm hoping that no moderation on my part will ever be necessary. It's fine occasionally to lapse into politics, but I was hoping to see more math discussions!.. Finally -- I am plain curious as to who's reading this barely-a-week-old blog and leaving comments. If you'd leave a name when commenting I'd be much obliged!

On Dictionaries and Language

2007-01-01T15:45:00.000-08:00

This is prompted by the Weekly Standard piece on Samuel Johnson. The author, Jack Lynch, credits Johnson (among other things) for taking the trouble to define such "obvious words" as take and get -- which lexicographers before him had neglected. The segue into philosophy of language is inevitable: do words have "primitive", "irreducible" definitions? Or are dictionary entries necessarily circular, since we can only define words in terms of other words? Since much ink has already been spilled on these matters (cf. Wittgenstein, Chomsky and David Lewis), let us frame the question more operationally. Can a computer program, in principle, reason about the world (on par with humans) given only text as input and output (for learning)? Or must it necessarily have sensory perception in order to become sentient?

My training at Bell Labs, where I was most heavily influenced by Daniel Lee, leads me to conjecture that a large enough corpus of text, with sufficiently clever statistical processing, is enough to train a machine that would pass the Turing test. Supporting evidence: congenitally blind people are able to reason about colors perfectly well, without having any qualitative experience of the phenomenon. The linguist J.R. Firth would seem to agree with the possibility of "stand-alone" semantics: "You shall know a word by the company it keeps".

Taking five minutes to ponder the mysteries of language reminds me why I left Natural Language Processing, after a few brief forays. The problem is just too hard, and our current tools too primitive. I realized that until we develop more powerful mathematical tools, NLP research will be plagued by the sad fact that ad-hoc heuristic hacks tend to outperform elegant, clean, principled models. Of course, I am quite out of it as far as recent developments -- and would be happy if someone would set me straight. I know that elegant, principled models exist for document classification and text translation. I also know that if the state of the art is to be judged by Google's automatic translator, then there is, ahem, much room for improvement.

I prefer to be a producer of formal theorems and a consumer of NLP products (and judging by my list of rejected NLP paper submissions, my preference is in line with that of the community). Of course, no one can stop me from dabbling in language as a hobby, which I regularly do. Want the etymology of an obscure (but known!) Indo-European or Semitic root? Want a tip picking out a good dictionary? You've come to the right place. Regarding the latter: I can size up a dictionary in a matter of minutes, and my intuition has yet to mislead me. Always look up slang and, yes, vulgarities -- any lexicographer who pretends that certain words don't exist isn't worthy of the title. (Russian joke: "Мама, что такое жопа?" -- "Такого слова нет, сынок." -- "Странно -- жопа есть, а слова нет?..") Our final conclusion is that Russians have a joke for most occasions.

Kontorovich-Shalizi love-fest

2006-12-30T19:45:00.000-08:00

Since Cosma doesn't have comments enabled, I have no choice but to respond to his posts here! As always, he's far too kind to me, and since I also hold him in very high esteem, this could easily degenerate into the kind of echo chamber for which we even have a Russian saying: "За что кукушка хвалит петуха? За то, что он кукушку хвалит." [If anyone knows the English/Hebrew analogue, please let me know!]

On a tad more serious note, the statement "Leo and I regard each other's politics as unsound" is inaccurate -- at least in one direction. I actually find Cosma's politics to be rather reasonable -- refreshingly so, given some of the hair-raising monstrosities I've encountered in the pristine halls of academia. (No, you'll get nothing concrete out of me here -- I'll have to start a different blog, under a different name, to be able to repeat what I've heard come out of otherwise sane people's mouths.) The difference between politics and faith is that reasonable people can persuade each other through intellectual arguments, and recognize that there are issues where disagreement is perfectly acceptable. (Eating babies? No way. Gay marriage? Let's discuss.) I have no patience for people who confuse politics with religious faith, considering their opponents not simply mistaken, but truly evil. I've encountered my share of such folks (if your office door sports a poster equating Bush with Hitler, chances are, you're one of them). But I'm happy to report that Cosma is a well-read, erudite, easy-going fellow who it's been my pleasure to shoot the breeze with over beer and coffee. We may not agree on everything, but I wouldn't call his politics unsound.

What is math good for?

2006-12-30T09:28:00.000-08:00

This is a response to Aaron's post, as well as a chance to link to some of my stuff, buried deeply in the comments on other blogs. Every mathematician, at some point or other, is asked to justify his occupation. A common (and, I believe, sufficient) answer is that mathematics is ars artis gratia and requires no more justification than poetry or painting. Some mathematicians even take a (perverse) pride in claiming that their work has no practical applications whatsoever.

I consider myself an applied mathematician, and I take great pride and satisfaction in my work. My motivation to work on a problem is directly proportional to how useful people will find the result. Recently, Anthony Brockwell has been applying some of my rather theoretical results to the very practical and obviously important problem of decoding neural signals. Now, I never had this particular application in mind when proving the inequalities, but it was obvious to me that many people will find this stuff quite useful, and that certainly added to my motivation; it was very satisfying to see my work finding a use.

It's a common false dichotomy to distinguish "useless" math from "useful" engineering. I hate to repeat myself, so I refer the readers to the relevant discussion on Olivier's blog. If I may be forgiven the cliche: "There is nothing so practical as a good theory" -- so trite yet so true. I am opposed to snobbery between the different fields of human endeavor. I readily recognize the importance of bread-bakers, bridge-builders and code-crankers. Can we recognize, once and for all, that theoretical math is an important thing to study in and of itself? Need I remind you that the most basic tools in every engineer's chest (calculus, Fourier analysis) were once nothing but mathematical esoterica? Even that genteel queen of mathematics, number theory, has recently found herself rolling up her sleeves and taking her turn in the sordidly applied field of cryptography. Did Higman have any idea in 1952 that his result on partial orders would be used in 2005 to prove that a certain class of languages is linearly separable (and therefore learnable)?

Any way you approach math -- an intricate art, an indispensible tool, some combination of the two -- it unquestionably merits (nay, demands!) intense study.

FLAC project ideas

2006-12-29T19:09:00.000-08:00

This spring I'm TAing Formal Languages, Automata and Computation (FLAC), with Lenore Blum as instructor and Katrina Ligett as fellow TA. Since we like to get the undergraduates off to an early start in independent research, we are suggesting (well, requiring) that the students do a course project.

Below I am going to suggest some project ideas, based on problems that came up in my work. These range from "mathematical curiosities" to solid research problems to truly fundamental questions, probing the very foundations of computer science. I'll be adding to this list as time goes by, but here is a start.

In 2003, I proved that the so-called n-gram uniquely decodable languages are regular. In Sec. 4.4 I conjectured that an efficient automaton construction is possible. Recently, such a construction was indeed given. Project: Read and understand the two papers. Implement the automaton described by Li and Xie (in matlab, for example). Attempt to answer other questions I raise in Sec. 4 (I'd be particularly happy to resolve 4.1).
In a recent paper with Mehryar Mohri and Corinna Cortes, we present a novel approach to learning formal languages from labeled samples. Our technique consists of embedding the strings in a high-dimensional space and learning the language as a maximum-margin hyperplane. We prove that a rich family of languages (the piecewise testable ones) are linearly separable -- and therefore efficiently learnable -- under a certain efficiently computable embedding (kernel). One of the gaps we've been trying to close is a lower bound on the separating margin, in terms of the automaton complexity. All we can currently show is that it's strictly positive. Do not be daunted by the machine-learning concepts in this paper; I'll be happy to sit down with you and explain them all. A result of the type "margin is at least 1/poly(#states)" would be a very good thing, and would certainly make a solid, publishable paper.
A natural extension of the work with Corinna and Mehryar is the question of what other language families can be linearly separated. It turns out there is a universal kernel that separates all the regular languages! This is one of those results that sounds deep (indeed, it eluded us for something like a year) but becomes trivial once you see the construction. The key quantity is the following auxiliary kernel. Fix a finite alphabet Sigma of size m, and let DFA(m,n) be the set of all deterministic finite-state automata on n states over this m-letter alphabet. There is no loss of generality in assuming that every DFA always starts in state 1. Then size(DFA(m,n)) = n^(mn)*2^n -- do you see why? Suppose I give you two strings, x and y over Sigma, and ask: how many A in DFA(m,n) accept both x and y? Call this quantity K_n(x,y). It may not be immediately obvious, but K_n(x,y) is a kernel of fundamental importance, for it can be easily adapted to render all the regular languages linearly separable. Unfortunately, we do not have an efficient algorithm for computing K_n(x,y), and in fact suspect that it's a computationally hard problem (a likely candidate for #P complete). Proving that this is indeed the case would be a big deal; providing an efficient algorithm for computing K_n(x,y) would be an even bigger deal. (We do have an efficient epsilon-approximation to K_n(x,y).) Again, I'm leaving out many details and a writeup/talk slides are forthcoming. I can't overstate the importance of this problem (according to a really famous computer scientist who'll go unnamed, it's even more important than I realize!). I'd be thrilled if a brave soul would attempt it.

Update: Jan. 26 2007:

More project ideas:

Algebraic automata theory. A couple of students have expressed an interest in the deep and fascinating connection between automata, languages, and semigroups. I am going to mention a few places to start looking; there's plenty of material here for several projects (heck, for many PhD theses). (1) Check out the expository papers by J-E Pin and/or Mateescu & Salomaa (2) Take a look at the book Semirings, automata, languages by Kuich and Salomaa.
Algorithms on strings. Computations on strings are at the core of natural language processing and computational biology. Take a look at an influential paper on string kernels, check out Dan Gusfield's book, or the excellent book by Sankoff and Kruskal.

The way I envisioned for this to work is that you do some independent reading, come to me with specific questions/ideas, and we together decide on what a reasonable project might be. I have a strong preference for independent research over passive summarization, but exceptions can be made for particularly challenging material.

UPDATE: Feb. 1, 2007: If we spoke about meeting, please email me with the time! Also, try to have a concrete idea by the time we meet...

Learning Proof Techniques

2006-12-28T06:56:00.000-08:00

Something else that has been on my mind for many years now, that I think has impeded my mathematical development: the whole business of how to actually go about proving something. I feel that, and I am probably not alone in this, I was never really taught strategies for how to develop a proof. Sure, I was taught about some very general techniques: proof by contraction, induction, etc. But no one ever really sat me down said, how are we going to develop this proof. Obviously I was shown the proofs to all sorts of famous theorems and other homework problems. But they just showed us the proof after it was already concocted. But rarely the messy business of how we might have come up with proof. Never the false starts, the random walks, and sheer examples of genius that are required pull the whole thing together. Because, to me, the presentation of the completed proof in a nice linear story-telling manner is a complete distortion of the actual reality that went into creating it.

So, does any one know of any resources that actually address this issue? Am I alone in thinking that this is a real pedagogical problem in mathematics? Or am I just too aware of my own limitations in this area?

A Second (Occasional) Contributor

2006-12-28T06:20:00.000-08:00

Hello, from a second (occasional) contributor. Leo has seen fit to grant me posting rights as well, so I thought I would introduce myself. I won't make you read to the bottom of the article to find out who I am: I am Aaron Greenhouse. I'm not completely sure what role Leo has in mind for me here, but I think I am best seen here as the skeptical consumer of mathematical results. Let me clarify, by giving my background. I have a doctorate in Computer Science from Carnegie Mellon University. My dissertation was in the realm of applying program analysis techniques to software engineering. Specifically, analysis of Java programs for race conditions. I am now a Member of the Technical Staff at the Carnegie Mellon University Software Engineering Institute. I can post the details of my current work at a later point if anyone is interested.

I am not, nor do I pretend to be, a mathematician, although I do have a mathematical background of sorts. I have an undergraduate minor in mathematics from Brandeis University. This was a bit of accident. All I really wanted to do was to take a course on Complex Analysis. But to do that I needed to take the multi-variable calculus course. I had taken that in high school, so I figured I would take the advanced version of the course at university. I'm not sure that was a good idea, because the professor—even though he was the undergraduate program coordinator for the department—hadn't taught undergraduates in several years. He frequently had catastrophic subscript and other notational errors one hour into proofs. But I made it through the course.

At some point I realized the minor only required five classes, so I figured I would take the Algebra course to acquire the minor. Another mistake. The professor was a specialist in Algebraic Number Theory, so you can guess where all his examples where drawn from. This did not help my comprehension. I only took one semester of Algebra, and then rounded out my minor with a very interesting course on nonlinear dynamic analysis that didn't make my head hurt as much.

My mathematics in graduate school were focused on programming language semantics. I took two courses from John Reynolds and a course from Stephen Brookes. I feel comfortable reading just about any paper from POPL, ICFP, and related conferences. But I frequently have the feeling that there is some higher level of understanding just outside my grasp that I find very frustrating.

So let's return to my claim that I am the skeptical consumer of mathematical results. Basically, I am not interesting the beauty of the result for the sake of the beauty. I am interesting in what it can do for me as a practitioner. I am not so stubborn as to want practical results immediately, but I would like to be convinced in less technical speak of what is the potential of the result. I seem to have a certain level of mathematical abstraction beyond which I cannot grasp. (This is actually quite interesting because Software Engineering and Programming Languages are all about abstraction.) Here's my point more concretely. I can read the axioms and some basic theorems about, for example, algebraic groups. I can nod my head, and say to myself, yes I understand what they mean. But then on the next page the textbook makes some comment like "and we see that the following property trivially follows." Except that, to me, it isn't trivial. The author won't even bother to present the proof of the property because the author thinks it is so obvious, and I'm left scratching my head in wonder.

Any way, so to summarize: I have, what I believe to be, a more advanced than many mathematical education. But yet I have a clearly defined limit of where it will take me, even though I would like to understand the overall implications of certain advanced concepts so that I can apply them.

Blogging from the road

2006-12-26T11:52:00.000-08:00

I've always wanted to be able to say that (and I'm indeed at an airport, the third time in a row that Continental has a 2+ hr delay).

I thought I'd explain my solution to getting tex to appear on the web page. I know that many perfectly sound solutions exist -- just google latex2html -- but this old dog would rather stick to the tricks he knows (matlab and latex) rather than learn new ones. I wrote a matlab script, which takes a .tex file, turns commands of type \link{url}{description} into the href business and {\it bla} into bla (and so on). It also extracts every math formula in the file, creates a temporary .tex file containing just that formula and calls the perl script textogif. It outputs the html code with the links to the formula gifs.

Is this the prettiest or most efficient way of doing things? Hell, no. But a quirk in my character makes it much easier for me to invent a solution from scratch rather than use an existing one. It's been a boon and a curse in my research. Here's that matlab script in case anyone is curious; I'd be happy to hear comments, suggestions, etc.

A minor breakthrough

2006-12-24T21:07:00.000-08:00

It looks like I've figured out how to encorporate formulas into html: (many thanks to Arthur J. O'Dwyer and Jeff Grafton for their patient explanations).

Now, how do I get rid of that annoying border?

Update: border issue solved (thanks to Jeff & Peter Nelson). I can now blog with the big boys...

Update II: My list of benefactors now includes Adam Schloss -- thanks to everyone for helping me figure out how to do this. The LDP vs COM post has been redone, and is now readable!

Deep mathematics (vs. the other kind)

2006-12-24T03:05:00.000-08:00

Let me belatedly join in the fray on Scott's blog, revolving around what counts as "deep" math. The discussion at times degenerates into a micturition contest, as such things are liable to, but interesting points are certainly raised. First, I have to take Scott to task for the comment, "The theorems in real analysis all seemed like painstaking formalizations of the obvious". I don't know what material you covered in Real, but: quick, without consulting textbooks, notes or the web (1) does there exist an everywhere continuous and nowhere differentiable function f:R->R? (2) what if we add the additional restriction that f be monotone?

If the answers to these were obvious to you before taking Real, then it's a real shame you didn't pursue analysis as a specialty. The year I'd graduated with a math degree from Princeton, I still made the shameful blunder of convincing myself that I'd constructed a continuous, monotonic, nowhere differentiable function (fortunately, I recalled the Lebesgue-Radon-Nikodym theorem before I had a chance to really embarrass myself). The latter, btw, is an example of a Truly Deep (tm) theorem from undergrad analysis.

Of course, it's silly to debate the relative "depth" of different mathematical disciplines. I'll grant you that P?=NP occupies a central place because of its philosophical implications (and it's a real pleasure to read your expositions on these). But I tend to avoid mine-is-deeper-than-yours contests as they produce nothing useful and occasional animosity. A "deep" result is any claim that's surprising, nontrivial, and has rich implications. It need not be paticularly difficult (the Gelfand-Mazur theorem is plenty deeep, but has a 1-line proof).

The "two cultures" paper (linked by Elad Verbin) is certainly relevant here (on top of being an educational and enjoyable read). I've always found discrete math more difficult to reason about than continuous. What makes combinatorics so difficult is that "continuity of intuition" fails. Things often go wrong not because you mis-formulated some technical condition but because the "structure" of the problem is so difficult to grab hold of. The hardest things I've proved haven't been terribly technical -- indeed, the techniques I used were elementary. The key part has always been was understanding the elusive structure of the objects I was working with. Alexandre Borovik refers to these two types of thinking by "switches" and "flows" in his book. I'd like to read the cognitive explanation more closely sometime (and of course would be thrilled if someone would summarize it).

PS. Don't mind Conway's off-handed dismissal of The Central Question. When you have a group named after you, you can pretty much say anything at all.

Large deviations vs. measure concentration

2006-12-24T01:06:00.000-08:00

Lately I've been seeing two distinct phenomena conflated: Large Deviation Principles (LDP) and Concentration of Measure (COM). Good references on the LDP include Large Deviations by F. Den Hollander and Large Deviations Techniques and Applications by Dembo and Zeitouni. I also heartily recommend Cosma Shalizi's Lecture notes (lectures 30-35). To read up on COM, a good place to start is Gábor Lugosi's "Concentration-of-measure inequalities", or Ledoux's book for a more abstract, in-depth treatment.

Given the abundance of rigorous treatments of LDP and COM referenced above, I'll focus instead on the "intuitive flavor" of the two approaches. First, the similarities. Both LDP and COM allow one to prove Laws of Large Numbers (LLN). For our handwavy purposes, a LLN is any claim asserting the convergence (weak, almost sure, in probability) of a sequence of random variables to their common expected value.

Quoting Dembo and Zeitouni (p. 4):

The large deviation principle [...] characterizes the limiting
behavior, as , of a family of probability measures
on , in terms of a rate function.

Letting be the empirical mean of independent, one-dimensional standard Gaussian random variables, Dembo and Zeitouni give a simple calculation (1.1.3) showing that

which they summarize as

The "typical value" of is [...] of the order ,
but with small probability (of the order of ),
takes relatively large values.

Note that this result, on its own, does not tell you how large of a sample you need (i.e., how big to make ) to ensure, with probability
that .

To get such a finite sample guarantee (as opposed to an asymptotic limit), we need a COM result. As a slight technicality, let us truncate those Gaussians to the interval and renormalize (anyone who suspects foul play may be referred to Samuel Kutin's extension of McDiarmid's inequality). Then a simple application of Hoeffding's bound gives

Note that the asymptotics match those of the LDP, but we can guarantee that for any

with probability at least , the empirical mean will not deviate from the expected value by more than . Note, however, that we do not have a rate of convergence (in probability) of a random variable to its mean; all we have is an upper bound.

I hope these two examples illustrate the different flavor of the two apporaches. COM tends to give sharper upper bounds on deviation probabilities. These have the advantage of being true for all (excepting at most finitely many) values of , and the disadvantage of providing next to no information on the lower bounds. LDP gives the asymptotic rate of convergence (both upper and lower bounds), but does not (at least without some additional work) yield finite-sample bounds.

It is little wonder, then, that COM has found many more applications in computer science (e.g., randomized algorithms) and statistical machine learning, than LDP. The user wants to know how long to run your algorithm to achieve a specified precision at a given confidence level; order-of-magnitude information for "typical" values is usually insufficient.

Having given an informal "definition" of LDP, let me close with an equally informal discussion of COM, this time, quoting myself:

A common way of summarizing the phenomenon is to say that in a high-dimensional space, almost all of the probability is concentrated around any set whose measure is at least . Another way is to say that any "sufficiently continuous" function is tightly concentrated about its mean.

I realize this isn't terribly informative (or at all original), but the linked paper does attempt a crude survey (with an emphasis of passing from indepenent sequences to those with weak dependence). A word of caution for those attempting to visualize "measure concentration": imagining a narrowly peaked, one-dimensional distribution is tempting but wrong. This is a genuinely high-dimensional phenomenon. The only "visual" intuition I can offer is that the (Lesbegue) volume of the -dimensional Euclidean unit ball goes to zero with , while the volume of the cube (in which the ball is tightly inscribed) blows up exponentially. This means that in high dimensions, most a set's content is concentrated near its boundary -- something that's certainly not true in low dimensions. Anyone who's intrigued by this (that's everyone, right?) should read Milman's "Surprising geometric phenomena in high dimensional convexity theory".

The inaugural post

2006-12-22T21:56:00.000-08:00

The hardest thing about starting a blog is coming up with a good name. It has to be whimsical yet not cheesy, and somehow encapsulate the ethos of the blog. At first, I was discouraged by the thought that all the clever ones were taken. Then one day I managed to crank out a whole bunch of potential blog names (I won't say what they were-- wouldn't want to ruin the fun for other newcomers). Finally, I settled on what you see here.

An explanation is in order. The name is an amalgamation of two of my main research interests: stochastic processes and automata theory. "Absolutely regular" is a type of strong mixing condition, and I've done a bit of work on that. "Regular" is also the name of a fundamental class of formal languages (in a well-defined sense, it is the simplest nontrivial class of languages with natural closure properties). I have some results regarding these as well.

"Regularity" is one of those abused terms in math (cf. "space" and "kernel") that means everything and nothing. Roughly speaking, regularity is whatever conditions we need to impose to exclude the pathologies that prevent intuitive/desirable statements from being true. Mathematical analysis is full of instances where the naive claim is inaccurate or plain false (integration and differentiation are inverse operations) but becomes true once the right (usually, mild) conditions are imposed. In some sense, analysis is the study of such conditions. Regularity also crops up in more applied areas, such as statistical machine learning. No one can learn arbitrary functions -- there are simply too many of them. However, once a regularity condition is imposed (VC-dimension, Sobolev norm, Tsybakov noise condition, etc) -- learning becomes possible. In some sense, machine learning theory is the study of the regularity conditions that enable learning.

And finally, "absolutely regular" might just conjure up an image of a relaxed, easy-going everyday joe-shmoe blogging away in his pajamas.

I'll close with a mission statement. This is mainly a research blog. I'll post about problems I'm working on, current and past, and invite readers to join in. Recently, my work has been generating a slew of open problems, so if you're looking for a good problem to work on, you've come to the right place.

I'll resist the temptation to post about personal stuff because (1) my friends shouldn't have to read my blog to get an update (2) everyone else really has no business even being curious. I'll try to keep the politics near zero, but I see myself occasionally lapsing into a mini-rant (what blogger worth his salt doesn't? At least I'm honest and upfront about it).

Finally, I'm a novice at this "web-logging" on "the inter-net" so please do bear with me. I don't even know how to make formulas, such as $f:\mathcal{X}^n\to\mathbb{R}$ come out right. I'm glad that русский and עברית seem to work.