A New Packard Fellow

Piotr Indyk, himself a 2003 Packard Fellow, writes

On the recent blog topic of awards: you might be interested to know that Venkat Guruswami just received a Packard Fellowship.

Congrats to Venkat for recognition (and money) well deserved.

NP-Completeness Papers

A colleague is refereeing a paper in a non-computer science area that shows a certain computational problem is NP-complete. The proof uses a simple reduction from a standard NP-complete problem. Should such a result be published? As long as people really care about the computational problem, then yes, such results should be published.

The greatest gift of computational complexity to society is the ability to use NP-completeness to show that a large variety of problems are likely hard. The field has also developed many tools to help easily show such problems are NP-complete. We shouldn't penalize people for using these tools.

This is one of those cases where having a "simple proof" hurts the paper. If the paper used PCP technology in the proof it would without question be published. And if the paper relied on the unique games conjecture (and thus a weaker result) the paper would likely get accepted into STOC.

Unix Free Since 1999

My first computer was a TRS-80, my second an Apple IIe. In college I mostly programmed in IBM 370 assembly code. But in graduate school (first at Berkeley and then at MIT) I starting using Unix in its various forms and its programs, first Vi and Troff, then Emacs and LaTex and reading email via the command line "mail."

My future wife had one of the early "IBM Compatible" PCs and I liked some of the programs one could use, like Quicken, Prodigy (an information dial-up service), good spreadsheets and word processing. My home computer has always been a DOS/Windows machine since.

Windows had good calendar and email programs long before they were available for Unix so at one point I got a PC card for the Sun in my office which ran Microsoft Windows in an Unix window. As I found myself spending more and more time in that window, my next machine was a Windows machine with an X-Windows program so I could connect to the department's Unix machines to use Emacs and LaTex.

Soon very good Emacs and LaTex programs became available for Windows and when I moved to NEC in 1999 I went Unix free and haven't looked back. My biggest complaint about Unix was the user interface. To print pages 3 to 5 of a latex document is easy in windows, for Unix I had to do a man dvips since I could never keep straight which flags did what. Once I spent hours trying to figure out what I did wrong in a Make program (I had uses spaces instead of tabs). I'll never forget the time I accidentally typed "rm temp *" instead of "rm temp*".

Ever since people have kept telling me Linux interfaces and programs have gotten much better, and they have, but never enough to get me to switch back. Some Apple lovers have tried to get me to move to Apples, but they just never had the software available that PCs do. Windows emulators for Apples are popular but you don't see the need for the other direction.

As more and more of the programs I use become web based, the actual platform becomes less and less important. Still though as someone who likes an easy user interface and wide availability of programs and doesn't do much programming and scripting, Windows has worked well for me.

Tradition

A conversation with a graduate student today.

• Student: Why doesn't FOCS have a best paper award this year?
• Me: They often don't announce the winners until the conference begins.
• Student: Traditionally the best paper get longer talks and there are none scheduled.
• Me: There's no such thing as tradition at STOC and FOCS. Rest assured (though I have no prior knowledge) there will be a best paper award given.

I've heard that by tradition FOCS has had single sessions and STOC has had parallel sessions. Not long ago both had parallel sessions and before that FOCS had the parallel sessions (the first time with a two volume proceedings) and STOC had single sessions, and before that both had single sessions. STOC/FOCS used to be Monday-Wednesday, now they are Saturday-Tuesday and sometimes not. STOC/FOCS were always in North American and then they weren't. FOCS once had the only best student paper award and then had the only best student paper award named after somebody. Now they both do. We've had invited speakers. We've not had invited speakers. We've had tutorials. We've not had tutorials. One day one of the conferences will have electronic proceedings and the other won't and that will be tradition.

The decisions of how STOC and FOCS are run are up to the program committee with constraints on schedule and the local arrangements site. Two or three years of the same in a row becomes a "tradition" and hard to change. But we shouldn't let these "traditions" prevent us from running the best possible conferences and nor should you count on them to continue as is. Traditions keep us in the past, change pushes us to the future.

