Andy's Math/CS page

Saturday, October 27, 2007

The Scientific Canon (I)

What is the scientific canon? A pantheon of immortal brilliance? A self-serving narrative of the dominant paradigm? A paean to dead white males?

Let me suggest a simpler, working definition: you know you've made it into the scientific canon when your name is writ large on the main building at MIT, stately-like, with any U's written as V's.

There's quite a procession of them, and I was struck by how many of their names were unknown to me. If I know at least half of the names in the latest Theory conference, shouldn't I also know who's made a lasting impression on science as a whole? Well, readers, here's part one of the list; how do you fare?

If anyone wants to chime in about interesting people on the list, please feel welcome. The names appear in blocks, as indicated, with certain key names especially large, and there is definitely some amount of thematic/historical grouping... what can you observe? There's a slight possibility some names are misspelled, since a few were well-hidden by tall trees.

Finally, I should note that some of these people might not, strictly speaking, be considered scientists. But, I've set my criterion--they're up on the wall, so into the canon they go.





















Monday, October 22, 2007

More Wordplay

Call a word 'orderly' if its letters are in alphabetical or reverse-alphabetical order. Consecutive appearances of the same letter is OK.

-Find a famous mathematician whose name is orderly.

-Now find a complexity theorist.

-How long an orderly word can you find?

-Have any other challenges for the rest of us? A CS research problem related to orderliness?

In a different but still-wordy vein, Free Rice is a fun site, where you donate rice to the UN by testing your vocabulary. The words get impressively obscure as you score more correct (multiple-choice) guesses, much more so than, e.g. the also-recommended Word of the Day page, and once you're arguing with friends about what 'carronade' means it's a good bet that you're not fighting poverty in the most effective way possible, but I still recommend it. What this quiz underscores for me is how much verbal knowledge we hold at the very edge of awareness and competence. (Hat tip to Chaya for the link.)


Friday, October 19, 2007

Space is a Lonely Place

Puzzle time again--this time a dressed-up version of a problem in Claude George's book 'Exercises in Integration'--not as boring as it might sound!

The year is 2100. SETI, having failed to make contact with any extraterrestrials, is facing termination. They haven't lost faith, but everyone else on Earth is pretty tired of them, so they decide to spend their remaining budget by blasting themselves off into space--a reconnaissance mission of no return.

The SETI folks are interested in coming near as many potentially-inhabited star systems as possible. They've watched 'Biodome' a few times, and they're pretty sure they can get their spaceship to support human life indefinitely. But fuel is limited to their blast-off needs, so they have to plan on following a straight-line path at constant velocity thru space (which is 3-dimensional, or 2 if you like, Euclidean, and devoid of gravity or other impedances--stars can be passed thru, e.g.).

A star-system is defined as the billion miles surrounding a star, within which SETI figures they'll have a good shot at communication with any planets in the system. In the first version of the problem, they also assume, somewhat optimistically, that candidate stars do not move and that candidate star-systems occupy a nonzero asymptotic fraction of the universe's volume. E.g., for any N, if we draw a ball of radius N around the Earth, at least .001 of its volume lies in some candidate star system.

Here's SETI making contact with 3 star systems:

Problem 1: Can the crew plot a straight-line course that will put them in contact with infinitely many candidate star-systems?

Problem 2: What if their navigation equipment forces their initial bearing to be a rational angle?

Problem 3: There's all sorts of potential crazy variants: do the stars move? How fast? Adaptively or non-adaptively? But I've already wasted enough time on this problem, so dear readers, I leave it to you.

Wednesday, October 10, 2007

Is This Right? Is This Legal?

This post may not approach the heights of quandary Scott has been facing lately, but I think it's worth discussing.

I typed in 'Computational Complexity' on to get the reference info for Christos H. Papadimitriou's textbook of the same name. Here's what I got instead.

It's a 'Cram101' production, an outline of Papadimitriou's textbook. His last name appears on the cover, but not his first name or classy middle initial, suggesting he had nothing to do with it.

So, is this right? Does such an outline contribute enough to warrant its own copyright, or does it infringe on Papadimitriou's?

One might argue from the precedent of 'Cliffs Notes' for novels, but there are some obvious differences. Cliffs Notes summarize, but do not reproduce, the artistry or enjoyability of novels, whereas cram101 presumably makes a direct substitution: their skimpier expository writing, modeled directly on Papadimitriou's careful exposition. Cliffs Notes add a modicum of clarification, criticism, thematic discussion, etc., whereas it's not clear what if anything Cram101 adds (please note that I haven't looked inside, and am prepared to reconsider the issue if the publisher or anyone else wants to show me the book).

I have heard it expressed that Papadimitriou's book is hard reading, but there are other, more elementary textbooks out there
covering much of the same content. The things in the text that are not in most TOC books (extensive logic and some necessarily hard advanced topics like Razborov's Theorem) are probably not going to be tested heavily in class, other than familiarity with the theorem statements--and you can get that easily enough from the textbook.

So I'm guessing the motivation and main selling point for this book is its much lower price compared to the original text. I can sympathize--I spent more than a semester ducking into Cody's Books to read from 'Computational Complexity''s sumptuous, glossy pages before my parents bought it for me as a high-school graduation present. Expensive textbooks (and journals) hurt science just as they hurt the college students who are forced to buy them, and outlines like Cram101's are a by-product. (Let me add that a) I don't blame Christos for his book's price, b) it was for me a life-changing book, worth its price many times over and still one of my favorite books.)

