Computational Complexity

Sunday, February 27, 2005

 
Are we the university?

Posted by Lance

Two fellow (and slightly better known) Chicago professors Gary Becker and Richard Posner run a joint weblog on various social issues. This week they tackle the question of whether the faculty "own" a university. Becker says yes and Posner says no. I have to go with no. I believe the board of trustees acts as the owners on behalf of the "shareholders" known as alumni. Many professor do act for the betterment of the university but professors come and go are no more owners than players on a baseball team.

Another question that comes up in discussions is who are the university's customers? Some possible answers:

• Students. But why is their success based on their performance?
• The Government who give the grants for research.
• The employers of the students.
• Society at large.

Perhaps the mistake is in making the analogy between university and corporation.

10:57 PM #

Friday, February 25, 2005

 
New Horizons in Japan

Posted by Lance

I'm off to Japan for a Workshop on New Horizons in Computing that kicks off a new theory project sponsored by the Japanese Ministry of Education. This will be my first time in Kyoto and my first trip to Japan since I was stranded there after September 11. Let's hope history doesn't repeat itself.

I'll be talking about my favorite theorems of the past decade but you, my loyal weblog readers, have seen it here first.

7:02 AM #

Wednesday, February 23, 2005

 
Ramanujan's Lost Notebook

Posted by Lance

