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.

Do Wikis Work?

John Stockton put a wiki version of the Complexity Zoo on the Quantum physics Qwiki. For those not up on the nomenclature, a wiki is a specially designed web page that anyone can change usually with mechanisms for tracking and undoing those changes if necessary. Ideally a wiki will allow the zoo to remain up-to-date without continual intervention from Scott. But will it work?

The Wikipedia has a number of entries for various complexity classes. I generally find them for the most part accurate but not complete. Take for example the NL entry which doesn't note that NL is closed under complement but instead has the misleading result that RL=NL (where one allows the randomized machine to have infinite computation paths). Sure I could fix the entry in wikipedia but there are at least two problems:

• There aren't enough people in the field who have the time and patience to go through all the entries and update them.
• I firmly believe RL should be what Wikipedia calls RLP. But what right do I have to impose my naming conventions on the whole wikipedia universe.

Sanjeev Arora and Boaz Barak set up Theory Matters as one big wiki. Boaz once said the following in a weblog comment.

Don't give "theorymatters.org" as an example to a place that ignores area X. It's a Wiki - if you don't add the material yourself no one will do it for you.

But people are reluctant, for whatever the reason, to edit the wiki. Outside of the "Survey Collection" you can nearly count the number of contributors to the wiki on one hand.

In short wikis, like anything else on the web, can be a good source of information but are often incomplete sometimes in important ways. Just because anyone can edit a wiki doesn't mean that they do.

P/poly

A student asked me why P/poly was an interesting class? A very interesting class with a funny name. It combines time and program-size complexity, and characterizes non-uniform efficient time and languages with small circuit complexity.

Here are two equivalent definitions of P/poly.

• A language L is in P/poly if there is a language A in P and a set of advice strings {a₀,a₁,…} such that |a_n|≤n^O(1) and x is in L if and only if (x,a_|x|) is in A.
• There is a family of circuits {C₀,C₁,…} such that |C_n|≤n^O(1) and for all n and all x=x₁…x_n, x is in L if and only if C_n(x₁,…,x_n) accepts.

The equivalence comes from Ladner's proof that the circuit value problem is P-complete. Some argue that P/poly is a better notion of efficient computation than P since we allow the program size as well as the time to grow as the input grows. Techniques from Adleman show that BPP is contained in P/poly. However P/poly contains noncomputable and in fact an uncountable number of languages

Here are just a few areas where P/poly plays a crucial role.

• Combinatorial Approach to P versus NP: Karp and Lipton show that if NP is in P/poly then the polynomial-time hierarchy collapses. So one approach popular in the 80's to show P≠NP tried to show an NP problem did not have polynomial-size circuits. Razborov shows the clique problem did not have polynomial-size monotone circuits.
• Derandomization: Nisan and Wigderson show that hardness against nonuniform classes can give us pseudorandom-number generators. Building on their work, Babai, Fortnow, Nisan and Wigderson show that if EXP is not in P/poly then BPP can be simulated in subexponential time on infinitely many input lengths.
• Cryptography: Often security is defined against P/poly adversaries to capture extraneous information in the system.
• Learning Theory: Learning polynomial circuits would be the Mecca of learning theory. Can't be done in the usual models unless factoring is easy. Bshouty et. al. show we can learn circuits probabilistically with an NP-oracle and hypothesis queries.

FOCS

From Anupam Gupta

A favor: the FOCS conference registration site is open; could you put up a small post on your blogs letting people know this, along with the fact that the advance registration deadline is September 23rd?

I did send mail to theorynet and dmanet, but clearly blogs are where the action really is.... :) thanks a ton, gents!

Done but my readers shouldn't count on the weblogs to tell them when to register or submit papers. Subscribe to DMANET or Theorynet, check the Theory Calendar or, most reliably, Google the conference to find out the appropriate deadlines.

SODA Rising

As theoretical computer science grew during the past twenty years, the general theory conferences STOC and FOCS could no longer present all of the good papers in theoretical computer science and a number of smaller specialized conferences arose, for example Computational Complexity, Learning Theory (COLT), Computational Geometry (SoCG) and many others. But one of these specialized conferences, the Symposium on Discrete Algorithms (SODA) has grown larger than STOC and FOCS both in submissions and attendance. Perhaps this should not be too surprising in that algorithms is a broad area and there is only one SODA each year and two STOC/FOCS conferences.

Recently though I've seen a few circumstances where SODA gets mentioned in the same breath as STOC and FOCS as an equal. For example, the SIGACT Home Page lists the upcoming FOCS, STOC and SODA conferences. OK, SIGACT co-sponsors SODA but the bottom of the upcoming FOCS Home Page (side note: Early Registration Deadline Sept. 23) list the previous FOCS, STOC and SODA pages. FOCS is an IEEE conference with no official connection to SODA. Finally Cathy McGeoch is trying to set up a hockey game at an upcoming FOCS, STOC or SODA conference. Can you have a true TCS World Cup with just algorithms people?

Are SODA papers getting the same prestige as STOC and FOCS papers? Not yet but we are heading that way. Is it truly a good thing to move from a STOC/FOCS/specialized conferences system towards a STOC/FOCS/SODA/other specialized conferences system?

Questions About Crypto

Bill Gasarch wants your help to judge a new book.

I am reviewing Encyclopedia of Cryptography and Security for a future SIGACT NEWS book review column. I will review it by asking various people for THINGS THEY WANT TO KNOW ABOUT from such a book, then I look them up, and see how the book does. (ease of finding it, value of information, etc.)

So, I request that you EMAIL me (gasarch@cs.umd.edu) a question that you would like to see in an encyclopedia of Crypto and Security.

If you know someone who probably doesn't read this blog but has good questions (e.g., a colleague working in Systems who works on security) pass this on to them.

Hard Times for the Big Easy

I have been to New Orleans twice. First for the 1991 STOC conference which overlapped the Jazz and Heritage festival. Then again in 1994, one last fling when my wife was pregnant with our first child. We went to the French quarter for crawfish and listened to Jazz at Preservation Hall, took the trolley down St. Charles Avenue, got our baseball fix with the New Orleans Zephyrs AAA team (the major league teams were on strike) and saw the Mother's Day Parade ("Mother" being a famous New Orleans transvestite).

Now this famous city lies mostly flooded, one of the victims of Hurricane Katrina. A major city, which has hosted many Superbowls and the biggest party in America in the days before lent, lies devastated by the hurricane, not to mention the tremendous damage in other Gulf Coast communities. With the tsunami last December, nature has not been kind to us this year.