DNA Testing for Sports

In the second biggest sports story in Chicago (after the White Sox rout of Boston), the Chicago Bulls basketball team traded Eddy Curry to the New York Knicks. The Bulls had wanted Curry to take a DNA test to check for a certain heart condition and Curry refused so finally they decided to trade him to the Knicks who will not require the DNA test. I understand the Bulls' position but testing DNA for diseases for employment opens up a big can of worms. Shades of Gattaca?

On a completely different note, one-time guest blogger Scott Aaronson has joined the blogosphere himself. What took him so long?

Euthanizing a Virtual Pet

We had a high pitch tone coming from somewhere in our family room but we couldn't find the source. I shut down the power in case the sound was coming from the stereo system or lights but the tone remained. Finally we found the culprit, my daughter's Tamagotchi buried under some books.

Pressing the buttons failed to quiet the device, so I attempted to open the unit up to remove the battery. When that failed I finally put the Tamagotchi in a plastic bag and hit it several times with a hammer until it finally shut up.

Later I confessed the destruction of the virtual pet to my daughter who seemed not to care in the least. The fad had ended. But next on my daughters' wish list: Nintendogs.

Awards

The Nobel Prizes will be announced this week and I predict that no one will win the Nobel Prize in computer science for the 105th consecutive year. Computer Science's highest honor, the Turing Award will be announced in early 2006 (February 16 last year).

We also have some awards coming up for theorists. At every third STOC/FOCS conference, the Knuth Prize is given for outstanding sustained contributions to theoretical computer science. We will find out the next winner at the upcoming FOCS Conference in a couple of weeks.

Every four years the International Math Union awards the Nevanlinna Prize for contributions in "mathematical aspects of information sciences" to a scientist under forty. The previous winners have all been computer science theorists and we have several excellent candidates for the 2006 prize as well.

ACM SIGACT sponsors or co-sponsors several other awards such as the Gödel Prize given to the best recent journal paper (where the definition of "recent" keeps changing) and the Paris Kanellakis Theory and Practice Award given to theorists whose work had practical applications.

Cocktail Conversations

I once met a professor at Chicago that would say "My business is war, and business is good." I have a food scientist friend from college who did his doctorate on starch and had a catch phrase "Everything you eat is healthy, safe and nutritious." But when I start having a conversation with non-scientists it often goes like this:

• Them: "What do you do?"
• Me: "I'm a professor at the University of Chicago."
• "That's neat. What do you teach?"
• "Computer Science."
• (a) "Oh. Excuse me, I see someone I know," or
  (b) "I'm setting up a wireless network in my house.", or
  (c) "I don't use the computers much but my kids are really into it."

I'm sure many of you have had similar experiences. On occasion they will ask me about my research and I will regale them with stories about traveling salesman and Arthur and Merlin, but that rarely goes far. It could be worse, I might have done my research on Hopf algebras.

How do you discuss your research with non-specialists? I'm sure some of you solve this problem by not having any non-CS/Math friends. But if we can't easily discuss our work one-on-one how do we convince the public that our research is important to them and society at large.

Circuit Complexity and P versus NP

In 1983, Michael Sipser suggested an approach to separating P and NP.

One way to gain insight into polynomial time would be to study the expressive power of polynomial-sized circuits. Perhaps the P=?NP question will be settled by showing that some problem in NP does not have polynomial-sized circuits. Unfortunately, there are currently no known techniques for establishing significant lower bounds on circuit size for NP problems. The strongest results to date give linear lower bounds, and it does not seem likely that the ideas there can go much beyond that.

Over the next few years, circuit complexity played a central role in theoretical computer science. In 1985, Yao showed parity required exponential-sized constant-depth circuits, greatly strengthening the bounds given by Furst, Saxe and Sipser. Håstad quickly followed with essentially tight bounds.

Shortly after Razborov showed that the clique function requires large monotone circuits. If we could just handle those pesky NOT gates, then we would have proven P≠NP.

