## Monday, February 12, 2007



Bill Gasarch guest blogging for Lance Fortnow

Jane: What you you been working on?

Bill: I've come up with an elementary proof of the
Gen. Multidim Poly van der Warden's theorem.

Jane: Is it new? Is it publishable? Does it have applications?

Bill: Its not new- People in the field already know this.

Jane: How many people are in the field.

Bill: Lets not go there. However, not new, not publishable as original research,
and no applications that I know of.  I got a guest post in Luca's Blog about it,
but that does not count for anything (should it?).
Anyway, here is a nice (known) corollary:

For any 2-coloring of the lattice points of the plane there exists d\in N
and a d by d^2 rectangle where all four corners are the same color.

Jane: Why did you spend time reading something with no hope for original research?

Bill: Jane, you ignorant ... (lets not go there either).

People don't watch Shakespeare plays for the sole purpose of getting
a paper out on them. Except English Professors.

2) Reading math or CS stuff that interests you is one way to find open
problems and new angles on things. So this is good in the long term.

3) Just because I did not plan to publish based on it does not mean that I won't.
By reading up on Ramsey Theory I have gotten out two papers, ideas for a third,
several (non publishable) ugrad and highs school projects, and a problem for the

Jane: Do you always talk in lists?

Bill: Only in fictional conversations.

Is it valuable to read math of interest to you with no particular plan for application?
Clearly Yes.
But the real question is, compared to what?
Compared to reading articles more directed towards a particular problem?
Compared to working on Math Olympiad problems?
Compared to sitting and thinking?
Compared to browsing porn on the web?
The answers vary from person to person.
However, my sense is that reading for pure interest is underrated.



1. “I was very curious about this theorem. That is reason enough. People don't watch Shakespeare plays for the sole purpose of getting a paper out on them. Except English Professors.”

It is also true that people don’t get paid watch Shakespeare plays, except English Professors.

I think you missed the most obvious point (perhaps to obvious to mention). If you do find a more elementary proof, it will help others better understand the area to. And helping people understand stuff is what we get paid for.

2. what was your last published result and when was it released ?

3. Responses:
1) YES, easier proofs do help the
community. The proofs I am looking
at are not really new, they ARE out there---
sortof. But YES, I do plan to write
them up. Not sure where to publish since
not new.

2) THANK YOU second commenter for indirectly
reminding me that my website resume is
out of date. I have fixed that, though
my links to papers is still out of date.
My last published result was MULTIPARTY
COMM COMPLEXITY OF THE EXACT T problem
in MFCS with Beigel and Glenn.
(2006). It DID use the Ramsey Theory
stuff I had read. Also FINDING LARGE 3 FREE SETS: AN EMPIRICAL STUDY
with Glenn and Kruskal
has been accepted by JCSS and I am putting
the final touches on it now. It ALSO
stuff too- see resume.)

