Computational Complexity

Saturday, February 12, 2005

 
Just Say No

I have one word of advice that applies especially to junior faculty: No.

You will be asked to referee papers, look at graduate applications, look a faculty applications, write reports and recommendation letters. You will be asked to sit on committees: curriculum committees, space committees, program committee, web page committees, budget committees, planning committees and other committees you would never have imagined. You'll have committee meetings at the departmental, divisional and university levels as well as committees to serve the broader theory community. You will be asked to organize workshops, conferences and edit special issues. You'll also be teaching, writing grants and going to faculty meetings.

All of the above are good things to do. But do all of the above and you'll never get tenure. You need time for research. So learn to limit yourself, learn to say "no". I'm not saying not to do any of the above. Most of these tasks have to get done; you should do your fair share and be a "good citizen". But you don't need to agree to every request, feel free to turn down requests when you feel yourself getting overloaded. If you gain a reputation as someone who can't say "no" people will take advantage of you. And don't fall for the "You are the only one who can do a good job" ploy.

If you try to do too much you won't do anything particularly well. I would much rather have someone say "no" to me than saying "yes" and doing a mediocre job.

7:22 AM #   

Thursday, February 10, 2005

 
Favorite Theorems: The Seminal Paper

Introduction

We should start off off my list of favorite theorems from the first decade of complexity with the seminal paper in complexity, the one that gives the field and this weblog its names.

Juris Hartmanis and Richard Stearns, On the Computational Complexity of Algorithms. Transactions of the American Mathematical Society, 177 (1965), 285-306.

This paper formalizes the idea that we now all take as obvious that we should use Turing machines to determine complexity of complexity by measuring time as a function of the size of the input. Ever since the Hartmanis-Stearns paper we measure nearly every resource (time, space, random bits, circuit depth, etc.) as a function of the input size.

This paper also gives the first hierarchy of classes, showing that for nice functions t and u with t²(n)=o(u(n)) then there are problems solvable in time u(n) but not time t(n) on multitape Turing machines. Soon later Hennie and Stearns showed the same result if t(n) log t(n) = o(u(n)).

1:58 PM #   

Wednesday, February 09, 2005

 
Maybe He Missed Some Math

Thomas Garrity's book All the Mathematics You Missed [But Need to Know for Graduate School] has a section on P versus NP which says

The N in NP is somewhat of a joke; NP stands for "not polynomial".

and later

While initially the smart money was on P ≠ NP, today increasingly the belief is that the statement P=NP is independent of the other axioms of mathematics. Few believe P=NP.

For the record NP stands for "Nondeterministic Polynomial-Time" (not a joke) and at least this complexity theorist feels that a proof of P≠NP exists and we just haven't found it yet. Just because we are too stupid to find the proof doesn't mean the problem is independent.

I don't mean to be hard on Garrity. He should be lauded for including the P versus NP problem in his book.

Thanks to Varsha Dani for the pointer.

4:40 PM #   

Tuesday, February 08, 2005

 
Guest Post on Numb3rs P vs NP Episode

Suresh has been doing a fine job reviewing the Numb3rs episodes. Nevertheless Bill Gasarch wanted to write a guest post on the P versus NP episode which was the second episode broadcast and not the fourth as I had previously mentioned. But first my comment to Charlie: Don't let your brother mess up your priorities. Go back to solving P versus NP. So what if a few bank robbers get away?

Now on to Bill's Guest Post:

REVIEW OF SECOND EPISODE OF NUMB3RS USE OF P vs NP.

This is the `P vs NP' episode.

"Are you still working on that P vs P thing"

"Its the P vs NP thing"

They mentioned P vs NP ALOT of times.

PROS: ANY mention of our favorite problem on TV is good. This may be the first mention of P vs NP on an entertainment show since Homer Simpson fell into the third dimension where there were all kinds of equations floating around in the background including P = NP.

CONS: Wasted Opportunity. They made NO attempt to explain the problem. Could they have? Trying to color a map with 3 colors might be the problem easiest to explain. Or TSP. Might be hard to tie that to a crime, but minesweeper is also contrived. For that matter, could they have explained minesweeper better, and add something like "One way to solve it is to look at all possibilities. Even with really powerful computers, that could take to long. We want to know, is there a faster way?" I would not even try to explain NP or `checkability' I would just say that here are problems we can solve by looking at all possibilities, and we want to know if we can do substantially better.

ODD POINT: They mentioned a few times that it was `unsolvable' What did they mean? Options-

1. Charlie was trying to prove P=NP and this is unlikely to be true
2. Charlie was using techniques from recursion theory that likely to not work because of the oracles. (the what?)
3. Charlie was using proofs that naturalize, which won't work because of the results of Razborov and Rudich (Judd Hirsch: So use unnatural techniques)
4. The problem is independent of PA
5. The problem is independent of ZFC
6. The problem is just very very hard.

Likely they meant 1 or 6 (SARCASM ALERT: 2-5 were not meant to be taken seriously). But they should have spoken more clearly about this.

PRO: They do (in general, not just this episode) show Math in a good light and show Mathematicians in a good light.

PREDICTION: Will be canceled within 1.5 years. Don't need Charlie's math to predict that.

1:29 PM #   

Monday, February 07, 2005

 
The Super Bowl Parties

My old apartment-mate Eric Schwabe came over to watch the game last night and brought along old posters he had from the Super Bowl parties we used to throw as grad students at MIT. The Lance Fortnow Super Bowl Party continued at MIT after I left with a much larger crowd in my absence. A few years later it morphed into the Who the Hell is Lance Fortnow Super Bowl Party. Around this time (about 1992) an MIT student was excited to meet me at STOC not because of any research I had done but because he had been to "my" party. Eventually even the memory of the memory of me faded away and so did the party.

What happens now? We invited a few friends over for the game, every single one of which left early to put their respective kids to bed.

7:33 AM #   

Archives