Then Razborov (in Russian) and Smolensky showed strong lower bounds for computing the mod_p function using constant depth circuits with mod_q gates for distinct primes p and q. These great circuit results kept coming one after another. We could taste P≠NP.

But then it stopped. We still saw many good circuit complexity papers and some beautiful connections between circuit complexity and communication complexity, derandomization and proof complexity. But the march of great circuit results toward P≠NP hit a wall after the 1987 Razborov-Smolensky papers. As far as we know today, NP still could have linear-sized circuits and NEXP could have polynomial-sized constant-depth circuits with Mod₆ gates.

Boppana and Sipser wrote a wonderful survey on these results in the Handbook of Theoretical Computer Science The survey remains surprisingly up to date.

Exciting Baseball Ahead

The last week of the major league baseball regular season starts tonight with some tight races ahead. The wild card adds some interesting complexity to the mix (so I can justify this post on the weblog).

My team, the Chicago White Sox (94-61), who have squandered most of their 15 game lead, still leads the Cleveland Indians (92-64) by 2 1/2 games in the AL Central. The White Sox finish the season with three games at Cleveland starting Friday.

Meanwhile the Boston Red Sox (a team many theorists root for since many of us spent time in Boston) are tied with their rivals, the New York Yankees at 91-64 in the AL East. Boston hosts the Yankees for the final three games also starting Friday.

The White Sox magic number is five (White Sox wins + Cleveland losses) to win the division. For the wild card their number is also five (White Sox wins + max(Boston losses, New York losses)). The White Sox get into the playoffs with only three wins since Boston or New York has to lose at least two of their three game series.

White Sox, Red Sox, Yankees, Indians: Three will go to the playoffs. One will end their season.

There are still some races open in the other divisions but it's hard to care, though it will be interesting to see if San Diego wins the NL West with a losing record.