4. As luck would have it I will be away at a confence when you give the talk at Iowa State March 26 :(

5. Unrelated question:

Graduate school decisions are coming out now. How should a theory undergrad decide which school to attend?

6. There was a discussion of that issue on this blog a while ago.

My somewhat cynical opinion: If you are admitted to, say, all the top 4 schools, then use comments on the post above to pick and choose. Otherwise, go to the highest ranked school you are admitted to. It will make your life easier in many ways.

7. Re. the question about choosing a grad school: as always,there are several dimensions to this, just wanted to chime in with one that I think is very important: go to a school where your education can be as broad as possible -- say you wish to do a PhD in complexity theory, pick a school where you'll learn a lot about algorithms, optimization, game theory, etc., and quite a bit about the rest of CS. The variety of ideas you will be exposed to is a very valuable asset, don't overlook that.

8. If your goal is an academic position, I'll second what anonymous #6 said. If you don't go to a top 5 school, getting an academic position becomes exponentially harder. (This is unfair, but that is life.)

9. I would say a huge factor in your decision is to pick a school where you would be happy (more important than the "quality" of the institution to some extent, I'd say). If you like city life, don't go to a rural campus, and vice versa. Try to go somewhere where the other grad students seem happy and are social (I went to a couple of schools for my visit days where the grad students seemed pretty miserable... definitely a turn-off). The culture of a department is very important (go to all your visit days and be sure to talk to as many grad students as possible!)

Whatever you do, don't go to the "highest ranked school" just because it's the highest ranked school. The quality of your work will speak for your abilities, not the institution you attend. And the quality of your work will definitely suffer if you attend a school that you hate.

-C

10. If you don't go to a top 5 school, getting an academic position becomes exponentially harder.

Exponentially harder is overstating it: "the difficulty goes up by a polynomial factor in time and space" would be more accurate.

don't go to the "highest ranked school" just because it's the highest ranked school.

Particulary be wary of places with great trailing reputations. A place that was top notch 15 years ago might have fallen in hard times, yet it takes quite a while for other people to take notice. You may end up accepting an offer from place X because everybody knows they have a great group in area Y and lo and behold all the big names have retired (or are about to), their replacements (if there are any) aren't half as good as the old timers and the whole group is drifting, resourceless and without a sense of direction.

11. The comment about "top 5 department" is particularly untrue about Theory.
Razborov did not go to a top 5 US department. Harvard is not a "top 5" CS department, yet their best Theory students do not have trouble getting interviews.

Theoreticians can and do read theorems, and they speak for themselves.

12. Razborov went to grad school in Russia, so using him as a data point says nothing.

Which theory students from Harvard are you talking about?

All you need to do is look at theorists hired by the top 25 schools in the past 3 years, and then look at how many got their PhDs at MIT/Stanford/Berkeley/Princeton/Cornell and how many got their PhD from another US institution.

What's amazing to me is how poorly theorists from other good schools (say, Georgia Tech) do in comparison to theorists from the top 5.

13. 1. USING SASHA RAZBOROV AS AN EXAMPLE FOR ENCOURAGING RECENT PHDS IS PROFESSIONAL NEGLIGENCE. SASHA IS HIGHLY ATYPICAL.

2. ANON #12 LEFT CARNEGIE MELLON OFF FROM THE LIST. I AM PRETTY SURE THAT ADAM KALAI WORKS AT GEORGIA TECH NOW AND HE DID HIS PHD AT CARNEGIE MELLON.

3. THE PRIMARY SET-BACK FOR GRADUATES FROM "NON TOP 5" GRADUATE SCHOOLS IS THAT THEY DON'T HAVE A DEGREE THAT WILL OPEN DOORS AND SERVE AS A TIE-BREAKER. TOP 5 SCHOOLS GRADUATE NUMEROUS "GREAT BUT NON TOP 5" THEORISTS EACH YEAR, AND THESE PEOPLE ARE LIKELY TO GET THE BENEFIT OF THE DOUBT MORE THAN COMPARABLE APPLICANTS FROM "GREAT BUT NON TOP 5" SCHOOLS

14. Not only is Adam Kalai at GAtech, so is Santosh Vempala, another CMU theory grad. And Shuchi Chawla at Wiconsin...

15. All you need to do is look at theorists hired by the top 25 schools in the past 3 years, and then look at how many got their PhDs at MIT/Stanford/Berkeley/Princeton/Cornell and how many got their PhD from another US institution.

That alone proves nothing. If the best students majoritarily attend the best schools, guess what? when it comes hiring times the best candidates are from those schools.

For the figures to prove something you need to give us a list of names of really bright graduates publishing scads of STOC/FOCS/SODA papers a year who didn't get a job offer at the top schools.

16. This alone proves nothing...
but it's useful information, because you can then focus on the exceptions in order to find out which schools, through high quality education and training, add the most value to a student. For example R.Ravi, currently at CMU, got his PhD at Brown...

17. I DO get paid to watch shakespeare plays, and my degree is in engineering. I have a side job writng theater reviews for a local paper. I get \$57 for 250 words, plus tickets.