An Endless Frontier Postponed

Science has a special issue on Distributed High Performance Computing including an article Service-Oriented Science by Chicago's own Ian Foster. The must read is an editorial An Endless Frontier Postponed by Ed Lazowska and Dave Patterson.

At a time when global competitors are gaining the capacity and commitment to challenge U.S. high-tech leadership, this changed landscape threatens to derail the extraordinarily productive interplay of academia, government, and industry in IT. Given the importance of IT in enabling the new economy and in opening new areas of scientific discovery, we simply cannot afford to cede leadership. Where will the next generation of groundbreaking innovations in IT arise? Where will the Turing Awardees 30 years hence reside? Given current trends, the answers to both questions will likely be, "not in the United States."

Also from the CRA:

The timing of the issue also couldn't be better, given that the House Science Committee will hold a full committee hearing on "The Future of Computer Science Research in the U.S." on Thursday, May 12th. You can watch it live on the Science Committee's real-time webcast (also archived).

Postdocs

While other fields have standardized postdoc programs, computer science still searches for the right approach for postdocs. While we have had postdoc positions since I can remember, quite often researchers have gone straight from Ph.D. to tenure-track positions particularly in times of high growth in CS departments (early-mid 80s and mid-late 90s).

We are now seeing a spike in the demand for postdoc positions for several reasons.

• A tightening job market means less tenure-track jobs so more people opt to do postdocs to build up their CVs. Several researchers are even taking second and third postdocs, not long ago a rarity in CS.
• Many students opt to delay a tenure-track position for a year and do a postdoc first. The commitment goes both ways, if a department is holding a position for a student then that student is committing to going to that department. It's not fair to go back on the job market during that postdoc year. Some departments are becoming more reluctant to allow the year delay because of bad experiences with students not fulfilling that commitment.
• More and more students attend graduate school in their home countries and hope to eventually return to permanent jobs in those countries but take postdoc positions elsewhere to get a broader view of the field.

Alas we don't have an increase in postdoc supply to go along with this demand. Many of the industrial research labs have shrunk and hire few or no postdocs. Meanwhile most US academic departments have no permanent postdoc programs and CS grants are rarely large enough to cover the cost of a postdoc (as opposed to Canadian and European groups which tend to have more postdocs). Just another way the US is losing strong researchers to other countries.

Dilemmas of Prisoners and Professors

Some interesting game theory and philosophy from the last couple of NUMB3RS episodes. Usual spoiler warnings.

In the April 22nd episode Dirty Bomb there were three suspects who wouldn't talk. Charlie, the mathematician, likened the situation to Prisoner's Dilemma and suggested putting the suspects in the same room, which is usually the wrong thing to do in prisoner's dilemma. What Charlie did was compute the utility for each suspect cooperating (with each other and not the FBI) based on family considerations and their previous record and convinced the one with the most to lose by cooperating to defect and talk to the FBI. Clever, but I really wonder if that would work in real life.

Last Friday's episode Sacrifice took a more philosophical direction. A murdered think-tank computer scientist was developing a program that measured academic potential based on where someone grew up, down to a city block. If such a program actually worked, how should a program be used, if at all? How far should one go to stop the project?

Charlie and his physicist friend Larry ruminated on whether scientists are responsible for how their research gets used, as well as a discussion on the lonely life of a scientist at a lightly attended memorial service for the murder victim. The episode also had a physics joke I don't quite get.

Applied physicists are from Venus; Theoretical physicists wonder why it spins in the other direction.

I really enjoy those discussions between Charlie and Larry because they ask some interesting questions and add some dimension to a public view of mathematicians and scientists.

Leonid Khachiyan (1952-2005)

Leonid Khachiyan passed away Friday at the age of 52. Khachiyan was best known for his 1979 ellipsoid algorithm giving the first polynomial-time algorithm to solve linear programming. While the simplex algorithm solved LP well in practice, Khachiyan gave the first formal proof of an efficient algorithm in the worst case. The ellipsoid algorithm also has applications for more general convex programming questions and can be used for approximating semidefinite programming used for example in the Goemans-Williamson algorithm approximating max-cut.
One of my first exposures to theoretical computer science came in high school when I read a New York Times article describing the algorithm. I later learned that article has become our standard example of bad science writing, focusing more on an unlikely link to NP-complete problems instead of just describing the important theoretical problem Khachiyan's algorithm does solve.

Mr. Khachiyan's method is believed to offer an approach for the linear programming of computers to solve so-called "traveling salesman" problems. Such problems are among the most intractable in all of mathematics…In the past, "traveling salesman" problems, including the efficient scheduling of airline crews or hospital nursing staffs, have been solved on computes using the "simplex method".

New York Times science writing (and science writing in general) has vastly improved since those days.

Read this Weblog, Get a Job

One of the requirements for a software engineering job at Autodesk.

Good knowledge of common algorithms and data structures; understanding of computational complexity

Clemens Lautemann

Some sad news from Thomas Schwentick.

What we have feared during the last weeks and months came true yesterday morning: Clemens Lautemann died at the age of 53 from cancer.

Most recently Lautemann had been working on logical characterizations of complexity classes but I will remember him most for his beautiful proof (or here) that BPP, the class of languages with efficient probabilistical computatins, is in the second level of the polynomial-time hierarchy. In 1983 Sipser had shown BPP in the fourth level, and very soon after Gács and Lautemann independently showed BPP in the second level. Lautemann gave a very simple combinatorial proof that I consider one of the prettiest applications of the probabilistic method to complexity.

The Quality Thesis

Too often Ph.D. theses in computer science consist of not much more than a couple of "papers stapled together." A shame as one can use the thesis to truly bring out the importance of one's research.

There is no serious upper page limit on a thesis and you can truly spend the extra time to make your thesis stand out.