Below the paid ads, Gmail gives me related links on the side of my email. In a discussion on a bad P ≠ NP proof (don't ask) Gmail pointed to this interesting article on Ramanujan's lost notebook.

Now only if we could find Gödel's lost notebooks on P versus NP…

8:22 PM #

Tuesday, February 22, 2005

 
The Complexity of the Nash Equilibrium

Posted by Lance

We know only a few natural problems in NP that are not known to be NP-complete or in P. The two most often named are factoring and graph isomorphism. Another that has come to forefront is Nash Equilibrium.

Given two n x m matrices A and B, consider the game where simultaneously player I picks a row i and player II picks a column j. Player I's payoff is A(i,j) and player II's payoff is B(i,j).

Nash proved that for all A and B there are probability distributions σ on the rows and τ on the columns so that if the player I plays according to σ and player II plays according to τ

1. There is no i such that if player I chooses row i his expected payoff will increase with player II still playing according to τ.
2. There is no j such that if player II chooses column j her expected payoff will increase with player I still playing according to σ.

The computational problem is to find σ and τ given A and B. It's a major open question whether a polynomial-time algorithm exists.

Using linear programming we can find Nash Equilibrium in a zero-sum game (A(i,j)=-B(i,j) for all i,j) or if we know the set of i where σ(i)=0 and the j where τ(j)=0.

We can also find a correlated equilibrium in polynomial-time which is a distribution on pairs (i,j). However to implement a correlated equilibrium you need either a third trusted party or use some cryptographic techniques.

I don't know a good survey on the complexity of Nash Equilibrium but perhaps my readers will have some good references.

7:13 AM #

Saturday, February 19, 2005

 
Factoring NUMB3RS

Posted by Lance

Scott Aaronson weighs in on last night's NUMB3RS episode "Prime Suspect". Mild Spoiler Warning.

Last night's NUMB3RS again centered around complexity. A brilliant mathematician (not Charlie) tells his friends that he's on the verge of proving the Riemann hypothesis -- and not only that, but his proof will somehow yield a fast factoring algorithm. When the bad guys get wind of this, they kidnap the mathematician's six-year-old daughter, demanding the algorithm as ransom. But the mathematician refuses to cooperate with the FBI investigation of the kidnapping. The reason, we later learn, is that the mathematician has fooled himself: he doesn't have a proof or an algorithm, and he's terrified the bad guys will find out. (One thing that has to be said for NUMB3RS: in contrast to, say, Good Will Hunting, it does get across the idea that math problems are hard.) So Charlie has the improbable task of helping the other mathematician fake a factoring algorithm -- apparently, the bad guys won't be savvy enough to run whatever they get on a few random instances!

In a way, this episode represents a retreat from the premise that "math helps us solve crimes" -- I mean, no duh it helps, if the crimes in question happen to involve polynomial-time factoring algorithms! But in my opinion, the fact that math was actually integral to the plot helped to make this the most effective episode so far. In contrast to the P versus NP episode, this time they actually explained a little about prime numbers, RSA, and factoring, and did a fairly non-egregious job by TV standards. Admittedly, an RH proof leading to a factoring algorithm seems pretty farfetched, but what path to efficient factoring isn't farfetched? (Other than building a quantum computer, of course.)

My main criticism is that, whenever Charlie and the other academics open their mouths, I feel like I'm listening to foreigners speaking perfectly grammatical sentences that no native speaker would ever utter. The phrasing is just too pretentious -- a trivial example being that everyone calls the Riemann hypothesis "Riemann's hypothesis." If they wanted to, the writers could easily fix this problem by reading the scripts to mathematicians, and seeing which lines pass the cringe test.

6:14 AM #

Friday, February 18, 2005

 
Computer Science Recruiting

Posted by Lance

I've already heard from several graduating students who have had few or no interviews scheduled and are really worried about finding a job next year. Don't panic yet.

CS recruiting is not a well coordinated affair running from January to June and often beyond. Each department determines their needs and resources and invites candidates for interviews, makes some of them offers and makes later interviews and offers as the first offers are turned down or as resources change, like a current faculty member decides to go somewhere else.

What does this mean? There is a small set of top candidates that get most of the interviews and initial offers. Some of these candidates can tie up offers for months because they are waiting for some other university to decide or they are simply indecisive and no one puts pressure on them to decide.

For students not in this top group they will get few or no early interviews and feel like they will never get a job. The market will shake itself out and dig deeper into the applicant pool. Departments that have theory as a secondary priority will realize they can't find good candidates in their top priority and start looking at theory candidates. In short the recruiting is game is just beginning.

Meanwhile broaden your search and look at places you may not have considered before. Work on your job talk even before you have anything scheduled and give a practice talk in your department. But mostly keep busy and get your mind off the job market. I found working hard on the thesis helps.

8:27 AM #

Thursday, February 17, 2005

 
Complexity Accepts

Posted by Lance

For this weblog it's the Super Bowl, the Grammys and the Oscars all rolled into one: Announcing the accepted papers of the 2005 Conference on Computational Complexity.

9:00 AM #

Wednesday, February 16, 2005

 
It's Safe to Study in America Again

Posted by Lance

I've seen several pointers to this nice article on origami and Erik Demaine in the Science Times section of yesterday's New York Times but also check out today's editorial page.

Thanks to pressure from prestigious academic and scientific organizations and leaders of high-tech industries, the administration added staff and streamlined the [student visa] process so clearance now takes less than two weeks, on average.

The capstone was a policy change announced last week that made a clearance valid for four years for students and two years for working scientists, making it easier for them to stay in the country for the duration of their study or research. America's reputation for welcoming scholars from around the world can only benefit.

We should always treat such news cautiously but hopefully these new policies will encourage more foreign students to come study in the states.

Update: Also in today's Times, an article announcing the ACM Turing Award that went to Robert Kahn and Vinton Cerf for their early work on the internet. The Turing Award is the closest computer science has to the Nobel Prize and its nice to see the New York Times taking it as such.

5:13 AM #

Monday, February 14, 2005

 
From Industry to Academics?

Posted by Lance

A reader question (anonomized):

How should you decide whether to go into industry? Are there ways back after you have sold your soul? The occasion: I got an offer from a major internet company to work at one of their labs. I have until Monday to decide. At this moment, I don't have any promising leads to do the research I'm interested in inside academia. My advisor says that if I don't like it at this company I can always come back, but I am a bit doubtful of that…what is your take on this?

It depends on the kind of industrial lab and how long before you would go back into academics. If you go to a basic research lab and continue to produce academic papers then you can find an academic job afterwords. You'll lose a little by not having teaching experience but that gets offset by having more time for research.

If on the other hand you go to an industrial job for even a couple of years and don't continue to produce academic research papers or attend conferences it will be very difficult to find an academic job afterwords particularly in a theoretically oriented field.

If you really want to stay in academics take an academic job that might not be to your liking and work hard to produce good research and try again later.

Do any of you readers have stories of people that have successfully gone from industrial jobs back to academics?

5:53 PM #

Saturday, February 12, 2005

 
Just Say No

Posted by Lance

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

Posted by Lance

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, 117 (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

Posted by Lance

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

Posted by Lance

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

Posted by Lance

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 #

Saturday, February 05, 2005

 
Information Markets and Quantum Computing

Posted by Lance

The DIMACS Workshop on Information Markets drew a neat crowd, a mix of computer scientists, economists (mostly experimental) and members of industry from companies as big as Microsoft and so small they are run by individuals in their spare time. Information markets create securities that can aggregate people's beliefs and help predict the likelihood of future events.

This workshop reminded me of the early conferences in quantum computing a decade ago. Quantum computing back then had some promising research (factoring algorithms for example) and no one was sure whether it would lead to whole new computing paradigm or just disappear into the ether. Information markets are also a new technology with some promising research (mostly analytic and experimental) and no one knows whether it will revolutionize the way everyone does prediction, information aggregation and decision making or just slowly disappear.

Information markets face different challenges than quantum computing. The technology already exists to run efficient markets and better tools are being developed. However the field needs to convince business and governmental leaders of the value and accuracy of the markets, overcome the stigma from the terrorism futures scare and find ways to overcome the legal issues relating to gambling in running real money markets.

Quantum computing needs to deal merely with the laws of physics but information markets need to deal with the laws of the United States of America.

Update 2/9: Ken Kittlitz's report on the workshop. (Thanks to Chris Masse)

3:41 PM #

Thursday, February 03, 2005

 
Internet at Conferences

Posted by Lance

One of my students wanted me to complain in my weblog at the lack of wireless access in conferences like the recent SODA meeting. Sorry but I don't agree. I've discussed before how I find internet at conferences reduces conversation between participants and prevents us from escaping from work back home. Is it so bad that the SODA participants were forced to (gasp) talk to each other?

On that note let me finish this post so I can pay attention to the talk.

3:27 PM #

Wednesday, February 02, 2005

 
How to Judge a Weatherman?

Posted by Lance

Each day a weatherman gives a probability p of rain for the next day and each day it either rains or it doesn't. How do we judge the quality of these forecasts? A first attempt uses linear scores, p if it rains, 1-p if it doesn't. However when you analyze this system the weatherman should predict p=1 if his belief is greater than 1/2 and p=0 otherwise.

A better measure is the log loss. The weatherman gets penalized -log(p) if it rains and -log(1-p) if it doesn't. A weatherman now has the incentive to announce his belief. There are other scoring functions with this property but the log loss has some nice properties such as the best a weather could hope to achieve is exactly the entropy of the distribution. The log loss and other measures are often used to analyze prediction mechanisms such as information markets.

Dean Foster and Rakesh Vohra have a different take looking at a notion called calibration. Here you take all the days that the weatherman predicted 70% chance of rain and check that 70% of those days it actually rained. A prediction algorithm calibrates a binary sequence if for finite set of allowed probabilities, each of the subsequences consisting of predictions of probability p have about a p fraction of ones. Foster and Vohra showed that some probabilistic calibration scheme will calibrate every sequence in the limit. In other words you can be a great weatherman in the calibration sense just by looking at the history of rain and forgoing that pesky meterological training.

Dean Foster and Sham Kakade gave a couple of interesting talks at the Bounded Rationality workshop giving a deterministic scheme that achieves a weak form of calibration and use it to learn Nash equilibirum in infinite repeated games.

7:48 AM #

Archives