Update 9/29: White Sox have clinched the central division!!! At worse they will be tied with the Indians, but because they will have a better record than any second place team (since the Yankees and Red Sox can't both win the rest of their games since they play each other), there will be no extra game, the White Sox would win the division based on a head-to-head tie breaker and the Indians would be the wild card team. So complex that the Chicago Tribune didn't get it right this morning and the champagne was barely ready in time.

Game Theory

Speaking of names, the associated press released a story yesterday More Colleges Offering Game Theory Courses about new courses on creating video games. CNN originally used this title and has since retitled the article More colleges offer gaming theory courses, and some sites now have the more accurate title More Colleges Offering Video Game Courses.

Many fields have historically bad names (like Computer Science) but Game Theory has a name that invokes an area of study quite different than what it actually does. Bob Soare led the charge to change recursion theory to computability theory with some success. Should the game theory community try to do the same? And what should they call it?

The Price of Freedom?

An anonymous guest post.

I was at a conference this summer where I saw several talks about distributed optimization that used the terms "social optimum" and "price of anarchy". (I believe that Christos Papadimitriou coined these terms.) Most of the speakers that I saw using these terms were European, and I found myself wondering if different terminology would have been chosen if an American theorist had initiated this line of research. (e.g., Nash only named it an "equilibrium"…) What do you readers think?

Egos Needed

I've often heard that scientists have unusually big egos. I don't disagree, egos are a part of being a scientist, a great motivator for us. I still love that feeling when a paper gets accepted in a conference, when someone mentions my name in a research talk or a paper, or that rare moment when the popular press picks up on our research. Even that quiet feeling of self-satisfaction when you find your own solution to a difficult but already solved problem. That need to feed the ego keeps us producing results, trying to please our peers. For better or for worse, it keeps us from doing weird research that no one will understand or follow.

Use your ego for motivation but try to not let it affect your outward personality, difficult to do in a community of strong egos. Sometimes our community even rewards those whose brag about themselves, if they can do so convincingly.

Egos vary dramatically. There must be scientists out there who work purely for the love of science, but I have yet to meet one. And then there are those on the other end of the spectrum. Several years ago, Stephen Wolfram came to Chicago to introduce Mathematica 2 and said "First there was Euclid, then there was Gödel and then there was Mathematica."

Short Takes

Congratulations to Jon Kleinberg, theory's newest genius.

Suresh reports that Tobias Gerken has shown that given any large enough set of points in the plane in general position (no three colinear), six of them form a convex hexagon containing none of the others. That is a geometry theorem even I can understand.

Sanjeev Arora gives an update on the SIGACT funding committee. I foresee very lengthy STOC and FOCS business meetings.

Lisa Randall, Harvard physicist and sister of CS theorist Dana Randall, wrote an op-ed piece in the Times on how scientific terms like "relativity", "uncertainty principle" and "global warming" often give the public the wrong impression of these concepts. Personally I would be excited if the general public knew enough about computational complexity to misunderstand it.

Thanks a Bunch STACS

The STACS conference has ruined my weekend. How? They extended their submission deadline from Friday to today. Why don't I just pretend the deadline was Friday and I would be none the worse off? Co-authors.

The extended deadline let one of my co-authors slack off. Another set of co-authors decided to submit a result to STACS that we probably would have held off for another conference. So I'm spending too much of this weekend reading over and editing papers.

For better or for worse, computer scientists schedule their lives around conference deadlines. It would be best if they weren't moving targets.

Proof

The movie Proof opens today after more than two years after a number of the scenes were filmed at the University of Chicago, some right in Ryerson (home to computer science). The movie got caught up in the Disney-Miramax divorce and is one of a half-dozen movies being released by Miramax before the September 30 separation date.

I saw the play as part of the excursion during the 2002 QIP conference and enjoyed it though I felt the mathematician's life didn't feel right, it went a bit too far on the pressure to produce.

I rarely see non-children's movies in the theaters these days so I probably won't see Proof until it is out on DVD. But let me know what you think about the film (careful about spoilers) and who makes the better mathematician: Jake Gyllenhaal (Proof) or David Krumholtz (Numb3rs).

Anatomy of a Theorem

A comment to Tuesday's post mentions the result

If Graph Isomorphism is NP-complete then the polynomial-time hierarchy collapses.

He gives credit to Schöning but this theorem combines results from a variety of papers.

Goldreich, Micali and Wigderson had a breakthrough paper with three main results.

1. If one way functions exist, every language in NP has a (cryptographic) zero-knowledge proof,
2. Graph Isomorphism has a statistical zero-knowledge proof (where the verifier learns nothing except that the graphs are isomorphic in an information-theoretic sense), and
3. Graph Non-Isomorphism has a bounded-round interactive proof.

It's the last result that we need. The protocol is rather simple.

Input: (G₁,G₂)
Verifier: Pick i∈{1,2} and a permutation π of the vertices uniformly at random. Let G=π(G_i).
Verifier→Prover: G
Prover→Verifier: j
Verifier: Accept if i=j.

If the two graphs are not isomorphic a powerful prover can determine which graph the verifier originally chose. If the two graphs were isomorphic the prover would only have a 1/2 probability to getting the answer right. We can lower the error with parallel repetition.

This protocol requires private coins that the verifier can flip but the prover can't see. Goldwasser and Sipser show how to convert any private-coin protocol to a public-coin protocol where the verifier flips the coins in front of the prover.

Babai and Moran show how to take any bounded-round public-coin protocol and create an equivalent protocol where the verifier flips random coins and the prover responds, the class AM.

Boppana, Håstad and Zachos (which combined two earlier papers) show that if co-NP is contained in AM then the polynomial-time hierarchy collapses to the second level.

Putting it all together, if graph isomorphism is NP-complete then graph non-isomorphism is co-NP-complete and we have co-NP in AM implying the hierarchy collapses.

Schöning gives a self-contained proof and shows that graph isomorphism is in the low hierarchy.

In my first STOC paper I show that for any language that has a statistical zero-knowledge proof, there is a bounded-round interactive proof for the complement of that language. Running through the same set of papers as above one gets that if NP-complete sets have statistical zero-knowledge proofs then the polynomial-time hierarchy collapses.

Jonathan and Me

My brother is out in California co-producing a movie Certifiably Jonathan, a quasi-documentary about Jonathan Winters. The basic story: Jonathan Winters loses his sense of humor and visits a number of comedians (such as Robin Williams and Rob Reiner) to help him get it back.
When I was out in California in August, I had the opportunity to watch a filming of a segment of the movie. Howie Mandel decided to take Jonathan to the Target because you can find anything (including a sense of humor) at the Target. I watched as Howie and Jonathan first met where Howie had this look of awe while talking to his idol. For the film they drove around the store in the handicapped carts making some pretty funny jokes along the way.
Afterwards I had lunch with Jonathan and the crew from the movie which was where the picture above was taken. Jonathan spent most of the time telling stories of his youth, sometimes sad but always in a funny way.
I know many of you readers are too young or foreign to know who Jonathan Winters is. But for an American of my generation it was great fun to meet and talk to one of the funniest people alive.

Favorite Theorems: NP-Incomplete Sets

August Edition

In the 1950's Friedberg and Muchnik independently showed there existed computably enumerable but non-computable sets that are strictly weaker than the halting problem. How about a polynomial-time version? We have some natural sets that are good candidates like Factoring and Graph Isomorphism but no proofs that these sets lie in-between P and NP. Any proof would imply P≠NP and Ladner, in a theorem that now bears his name, shows that P≠NP is the only assumption you need.

Richard Ladner, On the Structure of Polynomial Time Reducibility, JACM 1975.

Ladner shows that if P≠NP there exists an A such that

• A is not in P,
• A is in NP, and
• A is not NP-complete.

Here is my write-up of two proofs of this result, one due to Ladner and the other to Russell Impagliazzo. Ladner proves a more general result, given any computable sets A and B with B reduces to A but A does not reduce to B, there is a set C such that B reduces to C and C reduces to A and A does not reduce to C and C does not reduce to B. This result holds for any reasonable notion of resource-bounded reduction, and in fact you can embed any partial order between B and A.

Ladner's proof works by blowing holes in SAT using a clever looking-back technique to keep the set in NP. In the end it is a little unsatisfying because from the viewpoint of any fixed length, the set is either NP-complete or easy on that length. Impagliazzo's proof tries to get around this by slowing down the reduction but his proof still leaves large gaps of easily computable inputs. But until we learn how to show P≠NP we won't have any other method for proving the existence of incomplete sets.

Comments on Comments

If you only read these posts, say through the mailing list or a newsreader, then you miss the best writing on this weblog—the comments. Take some time (and it will take some time) and read through the comments of last Monday's post SODA Rising.

Otto von Bismarck said "If you like laws and sausages, you should never watch either one being made." The same could go for a conference program. With some notable exceptions, great papers will be accepted, lousy papers will get rejected. But the majority of submissions fall into a middle range where decisions get made by the tastes of the program committee, not only in area but on whether to emphasize deep techniques versus importance and usefulness of the result. Different PCs make very different decisions and one shouldn't make any conclusions about how one paper fares in different submissions.

On the purpose of STOC and FOCS: STOC started in 1969 because the Switching and Automata Theory (SWAT) conference had too much switching and automata theory and not enough of the newly growing areas of complexity and algorithms. Eventually SWAT became FOCS and followed suit. The only official role they have today is to be the flagship conferences of two theory societies, ACM SIGACT (STOC) and the IEEE-CS TC on Mathematical Foundation of Computer Science (FOCS). What purpose do they play now in a diverse theory community is a good but not well-answered question. So we have kept the status quo where, except for adding parallel sessions, have followed the same basic model since the 60's.

As a commenter has pointed out, the accepted papers list of the upcoming SODA Conference came out last week. I'll leave it to bloggers who care more about algorithms to talk about the good papers there.