1. Put the results of your earlier papers together in a common framework and add some new results you never bothered writing up. (Harry Buhrman's 1993 thesis has a large collection of results on exponential-time computations that I still often consult.)
2. Take the time to expand the proof of complicated results to the right amount of intuition and depth. (For many years Madhu Sudan's 1992 thesis had the best write-up of the proof of the PCP theorem.)
3. The initial chapters of your thesis can serve as an introduction to a relatively new research area, (Michael Kearns's 1989 thesis gave an early broad overview of computational learning theory.)
4. Or give your own impressions of a more established field (Scott Aaronson's thesis expounds on his views of quantum computing.)

If you are looking for a job you'll be too stressed to do research anyway so why not take the time to write a quality thesis which will get your thesis widely cited and possibly even widely read.

My Mouse and Me

Today is take your daughter (and son) to work day so today's post is written by Annie Fortnow (age 10) on the topic of her choice.

This is a Dell Computer. It has 3 different parts. The first part is the screen. The screen is were you see what you are typing. The next part is the keyboard. The keyboard is the place were you type. The last part is the mouse. It is my favorite part because it helps me to click on the things that I want to click on.

There are many other parts of a Dell Computer. Those are the parts that I recognize the most. But the mouse is my favorite part. The mouse comes in many different shapes and sizes. On a laptop the mouse is either a circle in the middle, a square at the end, or both. On a regular computer the mouse is either an oval, a trackball, or looking like a mouse.

The mouse is a really important part of the computer. I will always keep mine in handy.

The Story of Ribbit

Around 1980 for fun in New Jersey we would go visit the electronic video arcades to play various games like Asteroids, Pac-Man, Tempest, Missile Command and many others. I was not much of a player but I was fascinated by the games themselves and wondering what it was like to program them. Between high school and college in the summer of 1981, a high school friend Chris Eisnaugle and I tried programming up a few games on his Apple II. I remember getting a passable version of Asteroids working in a couple of days.
We talked with a computer magazine writer who said we could legally sell a game based on an arcade game as long as we changed the name and slightly changed the user interface. We focused on the game Frogger which was not yet available for the Apple and created Ribbit written mostly over winter break. That spring we sold the program through a local computer store before we got a cease-and-desist order from Sierra Online, who had bought the personal computer rights to Frogger. So we ceased and desisted but not before 1200 copies of the program got sold. I made about $2000 from the program, not bad for a college freshman in 1982. Also a computer magazine review of Frogger liked our program better!

"Sierra Online's Frogger is even worse than the game named after the sound a frog makes."

In the summer of 1982 I worked as a instructor/counselor at the Original Computer Camp, Inc. in Los Olivos, California, which had a series of two-week sessions. Early in the summer none of the campers had heard about Ribbit but later on quite a few did. Not because of the 1200 legal copies but because pirated versions of the game were widespread. At first I was quite upset at the piracy, even deleting the game from the disks of the campers who had the game with them ("There is no honor among thieves" one such camper complained referring to the fact that we had stolen the idea of the game from Frogger). But soon I realized that we weren't selling any more legal copies anyway and the game lived on through its pirated versions. Still it wasn't long before Ribbit was mostly forgotten. On the webpage I set up for Ribbit I posted a pirated version of the game I found on the web. To get the original version I would have to find the disks buried somewhere in my mother's house and then find a machine that can read floppy disks from a time when disks were floppy.

scIenCE Princess

My daughters saw the movie Ice Princess over the weekend. Based on what they told me here is the basic story: Casey decides to do a science project on figure skating and uses physics and computers to help some skaters improve their routines. Casey's mom is really pushing her to science and sets up an interview for an academic scholarship to Harvard (Note to Hollywood: Ivy League rules prohibit academic scholarships). But Casey falls in love with figure skating and goes against her mother, says no to Harvard and follows her new dream of skating.

I have nothing against "follow your dream" movies and Ice Princess does put science and computers in a good light, at least in the early part of the movie. But just once can't we have a movie where a young woman whose parents want her to be a great figure skater, gymnast or tennis player but instead she follows her dream of becoming a scientist.

Favorite Theorems: NP-Completeness

March Edition

This month we honor the papers that gave us the first NP-complete problems and marked the official beginning of the P versus NP question. The P and NP notation did not originate with these papers but I will use them anyway for clarity.

Steve Cook, The Complexity of Theorem-Proving Procedures, STOC 1971.

Suppose a nondeterministic Turing machine M accepts a set S of strings within time Q(n), where Q(n) is a polynomial. Given an input w for M, we will construct a propositional formula A(w) in conjunctive normal form such that A(w) is satisfiable iff M accepts.

In this paper Cook gives the first formal treatment of the P versus NP problem. He gives several examples of NP problems and notes his notion of NP is equivalent to a class of extended positive rudimentary relations due to James Bennett. He introduces P-reducibility (now often called Cook reductions) where one reduces a problem A to a problem B by solving A using a polynomial-time machine with access to an oracle for B. His main theorems show that Tautology and Subgraph Isomorphism are hard for NP under P-reducibility. The quote above came from the beginning of the proof for Tautology.

The theorems suggest that it is fruitless to search for a polynomial decision procedure for the subgraph problem, since success would bring polynomial decision procedures to many other apparently intractable problems…The theorems suggest that Tautology is a good candidate for a set not in P, and I feel it is worth spending considerable effort trying to prove this conjecture. Such a proof would be a major breakthrough in complexity theory.

Indeed.

Leonid Levin, Universal'nyie Perebornyie Zadachi (Universal Search Problems), Problemy Peredachi Informatsii 1973. Translation in appendix of the Trakhtenbrot survey.

If we assume that there exists some (even if artificially formulated) problem of the search type that is unsolvable by simple (in terms of volume of computation) algorithms, then it can be shown that many "classical" search problems have the same property.

Levin claims that any NP problem reduces to any of a list of problems including tautology, subgraph isomorphism, tiling, set cover and a few others. As was the Russian tradition of the times, Levin's paper does not have fully formal definitions or any proofs. Still he has similar results and the same insight as Cook that one can reduce any NP problem to specific natural problems.

All of these problems are solved by trivial algorithms entailing the sequential scanning of all possibilities. The operating time of the algorithms, however, is exponential, and mathematicians nurture the conviction that it is impossible to find simpler algorithms…but not one has yet succeeded in proving it.

In today's world results proven today get transmitted around the world in minutes. But given the technological and even more important the political situation of the 70's, Cook and Levin did not learn of each other's work until years later. Today we give them both credit for taking the P versus NP problem out of the abstract and connecting it to solving natural problems. Now only three decades later the P versus NP problem has become one of the great open questions in all of mathematics.

A Fine Line Between Prank and Fraud

You have probably heard this story by now. Some MIT students created a computer-generated paper accepted to a non-reviewed session of the Systemics, Cybernetics and Informatics conference. I haven't mentioned the story earlier because I didn't want to give the students extra publicity but now that the story has hit the AP wire something needs to be said: What these students did was just plain wrong.

I'm no big fan of the SCI conference but virtually none of the conferences in computer science fully referee their submissions. A clever student could write a paper with a bogus proof and have a chance of that paper being accepted at a major conference like STOC. I would consider someone who intentionally submits a bogus paper to STOC guilty of academic fraud. Why are these MIT students any different?

Students make mistakes and we should tell them what they did was wrong instead of just glorifying such activities.

And The Winner Is …

Haipeng Guo wins the math poetry contest with the poem below. Congratulations and thanks to all that participated.

When a P-man loves an NP-woman

Been a happy deterministic man
With a simple polynomial brain
I contented myself with P problems,
And always looked at NP with disdain.

Fell in love with a polynomial woman,
But with a non-deterministic wit,
She said she would marry me,
Only if I could show her that P=NP.

I rushed to the library and studied,
Asked Garey & Johnson for a hint to the truth,
They said "this is quite a hard question",
But none of them had a hint or a clue.

Went to church and prayed to The Almighty,
"Please Oh Lord, give me a lead the truth",
"Don't waste your time son", a voice said laughing,
For I myself on this wasted my youth.

First oracle says you will marry
Second one tells you you'll split
Time moves, paths branch, results may vary
Accept the state that finally fits

If you finally marry this girl,
And P=NP was true,
What a Chaos: E-banking unsafe, Salesmen traveling cheaply!
And mathematicians with nothing to do!

If I grant your happiness,
The precondition must be no witness,
Even you both did nothing completely wrong,
The punishments will be exponentially long.

If you really want to marry this woman,
Then randomness might be the only key,
But please stop praying for an answer to me,
For I could not decide on this P=NP!

A New PCP Proof

There is some buzz about a new construction of probabilistically checkable proofs by Irit Dinur. The PCP theorem, first proved by Arora, Lund, Motwani, Sudan and Szegedy in the early 90's, states that every language in NP has a proof that can be verified randomly using O(log n) random bits and a constant number of queries. The PCP theorem has had many applications to showing hardness of approximation results and has had many improvements such as Håstad's tight result that I highlighted last year.

The previous proofs used considerable algebraic techniques. Dinur takes a more combinatorial approach using a powering and composition technique (inspired by Reingold and the zig-zag product) to separate the gap in 3SAT without increasing the number of variables.

An upcoming STOC paper by Ben-Sasson and Sudan gives a PCP for SAT of only quasilinear size but requiring polylogarithmic queries to verify the proof. Dinur, by applying her construction to those PCPs, can now create quasilinear-size proofs which only need a constant number of queries for verification.

Discussion Questions

New Balance has been heavily advertising some questions about sports so I'd thought I would give my own discussion questions about academics.

• You've been working hard on a research problem and someone else solves it. Does that make you feel happy or sad?
• Three people in an office. Two of them bounce ideas back and forth to prove a new theorem while the third just tries to keep up. Should the third person be a co-author?
• You are reviewing a paper and see an easy but major improvement to the paper's main result. What do you do?
• Your friend is applying to your university and you see that one of his recommenders wrote a weak letter. Do you tell your friend?
• Your advisor of the opposite sex has two tickets to a concert you really want to see and invites you to join him/her. Would you go?
• You discover a student wrote something strongly negative about a colleague on their weblog. What would you do, if anything?
• Would you still be a scientist if you could do research but all your work had to be published anonymously?

Go forth and discuss.

The Translation Lemma

A simple trick that every complexity theorist should know but, based on some recent conversations, not every complexity theorist does know. Roughly speaking collapses for small resource bounds imply collapses for large resource bounds. Here is the result for NTIME (nondeterministic time) and DTIME (deterministic time) but the proof works for nearly every pair of complexity measures.

Translation Lemma: Let f(n), g(n), h(n) be reasonable (time-constructible) functions with h(n)>n. Then

NTIME(f(n))⊆DTIME(g(n)) implies NTIME(f(h(n)))⊆DTIME(g(h(n))).

The proof uses a technique known as padding. Let L be in NTIME(f(h(n))) via a machine M. Define A by

A = {x01^h(|x|)-|x|-1 | x in L} We can compute whether x01^h(n)-|x|-1 is in A by simulating M(x) which takes nondeterministic time f(h(|x|))=f(m) where m=h(n) is the length of the input. So A is in NTIME(f(m)) and by assumption in DTIME(g(m)).
Now if we want to compute whether x is in L we can use the DTIME(g(m)) algorithm for A on x01^h(n)-|x|-1 taking total time g(h(n)) since the input has size m=h(n). QED

As an immediate consequence we get that if P=NP then E=NE (where E=DTIME(2^O(n))) by letting h(n)=2ⁿ.

The translation lemma works in only one direction. You need h(n)>n, you can't unpad an arbitrary x. It's open whether E=NE implies P=NP for instance.

The lemma has many applications. Here is one example.
Theorem: If P=NP then some language in E does not have subexponential-size circuits.

Proof: In the Σ₄ level of the E-time hierarchy we can compute the lexicographically-first language A that cannot be simulated by any 2^n/2-size circuits. If P=NP then the polynomial-time hierarchy collapse to P. By a version of the translation lemma with h(n)=2ⁿ the polynomial-time hiearchy collapsing to P implies the E-time hierarchy collapses to E. Thus A is in E but A does not have subexponential-size circuits.

A Modest Proposal

A guest post by Michael Mitzenmacher

Lance nicely invited me to expand on my views on the format for conference submissions. Currently, I am on a program committee using the standard theory call:

A submission for a regular presentation must be no longer than 10 pages on letter-size paper using at least 11-point font…additional details may be included in a clearly marked appendix, which will be read at the discretion of the program committee.

We have actually had discussions on whether to reject out of hand papers that use 10 point font or otherwise violate this standard.

The problem is that many, including myself, think that this formatting rule is silly, and so it has been widely ignored or at least painfully abused for many years. I would like to propose a simple and logical alternative: conference submissions should be in the same format (or as near an equivalent as possible) as the final conference version. Many other conferences (such as AAAI and Sigmetrics) use this approach with great success.

The advantages of this approach include:

1. It reduces the work of the authors. Right now, authors have to create entirely distinct submission versions and final versions of conference papers using various formats. Most authors find this a hassle, and this is my main reason for the proposal. I hate writing the same conference paper multiple times just to cope with formatting issues.
2. It gives the reviewer a more accurate picture of the conference paper. Reviewers will have a very good idea of what the paper will look like in the conference proceedings, making it easier to judge. When you're staring at 20+ pages of appendices, it is hard to tell what the final paper will look like.
3. It enhances fairness. Because this is a standard with a clear reasoning behind it -- you cannot have a longer submission than conference paper -- people are more likely both to follow and enforce the rule, avoiding potential unfairness.

I have heard of some disadvantages of this approach. Let me attempt to dispense with them.

1. The format is too hard for the reviewers to read.

   My response: If this is the case, then perhaps the conference paper format itself should be changed -- after all, don't we expect many people to actually read the conference version? If the conference paper is packed tight for other reasons (the publishers charge by the page), then for submissions design as near an equivalent format as possible. If we find 10 double-column 10 point pages with style file A essentially equals 20 single-column 11 point pages with style file B, then clearly state that in the call and ask for the latter. (Luca Trevisan pointed out this is done for the Complexity Conference already.)

2. Appendices are necessary when there are long proofs that won't fit in the paper.

   My response: If the proofs won't fit in the final conference paper, this is something a reviewer should see and know. The program committee can either allow appendices, with the knowledge they won't have room to appear, or allow pointers to more complete versions (TRs, arXiv preprints) that the reviewers can examine if they desire.

3. By having different formats, we force authors to revisit and hopefully improve their paper.

   My response: Nice intentions, but don't people already want to make their published work as good as possible? This seems unnecessary, and not worth the price.

I ask all program committee chairs to please consider this modest proposal.

Paper Pet Peeves

Little things that annoy me in research papers.

• Declarative first sentences of the introduction, like "Analyzing Left-Handed 12-SAT is a key approach to solving the P versus NP question." Just because you say it doesn't make it true.
• "We use novel techniques that might be of independent interest." A double faux pas. You don't get to call your own techniques novel. "Might be of independent interest" is such a meaningless statement.
• Footnotes (and parenthetical statements) which interrupt the flow of the paper. If it's not worth mentioning in the text then don't mention it.
• Using citations as nouns like "[13] using techniques of [6] showed the main result of [4] follows easily from [18]." I hate having to keep flipping to and from the references to read these papers.
• Using the cliché "larger than the number of atoms in the known universe." It's big. We get it.
• Using the word "respectively" which says "I'm going to give you something hard to parse because I'm too lazy to write two sentences."
• Titles with symbols or complexity classes: If you can't describe your research with words you might consider becoming a mathematician.

Does a book exist if nobody reads it?

A recent conversation with a graduate student.

Student: I couldn't find the paper online.
Me: So walk over to the library and get the paper there.
Student: But you can't take those books out and I don't want to spend hours at the library reading the paper.
Me: So make a copy and take it home.
Student: The library has copy machines?

Here is where I tell the story that when I was a graduate student and wanted a paper I walked five miles barefoot in blizzard conditions (actually two flights of stairs) to the library, or would send a stamped self-addressed envelope to an author. Not that we should go back to those times but don't ignore papers just because you can't find them online.

The next generation gets even worse. From a discussion in an undergrad class.

Student: I searched really hard for this topic and didn't find much. Are you sure it even exists outside of class?
Me: Really, I'm sure the math library [right down the hall] has several books on the topic.
Student: Oh, I just used Google.

Are we really getting to the point that if something isn't on the internet (or even on the internet but Google doesn't find it) then it doesn't exist?

The Battle of Grantsburg

From FYI:

Challenges to the teaching of evolution in public schools across the country have prompted National Academy of Sciences President Bruce Alberts to write to all members of the Academy. Warning of "a growing threat to the teaching of science," Alberts calls on Academy members, if such a controversy arises in their state or school district, to take actions against "attempts to limit the teaching of evolution or to introduce non-scientific `alternatives' into science courses and curricula."

Let me take you to the trenches in such a school district, Grantsburg, a small town in northwestern Wisconsin.

A good college friend of mine who grew up in suburban Connecticut, after finishing medical school and residency took a family practice position in Grantsburg. He got married, had kids and grew to like the rural life. But recently he got involved in a nasty battle with the school board.

The board last fall, after viewing an anti-evolution movie, had authorized teachers to teach "alternate theories of evolution" in the science curriculum. Last December, the board under some pressure changed the policy

Students are expected to analyze, review and critique scientific explanations, including hypotheses and theories, as to their strengths and weaknesses, using scientific evidence and information. Students shall be able to explain the scientific strengths and weaknesses of evolutionary theory.

Not much of an improvement. So the opposers brought in local professors to discuss the importance of evolution but this failed to sway the board.

So finally they tried to replace the board with a slate of science-friendly candidates but just this week they lost that fight as well.

And so my friend, who simply wanted to be a good country doctor, has made some enemies and worries about about the education his kids will receive.

Baseball is Back

A perfect spring day in Chicago and all of my afternoon meetings mysteriously canceled so I took visiting Portuguese professor and avid soccer fan Luis Antunes to his first baseball game, the Cleveland Indians against the White Sox.

Luis was sure he would be bored. We got awesome seats behind home plate and I introduced him to the full baseball experience with Polish sausages for lunch and Take me out to the ballgame during the seventh-inning stretch. Luis knew little about baseball but pretty soon he concentrated on every pitch counting balls and strikes. During the game he even said "baseball is not quite as boring as I had feared." The experience became complete when the Sox scored four runs in the bottom of the ninth to win the game.

Yes, baseball is back and all is good in the world.

Math Poetry Contest

From a poster in my building:

What is the longest song?

"ℵ₀ bottles of beer on the wall."

Happy Mathematics Awareness Month!

April is also National Poetry Month. In honor of April I am running my first (and perhaps last) annual math poetry contest. Winner will receive a copy of Complexity of Computations and Proofs (Jan Karjicek, editor), volume 13 of Quaderni di Matematica, Dipartimento di Matematica della Seconda Universitá Napoli, 2004.

Submit your new original poem on a mathematics or theoretical computer science theme in the comments section of this post with your name and/or email. One entry per person. Entries due by 11:59 PM CDT on Monday April 18. A panel of celebrity judges will choose the winning poem based on whatever criteria they deem fit. The decision of the judges are final.

Update: And the winner is…

What happened to the PRAM?

When computational complexity gets accused to having no connection to reality, I bring up the story of the PRAM (Parallel Random Access Machines), a complexity model killed by technology.

Today we think of the class NC in terms of circuits: NC contains the problems solvable in polynomial-size and polylogarithmic-depth circuits. But Nick Pippenger originally defined the class to capture parallel computation: problems solvable on a PRAM with a polynomial number of processors and polylogarithmic time. The PRAM model had several processors that shared a polynomial amount of random-access memory. There were three main variations:

• EREW–Exclusive Read/Exclusive Write: Every memory cell can be read or written only by one processor at a time.
• CREW–Concurrent Read/Exclusive Write: Multiple processors could read a memory cell but only one could write at a time.
• CRCW–Concurrent Read/Concurrent Write: Multiple processors could read and write memory cells. This variation had several subvariations depending on how one handled conflicting writes.

PRAMS got criticized due to the unrealistic nature of immediately addressable shared parallel memory. Areas like VLSI and Parallel Models (like the butterly network) worked to address these concerns. However while algorithmicists worried about the various PRAM models, achieving the better networks only causes a logarithmic factor increase in time and doesn't affect the complexity class NC.

So why don't we think PRAM anymore when we look at NC? Moore's Law. Processors got faster. Much much faster. The ideas of having many many processors each doing a tiny bit of work seems wasteful these days when we can just as cheaply have each processor do a lot of work.

We still see active research in parallel computing and one can speed up many computations using a large number of machines sometimes far away from each other just connected via the internet. But the best one could hope for is perhaps a quadratic improvement, not the exponential improvement that comes from PRAMs.

Another Breakthrough!

Speaking of space complexity, Adam Kalai, Adam Klivans and Rocco Servedio have extended Reingold's result to show that every language in randomized logarithmic space has a deterministic log-space simulation, i.e., RL = L. Cool.

You can find a copy of their paper here.

Sublogarithmic Space

A reader asks

I wanted to ask you something about the Savitch and Immerman-Szelepcsényi theorems that I saw you have in your weblog. In both thorems we have that s(n)≥logn. Why is that?

For any space function s(n), we also need to have a pointer to read every bit of the input and thus we'll have n2^O(s(n)) possible configurations. For s(n)≥log n, we can safely ignore the extra factor of n but for s(n)=o(log n) this causes problems for directly using the proofs of Savitch and Immerman and Szelepcsényi.

Still many researchers have studied sublogarithmic space classes but these results tend to be dependent on the exact machine model and it's tricky to understand what they tell us about general computation.

A Non-Standard Post

Mike O'Donnell tells a story of talk he saw once where the speaker considered the following recursive program: f(n) := output 0 if n = 0; output f(n-1) otherwise. By straightforward induction one can show that for any natural number n, f(n) will halt in a finite number of steps. The speaker argued that if we take n to be a non-standard natural number (which is bigger than all the standard integers) than the program will never halt. Mike O'Donnell counters that it will halt, just in a non-standard number of steps.

Suppose we could prove P≠NP in the theory of arithmetic. I can create a machine M that solve SAT on standard formula φ using |φ|^k time if k is nonstandard: Since k and thus |φ|^k is greater than every standard integer, we have time to do exhaustive search. However there will be some nonstandard φ that M will fail to solve satisfiability in time |φ|^k time, for whatever the satisfiability question for nonstandard φ means.

Now suppose P=NP in the standard model but P≠NP in some non-standard model (and thus the P versus NP question is independent of the theory of arithmetic). We have a standard machine M and a standard integer k such that M(φ) correct computes whether a standard φ is in SAT in |φ|^k steps. But for some non-standard φ, M(&phi); would fail even though it gets to run in time n^k for the nonstandard n=|φ|. Even if we allow M and k to be non-standard there will be some φ that M will fail to determine satsifiability.

You can keep playing this game and never get into trouble assuming the theory of arithmetic is consistent. But I get a headache when I try to think what non-standard Turing maching, non-standard polynomial running time and satisfiability of non-standard formula really mean.

Getting an Edge

Using performance-enhancing drugs has become a major issue in national and international sports, most recently in Major League Baseball in America where many major players have admitted (or refused to deny) using steroids to increase their power.

What about in academics? Supposedly some mathematicians have used amphetamines to get an edge or keep up with younger mathematicians. If we discover that a mathematician used such a performance-enhancing drug to prove a theorem would we take away his credit for that result? No, we wouldn't.

I don't have any direct evidence that any mathematicians or computer scientists actually use any performance-enhancing drugs, other than caffeine of course. Even so I doubt many of us would agree to random drug testing of academics. But then why should professional athletes be held to a different standard than professional academics?

My Brother

I have a brother who worked in the music industry and got us first row tickets to Kool and the Gang. I have a brother who was an entertainment lawyer who appeared on Court TV and a morning show in Trinidad and Tobago. I have a brother who co-founded a popular fantasy sports website commisioner.com which was later bought out by CBS Sportsline. I have a brother who was shown in a bar celebrating the Red Sox during the World Series telecast last fall and a week later pictured in the New York Post with the trophy. I have a brother who created an award winning short film in New York and is now producing a movie in LA.

I have but one brother. Happy Fortieth Matt. Thanks for making my life seem so ordinary.

P=NP and the Arts

A few years ago someone asked Steven Rudich, a complexity theorist at Carnegie-Mellon, why he thought P is different than NP. He replied "I can recognize great music but I can't create great music," the implication being that it's much harder to find a solution than to verify one.

But suppose NP-complete problems do have very efficient algorithms. Can we use them to create art, perhaps, as someone recently suggested to me, create a new Mozart opera, Shakespeare play or finish Schubert's symphony?

Perhaps we could use P=NP to find a small circuit that outputs "Shakespeare" plays. But these plays will only extrapolate from his known works. The program cannot add the new creative ideas Shakespeare puts in his works. It cannot create art just generate similar pieces.

Of course this whole exercise is moot since we strongly believe that NP-complete problems are hard. Even so a P=NP fantasyland might put some mathematicians and computer scientists out of work but true artists will still create in ways computers can never match.

Complexity LaTeX Package

From Chris Bourke: I've created a LaTeX package for typesetting complexity commands ($\P$, $\NP$, etc). Its available on CTAN. Not only does it define commands for classes (and languages, functions) but with just an option call to the package, you can specify the font all the classes are typeset in. I welcome feedback.

Tape Reduction

Given a k-tape Turing machine can we reduce the number of tapes without too large an increase in time and space (memory)? Not just an esoteric question, tape reduction plays an important role in time and space hierarchies and creating efficient reductions.

For space we have an easy result: Every k-tape s(n)-space bounded Turing machine can be simulated by a 1-tape machine in O(s(n)) space. Create a single supertape with separate "tracks" for each of the original tapes and add markers for the locations of the heads on each of these tapes.

For deterministic and nondeterministic time, this constructions yields a t²(n)-time 1-tape simulation of a k-tape t(n)-time machine and this is the best you can do (consider { x#x | x∈Σ^*}). We can do much better if we reduce k tapes to 2 tapes.

We can simulate any nondeterministic t(n)-time k-tape machine in nondeterministic O(t(n)) time on a 2-tape machine. Roughly the simulation guesses every step of the transition function on one tape and uses the other tape to verify the transition function on each tape of the original machine one tape at a time.

For deterministic time we can only achieve a weaker result: Every t(n)-time k-tape machine has a 2-tape simulation using O(t(n)log t(n)) time. The proof (due to Hennie and Stearns) is quite involved and I won't give it here. The proof has a nice side effect: The construction creates an oblivious machine where the head movements depend only on the input length. One can use this fact to show that we can simulate any t(n)-time Turing machines with O(t(n)log t(n))-size bounded fan-in circuits and reduce any t(n)-time nondeterministic computation to satisfiability questions of size O(t(n)log t(n)).

Paul Fortnow (1937-1980)

My father passed away 25 years ago today. I thought I would share some of the lessons I learned from him.

• Once you win an argument, stop arguing.
• Always play to win. He would always take a handicap and play his hardest rather than dumb down his play particularly in chess, his favorite game.
• When he went to college, the engineers measured their prowess in the number of digits of precision they could get from their slide rules. I guess he didn't get enough digits as he gave up engineering and eventually went into marketing.
• The extra character in a movie that seems to serve no purpose is the one that committed the murder.
• He said "When you grow up and drive you can choose the radio station." Like my daughters let me get away with that.
• Nixon really was a crook.
• Given enough money, there is nothing anyone won't do.
• He meticulously taught me how to keep score in baseball as this is a skill every American should know. He then told me never to keep score as it distracts from the game.
• The two course he regretted not taking in college were art and music appreciation. So I took art appreciation in my first year. Big mistake. For the record the two courses I wish I took were economics and mathematical logic.

Dad, if you are surfing the net from the great beyond know that I miss you and my family, including the daughter-in-law and granddaughters you never met, think of you often. And your Red Sox finally won the World Series.

The End of the Travel Season

In 2005 I have already traveled on five trips to four different countries on three different continents. My travel comes in bunches. I didn't teach in the winter quarter (at the cost of doubling up in the spring) so I planned much of my travel during this time. After I return tomorrow I have no major trips planned until STOC in late May.

Why do I travel? I don't enjoy at all the act of traveling despite the advantage of non-stop flights to nearly everywhere from Chicago. The tourism bit has long lost its allure. After a while all the cities and universities start to look the same.

I don't need to travel. I could hole up in Chicago, just work with the students and visitors and have a moderate research career. I have tenure so my job is safe in any case. So why travel?

1. People: Working with people, talking with people, drinking with people. Traveling to visit different people keeps my research and academic life from getting stale.
2. Getting Away: Like most people, I have considerable work and family responsibilities and travel allows me to escape and have time to focus on research. When I visit someone for a short time they will usually make time to work with me as well. The internet has prevented me from completely escaping but I can usually tell people I'm away and I will deal with the problem when I get back. I do try to keep to a goal of not leaving the family for more than a week at a time.
3. Being Involved: If you want to be an active member of the community people need to know who you are. Don't travel and people will forget you. Email is not a good substitute for meeting face to face.

Traveling has many virtues but I am really looking forward to two straight months of going no where at all.

Bicycling in Holland

When I visit Amsterdam I rent a bike for much the same reason I rent a car when I travel to New Jersey. CWI is in the east part of the city and does not have great access via public transportation. A bicycle lets me get from the hotel to CWI quickly and also gives me easy access to the rest of the city.

Why does the Netherlands have such a strong biking culture? Most of the country is flat, the cities are compact (at least by Chicago standards) and the weather never gets too hot or too cold to bike. One can reliably commute by bike nearly every day of the year. The country has many dedicated bike paths and marked bike lanes on many major roads. Traffic laws greatly favor bikes over cars. This all gives positive reinforcement to bicycling in this country.

Bicycles here for the most part do not have hand brakes or multiple gears but are otherwise rather sturdy. Bicycle lights are required at night; a visiting complexity theorist got a ticket for not using his. Virtually no one wears a helmet. When we lived here on sabbatical we would put our one-year old daughter on a bike seat on the handlebars without a helmet—the norm for Holland but might have gotten us arrested back in the states.

Bicycle theft is a big problem especially in the cities. The general rule is to spend as much on the lock as you did on the bike. Locking up your bike requires knowing your topology; Get it wrong and you might lose a wheel or worse yet keep your wheel and lose the rest of the bike.

Most people in Holland don't bike for health or environmental reasons. Bicycling is often simply the easiest way to get from point A to point B.

What Makes a Good Collaborator?

This week I visit CWI in Amsterdam where I spent my sabbatical year eight years ago and continue working relationships with many people here especially Harry Burhman. Harry is my strongest collaborator in the sense that I have written far more papers with him than any person. So what makes for a good collaborator?

• Strength—A good collaborator should of course be a strong researcher in my area of interest and Harry certainly fits that bill. But there are many great complexity theorists I have hardly or never worked with.
• Compatibility of Strengths—The strengths should complement each other nicely. Good collaborators know their areas well and can quickly focus the inherently difficult parts of a problem and have different tools and approaches they can bring to the table.
• Respect—Good collaborators need to trust and respect each others ability and judgment.
• Philosophy—Long-Term collaborators need to share beliefs on what problems are important and worth working on.
• Personality—You need to have a friendly relationship outside of work. It helps immensely if your respective families get along.
• Luck—Finding the right problems to work on together at the right time. You need a good first collaboration before you start making time for further collaborations.
• Distance—This seems counterintuitive but two people in the same geographical area rarely have a long history of collaboration. It's hard to make time for working together when you are in close proximity. Also two people who see each other constantly get tired of working with each other no matter how compatible they are. Better to keep in email contact and have several short and long visits where one can allocate time for the other.

There is something else that I can't perfectly describe where something just "clicks" when you have someone you can work with well.

The Reality of Virtual Pets

The Tamagotchi craze has hit my daughters' school. The Tamagotchi is a small toy with a few buttons and a screen where you can play with a cartoonish creature. You can feed and play with your creature to make him/her happy. Two people can point their devices at each other and their Tamagotchis will play and possibly "mate".

First my older daughter's fourth grade friends gave her a Tamagotchi and soon after my younger first grader also wanted one and we relented. She then convinced several of her first grade friends that they needed them which caused some parents to call us mostly because they got these Tamagotchi and nobody could figure out how to work them. My first grader is giving out lessons tomorrow.

These devices beep when they need attention—food or playing or needing cleanup after an "accident". Don't attend to them and they will die. My kids pay constant attention to the Tamagotchi and it is sometimes hard to bring them back to reality. My youngest, a couple of days ago, got all excited when her Tamagotchi learned to go to the bathroom by himself. It didn't seem like all that long ago that I got excited about the same thing for her.

Luckily young kids are fickle and the Tamagotchi craze will soon pass. But move over Godzilla, the scariest monster from Japan is a friendly looking creature in a plastic case.

NP-complete Problems and Physical Reality

Scott Aaronson has a fun paper in the complexity column of the new SIGACT News where he addresses the question: Can NP-complete problems be solved efficiently in the physical universe? Worth reading though I can sum up the answer in one word: No.

Favorite Theorems: Efficient Computation

February Edition

How do we formalize the notion of efficient computation? Two important papers from the 60's suggest polynomial time algorithms are efficient though both caution against equating the concepts.

Paths, Trees and Flowers, Jack Edmonds, 1965.

The Intrinsic Computational Difficulty of Functions, Alan Cobham, 1964.

Edmonds paper will always be best known for giving the first efficient algorithm for matching on general graphs. But I list it here because of a section of his paper labeled "Digression". Edmonds talks about the difference between exponential and algebraic (polynomial) order though he cautions against any rigid criteria for efficiency.

An explanation is due on the use of the words "efficient algorithm"…I am not prepared to set up the machinery necessary to give it formal meaning, nor is the present context appropriate for doing this…For practical purposes the difference between algebraic and exponential order is more crucial than the difference between [computable and not computable]…It would be unfortunate for any rigid criterion to inhibit the practical development of algorithms which are either not known or known not to conform nicely to the criterion…However, if only to motivate the search for good, practical algorithms, it is important to realize that it is mathematically sensible even to question their existence.

Cobham defined the class we now call P as important because of its machine independence.

For several reasons the class P seems a natural one to consider. For one thing, if we formalize the definition relative to various general classes of computing machines we seem always to end up with the same well-defined class of functions. Thus we can give a mathematical characterization of P having some confidence it characterizes correctly our informally defined class. This class then turns out to have several natural closure properties, being closed in particular under explicit transformation, composition and limited recursion on notation (digit-by-digit recursion).

Cobham also offers a caution.

The problem is reminiscent of, and obviously closely related to, that of the formalization of the notion of effectiveness. But the emphasis is different in that the physical aspects of the computation process are here of predominant concern.

Perhaps Cobham realized there might be future models of computation that may not correspond to his class P. Later developments of randomized and quantum computation will show that perhaps we cannot have a fixed notion of efficient computation.

The Researcher's Dilemma

I finally read Clayton's Christensen's The Innovator's Dilemma. A few years ago an NEC executive gave a talk using the ideas in the book to explain NEC's interest in quantum computing.

Christensen divides new technologies into two groups: sustaining and disruptive. Sustaining technology helps improve a product for its current customers for example Intel building a faster microprocessor. Disruptive technology is technology that is not initially useful for a big company's current clients. So other newer and smaller companies develop the technology for a niche market. But eventually the technology improves to meet the needs of the original big company's customers at a much lower cost. At this time the big company cannot catch up with the new technology and loses their main business to the newer startups. Christensen gives many examples such as the development of smaller disk drives and the advent of discount stores like Target hurting bigger retailers like Sears.

The book makes some solid arguments but determining which technologies will be disruptive is quite difficult. So companies need to place lots of bets perhaps why NEC funds quantum computing research just in case it becomes a disruptive technology in the future.

Do the same concepts apply to research? In complexity we have had some disruptive technologies, for example, the PCP theorem for hardness of approximation or the idea of Nisan and Wigderson of using hard languages to derandomize, or going way back the whole concept of NP-completeness. Other concepts like circuit complexity have not been as disruptive as originally thought. Also one could view tools like the probabilistic method or extractors as disruptive.

What could happen to large companies can also happen to researchers. Suppose George is a researcher who creates new results building on current ideas with small twists (sustaining technology). George ignores some new ideas in complexity because it doesn't seem to help him prove new results in his area. But as those new technologies develop they later allow others to go well beyond what George has done. Now George is behind the curve on the new disruptive technology and can no longer play an important role even in his own field.

What can George do? He can learn the new techniques or he can change fields. And often the newcomers never properly learn the old tools and George can still pull a few surprises out of his hat.

Finding Duplicates

Here is an interesting problem given by Muthukrishnan during his talk in the New Horizons workshop.

Start with an array A of n+1 entries each consisting of an integer between 1 and n. By the pigeonhole principle there must be some i≠j and a w such that A(i)=A(j)=w. The goal is to find w. Depending on A there may be several such w, we want to find any one of them. The catch is that you only get to use O(log n) bits of memory.

First a warm-up puzzle: Find w using only O(n) queries to entries of A (remember you only get O(log n) space). Hint: Use pointer chasing.

Now suppose A is streamed, that is we get in order A(1),A(2),…,A(n+1) and then get another pass etc. How many passes do you need to find a w?

You can find w in n+1 passes just by trying each possible value for w. With a little work you can use O(log n) passes doing a binary search.

Muthukrishnan asks whether the number of passes needed is Ω(log n) or O(1) or something in between.

Theory in Japan

Japan has produced some excellent theorists, like Seinosuke Toda who won the 1998 Gödel prize for his paper reducing the polynomial-time hierarchy to counting solutions of NP problems. But Japan has not had the large international impact in theoretical computer science as countries like Israel, India or Hungary.

In this trip I am seeing signs that this may change for the better. The conference is kicking off a new project New Horizons in Computing that shows a serious commitment of the Japanese government to computer science theory. The large turnout, over 130 registrants the majority of which are students, shows a keen interest in theory from the academic side as well.

I'd like to see more Japanese go abroad for graduate work and postdoc positions and more Japanese universities making theory an important part of their computer science programs. But given the excitement I see at this meeting I am very hopeful that Japan will also become a true theory powerhouse in the near future.

Are we the university?

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.

New Horizons in Japan

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.

Ramanujan's Lost Notebook

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…

The Complexity of the Nash Equilibrium

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.

Factoring NUMB3RS

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.

Computer Science Recruiting

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.

Complexity Accepts

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.

It's Safe to Study in America Again

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.

From Industry to Academics?

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?

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.

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, 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)).

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.

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.

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.

Information Markets and Quantum Computing

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)

Internet at Conferences

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.

How to Judge a Weatherman?

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.

An Auction of Computing History

From Ryan O'Donnell

Christie's is auctioning off a bunch of documents related to the history of computing.

A '46 IAS report by von Neumann and others to the US Army on the concept of a computer is expected to go for around $35k, an original copy of Turing's "On computable numbers" for about $17.5k, a letter from Gödel to Skolem for about $15k, Shannon's collected works for about $10k, etc.

More from Anupam Gupta: Some related info (including dates of exhibitions in Cambridge MA, and Palo Alto) and also on Boing Boing.

DIMACS

This week I'm in the great Garden State of New Jersey (my home state) for back to back DIMACS workshops on Bounded Rationality and Markets as Predictive Devices.

Since 1989 DIMACS (the Center for Discrete Mathematics and Theoretical Computer Science) has greatly served our community with a collection of workshops, visitor and postdoc programs built around special years (later becoming special foci as they extended to several years). The workshops this week come under the Special Focus on Computation and the Socio-Economic Sciences. DIMACS also has a strong educational mission with programs for teacher training and for high school and undergraduate students.

DIMACS started as a National Science Foundation Science and Technology Center and when that program ended in 2000 DIMACS continues through a series of smaller state and federal grants. DIMACS based at Rutgers has partners drawn from several New Jersey universities and research laboratories. DIMACS has a strong but small staff and many volunteers within our community but I attribute the recent continued strength of DIMACS mostly to the tireless efforts of its director Fred Roberts.

DIMACS plays an important central organizing effort in theoretical computer science and has often represented theory to the NSF and other funding agencies. DIMACS has had an important direct and indirect role in my academic career and I suspect the careers of most theorists. Let's hope DIMACS can continue its multifaceted role in our field for decades to come.

Choosing Your Advisor

Someone threw out this quote yesterday.

Choosing your advisor is like choosing your spouse.

I would say more like choosing your parent since the advisor-student relationship is not symmetrical. But the point remains: No single decision will make or break your graduate career more than the choice of advisor.

A good advisor serves as a mentor and a colleague. Someone who will represent you, fight for you, challenge you and push you but not belittle you or take advantage of you. He or she will direct your research to primarily address your future career. An ideal advisor-student relationship will develop into a mutually strong research environment and will last well beyond the student's graduate career.

You should ideally choose an advisor whose expertise matches your research interests. But more importantly you need to find the advisor with which you can have a strong working relationship. You don't have to see eye-to-eye on every issue but you need to have mutual respect. Like in marriage, an advisor might work well with one kind of student but not with another. You need to find the right advisor that fits your needs and personality. If the advisor relationship goes sour for any reason, you need to change advisors. Being stuck in bad advisor-student relationship is almost a guarantee of a disastrous graduate career.

Remembering the Holocaust

As you probably know today was the sixtieth anniverary of the liberation of Auschwitz. In religious school as a kid we read books, saw gruesome movies, met holocaust survivors and I visited a concentration camp during a college trip to Europe. But the enormity of the holocaust hit me most during my sabbatical year in Amsterdam in 1996. One fourth of the population of the city was Jewish in the 30's. We had to work hard to find the small Jewish population so we could properly celebrate the Jewish holidays during our year there.

I worry sometimes about how to keep my children aware of the holocaust. How do I prevent them from just thinking it was just some event that happened a long time ago? When they reach my age what will they and the world do for the 100th anniversary of Auschwitz? Let us hope we can always remember.

STOC Papers

The list of accepted papers for STOC is up. Nice to see they accepted Trifonov's paper in addition to Reingold. Many other nice complexity results too. Take a look.

Blink

A publisher sent me a copy of Blink a new book by Malcolm Gladwell. Gladwell wrote the very popular Tipping Point about phase transitions which I haven't read.

The main thesis of Blink states that people can make good predictions quickly and with a small amount of information if they have experience or are properly trained. The real challenge is to get people to ignore excess information and focus on the few bits that can really can accurately determine an outcome. Often people make better decisions when rushed since they won't have time to focus on the extraneous details.

Gladwell does his homework and makes his case best by describing experts who do a good job predicting the longevity of a marriage, the flight of a tennis ball or the popularity of a new food item. I find his one-time examples less convincing since anyone can get lucky and even his best experts make occasional mistakes.

How do these ideas relate to computer science? In many more ways than I can mention in this post. Juntas (or NC⁰ as we used to call them) are functions that depend on a constant number of input bits and we've seen recent work on learning juntas. In general most of learning theory focuses on finding a short description that predicts well. Transformations like Fourier transforms and wavelets which allow researchers to focus on a small amount of important information useful in many areas like computer vision. The recent areas of sublinear algorithms and property testing often can say something interesting about an input by only looking at a small part.

In my job I also find myself using less information to make just as good decisions. I can often get a good feel about a research paper or a recommendation letter by a quick focus on a few key elements. I can almost always predict the quality of a talk within the first thirty seconds. Even in research where one has to narrow the list of techniques, I can eliminate large sets of approaches without having to work them out thoroughly.

One needs care not to weed out a good idea too quickly but if you allow yourself to get bogged down in details you will spend too much time often making the same or possibly worse choices.

The Premier of Numb3rs

Feel free to comment on last night's premier of Numb3rs, a show that has seemed to capture the interest of this community. For good reason as apparently the P versus NP problem will get mentioned on episode four, the best publicity we'll get since Homer Simpson went 3-D.

My wife and I enjoyed the show. Charlie, the mathematician character, definitely fits within the convex hull of math types I know. I liked the scene where Charlie asked several people to position themselves randomly and remarked that they were evenly spaced while real random points would have some clusters. Viewers might actually learn some interesting mathematical concepts watching this show.

At one point Charlie's physicist friend says something like "You are almost thirty at the peak of your game and most mathematicians only have five to six good years in them." Generally accurate but a little disheartening to this forty-one year old.

Machine Learning, Information Markets and Love

John Langford starts a new weblog Machine Learning & Theory.

2004 Year End Awards from Chris Masse's Predictions Market Digest (from David Pennock)

Is love more complicated than computational complexity? I can't make this up.

Does a Chess Program have Free Will?

A non-CS Chicago Alum asked me a question about free will and computation. I passed the question to David McAllester, an AI professor at TTI, and he gave the following interesting reply.

The idea that I could be simulated on a computer seems at odds with my subjective experience of free will and my intuition that my future actions are not yet determined — I am free to choose them. But consider a computer program that plays chess. In actual chess playing programs the program "considers" individual moves and "works out" the consequences of each move. This is a rather high level description of the calculation that is done, but it is fair to say that the program "considers options" and "evaluates consequences". When I say, as a human being, that I have to choose between two options, and that I have not decided yet, this seems no different to me from the situation of a chess playing computer before it has finished its calculation. The computer's move is determined — it is a deterministic process — and yet it still has "options". To say "the computer could move pawn to king four" is true provided that we interpret "could do x" as "it is a legal option for the computer to do x". To say that I am free is simply so say that I have options (and I should consider them and look before I leap). But having options, in the sense of the legal moves of chess, is compatible with selecting an option using a deterministic computation. A chess playing program shows that a determined system can have free will, i.e., can have options. So free will (having options) is compatible with determinism and there is no conflict.

Favorite Theorems: The First Decade

I have listed my favorite theorems for the first and second decades of my research career corresponding roughly to the third and fourth decades of research in computational complexity. This year I will list my favorite theorems for the first decade of complexity, 1965-1974.

As opposed to the previous lists, we have 30-40 years of hindsight to see what theorems have stood the test of time. Each month starting in February I will highlight one result and mention related work to show how computational complexity went from a simple but beautiful idea to an important subdiscipline of computer science.

Recommendation Letters

A few random comments as I read and write recommendation letters for various academic positions:

Back in the old days, a candidate would send a department a list of references and the department would send to each reference by postal mail a request for a letter which would be sent back by postal mail and followed up by a thank you sent again by postal mail. Faculty had a lot more secretarial support back then. This year I only got one such request, from a math department. Many departments have the candidates ask the recommendors to send letters directly by post and/or email. The best organized departments send the recommendors a link that leads to a secure upload page that puts the letter directly in the department's database.

Some misguided people like to send letters by post because they worry about the security of email and the electronic storage of their letters. Letters sent by post are far less secure. Copies of these letters must be made and these copies get left, on copy machines, in mailboxes in public areas, on peoples desks and in conference rooms. In any case it doesn't make sense to go crazy over security, any student with a little imagination can find a way to see their letters. Students: Don't do this. No good will come out of it.

There is an old saying "If a price is advertised as under $30 you can rest assured it is not $19.99." I take this saying into account when I read recommendation letters, particularly lines like "among the top half of complexity theorists graduating this year". In general I read letters more for what is not said than what is said.

"Strong potential" looks good for a fresh Ph.D. and the kiss of death for a senior candidate.

I ignore negative recommendations as probably personal issues. If you really dislike someone write a lukewarm letter. Seriously, if you don't feel you can write a strong letter for someone make up an excuse for why they shouldn't list you as a reference. Don't refuse to write if you get a request directly from a department. No letter is seen as a negative letter.

"I recommend" is a weak recommendation. "I very strongly recommend" is a strong recommendation. "I give my strongest recommendation" is a meaningless lie. "Don't hire this person because we plan to make him/her an offer and we want him/her for ourselves" is as strong as they get.

Theory for Dentists

Thanks to Rahul Santhanam for covering for me last week. If you are looking for a smart hard-working postdoc in complexity take a look at Rahul.

On the plane last week the passenger sitting next to me, a dentist from Vancouver, was reading a Scientific American article on quantum cryptography. Quantum cryptography got its start from people in the theoretical computer science field like Charlie Bennett and Gilles Brassard. For our field to flourish we must produce research of interest to others and to see outsiders reading about the fruits of our labor just for fun is a good sign.