Toluu

Andy's Math/CS page

Sporadic notes on mathematical and non-mathematical topics, from a student of computational complexity.

A Rather Elegant SolutionDecember 3 2008

So I'm co-writing a survey paper for a course project, and struggling with the conflicting demands of completeness and brevity. As if charmed, while taking a break I happen upon a '99 paper called "50 years of Bailey's Lemma" by S. Warnaar whose abstract really resonates:

"Half a century ago, The Proceedings of the London Mathematical Society published W. N. Bailey’s influential paper Identities of the Rogers–Ramanujan type... To celebrate the occasion of the lemma’s fiftieth birthday we present a history of Bailey’s lemma in 5 chapters...
Due to size limitations of this paper the higher rank [42, 40, 43, 41, 14, 60] and trinomial [11, 59, 19] generalizations of the Bailey lemma will be treated at the lemma’s centennial in 2049."

Excitement and ProbabilityOctober 31 2008

Elections, sporting events, and other competitions can be exciting. But there is also a sense in which they are almost always dull, and this can be proved rigorously. Allow me to explain.

(What follows is an idea I hatched at UCSD and described to Russell Impagliazzo, who had, it turned out, discovered it earlier with some collaborators, for very different reasons. I wouldn't be surprised if it had been observed by others as well. The proof given here is similar to my original one, but closer to the more elegant one Russell showed me, and I'll cite the paper when I find it.)

I want to suggest that a competition is dull to watch if one side is always heavily favored to win (regardless of whether it's the side we support), or if the two sides muddle along in a dead heat until some single deciding event happens. More generally, I'd like to suggest that excitement occurs only when there is a shift in our subjective probabilities of the two (let's say just two) outcomes.

Without defending this suggestion, I'll build a model around it. If anyone is upset that this notion of excitement doesn't include the smell of popcorn, the seventh-inning stretch, or any substantive modelling of the competition itself, there's no need to read any further.

Assume we are a rational Bayesian spectator watching a competition unfold, and that we receive a regular, discrete sequence of update information X_1, X_2, ... X_n about a competition (these upd

NO on Prop 8October 24 2008

If you are straight, would you join a club that disallowed gay people? Or keep your membership in a club that stopped admitting them? Would you feel distinguished by your membership? To the contrary, I think most people would feel embarrassed and cheapened by it.

That's why everyone who is or hopes to get married in California (or anywhere, really) should feel alarmed about Proposition 8, why everyone whose tax dollars fund the Marriage Club should feel affronted by this attempt to make it an exclusionary one (by amending the state constitution). Even though we also fund the similar and inclusive Civil-Union Club next door (at least, until the next wacky voter initiative comes along), who can ignore the fence-builders' zeal for insisting on this petty distinction for heterosexual couples, or fail to grasp its underlying message?

Nothing in the existing laws force clergy of any religion to give ceremonies or `recognize' marriages they don't accept. There remains, in fact, plenty of space in private life to speak and practice intolerance, but we can't let it be done in the name of all Californians.

For thoughtful posts on the subject, see e.g. Luca's, Ben Casnocha's, and the No on Prop 8

David Foster WallaceSeptember 14 2008

About a week ago, at great risk to my studies, I gave in to temptation and checked out 'Infinite Jest' from the library. Last night, ~300 pages into rereading this wonderful novel, I learned that David Foster Wallace, its author, has died in an apparent suicide.

I never met DFW, and know little about his personal life--probably as he wished it--although he seems to have been widely regarded as a kind and generous person. I also never connected too closely with his short fiction and journalistic writing, although I read most of it eagerly. My relationship to DFW centered on `Infinite Jest' (1996), an immense book that captivated me when I discovered it in high school.

Briefly, IJ consists of about 1000 pages of chronologically free-form and narratively heterogeneous episodes from the lives of several characters, generally connected either to the Enfield Tennis Academy of metro Boston or to the nearby Ennet House, a drug rehabilitation center. It is supplemented with ~200 pages of footnotes--a generous helping of asides, extra scenes, and background info (it's set in the slight future, culminating around 2008, better known as the Year of the Depend Adult Undergarment in the era of Subsidised Time).

IJ is at once:

-a lush entertainment, addictive in ways I can't fully explain;

-a barrage of observatio

Heh...July 10 2008

Funny web comic touching on complexity theory.

From Request Comics. Handed across the room by Madhu to Brendan, who showed it to me.

Earlier I'd seen another, slightly more reverent, comics treatment of Interactive Proofs, by Larry Gonick of 'Cartoon History of the Universe' fame.


To briefly discuss the Request Comics scenario: suppose an alien claims to play perfect chess (in all positions) on an n-by-n board; is it possible to efficiently test this in a poly(n)-length randomized interaction?

If there's only one alien, this might be too hard, since the 'correct' generalization of Chess is EXPTIME-complete. If we instead play a PSPACE-complete game like Hex (or Chess with a truncated game length of poly(n)), things change: Shamir's Theorem tells us how a Verifier can be convinced that any particular board set-up is a win.

But this is not the same as Prover convincing Verifier that Prover plays perfectly! However, additional ideas can help. Feigenbaum and Fortnow showed that every PSPACE-complete language L has a worst-case-to-average case reduction to some sampleable distribution D on instances.

This means there exists a randomized algorithm A^B using a black-box subroutine B, such that