Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Another question that comes up in discussions is who are the university's customers? Some possible answers:
I'll be talking about my favorite theorems of the past decade but you, my loyal weblog readers, have seen it here first.
Now only if we could find Gödel's lost notebooks on P versus NP…
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 τ
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.
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.
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.
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.We should always treat such news cautiously but hopefully these new policies will encourage more foreign students to come study in the states.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.
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.
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?
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.
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.
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"They mentioned P vs NP ALOT of times."Its the P vs NP thing"
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-
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.
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.
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)
On that note let me finish this post so I can pay attention to the talk.
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.