Still, Cram101's costs are low partly because they are free-riding on Christos' considerable labors. Is a discussion of the larger academic publishing industry really necessary in this case? Again I ask--is this right?

As an independent point, I think amazon's presentation of the product is slightly duplicitous: though it does point out this is not
the textbook, it lists 'Papadimitriou' as the author, and it gives reviews of the textbook in place of reviews of the outline. Also, Christos' book comes up much lower in the search results.

Update 12/02: After being alerted to the Cram101 phenomenon, Christos said he'd see what he could do about it. Now I see that some changes have been made on the amazon page:

i) Papadimitriou is no longer linked to as the author;

ii) The title header has been changed--now it is prefaced as 'Outlines & Highlights for' C.C.;

iii) It now comes up below Papadimitriou's book in searches (though this may have more to do with sales-rank than intentional policy).

These are all positive steps. On the other hand, one still might wish that

i) Comments on Papadimitriou's book weren't displayed with this one, as they still are;

ii) amazon would have the sense to stop selling a book that is not only of questionable legality, but that multiple readers have characterized as a scam that doesn't even deliver the plagiarized content it promises. At the very least they could comment on their decision to sell it, offer customers a look inside this book, etc.

Tuesday, October 09, 2007

Random Freaky Facts

While it may not be at all apparent, I've been somewhat particular about the types of posts I make to this blog. I've realized, however, that there should be no real harm in loosening up, and it'd probably increase my post frequency. So today, let me report two theorems that caught my eye in recent weeks. If I had to find a common theme, it'd be: finding interesting constraints in seemingly very unconstrained settings.

1) Let G be an infinite (undirected, simple) graph. Let the 'density' d(H) of a finite subgraph H of G be the fraction of pairs of vertices (u, v) from H that are connected by an edge. Let the 'upper density' d*(G) of G be the greatest number p such that we can find arbitrarily large finite subgraphs H, with d(H) as close as desired to p.

(i.e. for all n, epsilon there exists an H with |H| > n, d(H) > p - epsilon.)

Then, bizarrely, d*(H) must be one of the following numbers: {0, 1, 1/2, 2/3, 3/4, 4/5, 5/6, ...}

This result follows from the 'Erdos-Stone Structure Theory', generalizing Turan's Theorem in extremal graph theory. It is presented, in context, in Bollobas' excellent textbook 'Modern Graph Theory'. Basically, the idea is that, if H is large enough and of density greater than, e.g., 5/6 + epsilon, it must contain a particular subgraph H', of density 6/7.

2) Let X be a probability distribution over R^d. Choose d+1 points independently, each distributed as X. Then the probability p that their convex hull contains the origin, cannot exceed (1/2)^d.


Unfortunately, I forget where I saw this last one, or who it's due to, but if I find out I'll attribute it here. I'm, uh, 90% sure I've got the numbers in the statement correct.


Friday, October 05, 2007

Another Heads-Up for Puzzlers

Two puzzle collections (both drawing on diverse sources) caught my eye recently. The first is 'The Art of Mathematics: Coffee Time in Memphis', by the famous mathematician Bela Bollobas. It's got a number of gems, for instance: is it possible to 'load' two dice, i.e. skew their faces' probabilities, possibly in distinct ways, such that when both are rolled the resulting distribution is uniform on {2, 3, ... 11, 12}?
The book is definitely worth looking at, but, perhaps as a function of its ambition to teach some important (and cool) math along the way, it is rather difficult on the whole, and ridiculously so in some cases (one of his 'puzzles' is to disprove the Borsuk conjecture, a problem that had been open for something like 60 years. Granted, there is a hints section, but come on...). The Amazon page lets you browse a number of the more approachable puzzles, so check it out.

The second is 'Mathematical Mind-Benders', Peter Winkler's much-anticipated sequel to the instant classic 'Mathematical Puzzles: A Connoisseur's Collection'. I haven't spent enough time on the new one to see how it stacks up to its predecessor, but it definitely contains some beguiling problems. Many are 'old friends' of the puzzle genre (bugs, prisoners, hats, etc.), but remade and fiendishly harder--think of the fight with Super Shredder at the end of 'Turtles II'...

However, while Winkler's books are also quite hard, they generally involve much less 'higher math' than Bollobas', which is really written for readers interested in mathematics proper. Another emphasis of Winkler's new book is on surprise answers, as in the following two puzzles from the first, warm-up chapter:

-A pencil has a regular pentagon as its cross-section, and its maker's logo on one face. If the pencil is rolled on a table, what is the probability that it comes to rest with the logo facing up?

-You have 15 bags. How many marbles do you need to produce an arrangement where each bag contains a different number of marbles?

Winkler also unveils a neat word puzzle called 'the HIPE game', something he co-invented as a teenager. One player comes up with a string of letters and challenges the other players to find a word containing it (as a block of adjacent letters): for instance, can you place HIPE in a word? Of course, the problem poser should actually have a word in mind...

Some other challenges he gives: BG, CM, FC, FW... and the book has many more (and harder). I'm normally pretty decent at word games, but this one is killing me so far.

Thanks, Bollobas and Winkler!