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.

--
Posted by Lance to Computational Complexity at 9/01/2005 07:10:00 AM

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

--
Posted by Lance to Computational Complexity at 9/02/2005 07:18:00 AM

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?

--
Posted by Lance to Computational Complexity at 9/05/2005 06:12:00 PM

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!

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.

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.

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.

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.

--
Posted by Lance to Computational Complexity at 9/08/2005 05:44:00 PM

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.

--
Posted by Lance to Computational Complexity at 9/11/2005 10:14:00 PM

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.

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.

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.

--
Posted by Lance to Computational Complexity at 9/12/2005 08:18:00 PM

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.

--
Posted by Lance to Computational Complexity at 9/13/2005 09:02:00 PM

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.

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.

--
Posted by Lance to Computational Complexity at 9/14/2005 08:31:00 PM

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

--
Posted by Lance to Computational Complexity at 9/16/2005 05:54:00 AM

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.

--
Posted by Lance to Computational Complexity at 9/18/2005 09:50:00 AM

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 even 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 principal" 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.

--
Posted by Lance to Computational Complexity at 9/20/2005 08:33:00 AM

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."

--
Posted by Lance to Computational Complexity at 9/22/2005 10:31:00 AM

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?

--
Posted by Lance to Computational Complexity at 9/23/2005 11:55:00 AM

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?

--
Posted by Lance to Computational Complexity at 9/24/2005 12:49:00 PM

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.

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.

--
Posted by Lance to Computational Complexity at 9/26/2005 05:13:00 PM

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.

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.

--
Posted by Lance to Computational Complexity at 9/27/2005 05:57:00 PM

• 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."

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.

--
Posted by Lance to Computational Complexity at 9/29/2005 05:57:00 PM

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.

--
Posted by Lance to Computational Complexity at 10/02/2005 09:26:00 AM

Pressing the buttons failed to quiet the device, so I attempted to open the until 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.

--
Posted by Lance to Computational Complexity at 10/03/2005 01:07:00 PM

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

--
Posted by Lance to Computational Complexity at 10/04/2005 09:04:00 PM

• 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.

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.

--
Posted by Lance to Computational Complexity at 10/05/2005 10:07:00 PM

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.

--
Posted by Lance to Computational Complexity at 10/06/2005 05:55:00 PM

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.

--
Posted by Lance to Computational Complexity at 10/08/2005 11:38:00 AM

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

Usually we think of the class NP as either languages accepted in polynomial-time by a nondeterministic Turing machine or languages with polynomial-time verifiable witnesses. Ronald Fagin gives a characterization of NP based on logic without references to Turing machines or polynomial time.

Ronald Fagin, Generalized first-order spectra and polynomial-time recognizable sets. Complexity of Computation, ed. R. Karp, SIAM-AMS Proceedings 7, 1974, pp. 43-73.

In this paper Fagin shows that NP consists of exactly the languages expressible with existential second-order formulas. For example consider a graph G described by an edge relation E(i,j) and we can define whether G is k-colorable by

With some more work you can use binary predicates. In general every language in NP has an existential second-order characterization with binary predicates and a universal first-order part.

Stockmeyer generalizes Fagin's result to characterize the polynomial-time hierarchy with second-order formulas.

Fagin's result started the area of descriptive complexity that characterized many common complexity classes in various logics and has connections to the complexity of database queries. Neil Immerman's work in descriptive complexity led him to his proof that nondeterministic space is closed under complement. Robert Szelecpsényi independently came up with a similar proof through a different approach.

Papadimitriou and Yannakakis use Fagin's result to characterize the class MAX-SNP of optimization problems. One of the first corollaries of the PCP Theorem is to show the MAX-SNP hard problems cannot be approximated within an arbitrary constant unless P=NP. In fact the concept of probabilistically checkable proof itself originally comes from a second-order view of NP that originated from Fagin's paper.

--
Posted by Lance to Computational Complexity at 10/10/2005 04:45:00 PM

Which one of us is keeping the crazier hours?

--
Posted by Lance to Computational Complexity at 10/12/2005 07:23:00 AM

In the olden days (circa 1990), we all wrote our LaTeX papers using the Computer Modern font. When we sent a paper to a proceedings we printed up a clean copy and sent it via Federal Express.

Now we have choices of fonts. Fonts are a surprisingly complicated process. A good font is a work of art and a scalable font is actually a computer program for each letter. If you intellectual property issues for digital music is complicated, IP for typefaces is nearly impossible to implement well.

When some societies like the IEEE first started taking electronic uploads for their proceedings we would get the occasional disastrous effects because the IEEE fonts didn't match the fonts people used to create a paper. For example the "<" would appear as a "⇒" making some of the papers unreadable. Most of these organizations have become more aware of this issue but now require us to jump through some hoops (use the right fonts and style files and putting the paper in the appropriate format using the right program to do so). Makes me wish for the old days when I could send a paper and they would scan it, which the IEEE will still do but charge extra for.

Sometimes you'll see "¿From" in older papers. This is not a font problem but a property of sending text files through email would add a ">" to a line beginning with "From" which would come out "¿From" after LaTeX processed the file. You see it less now as files get sent via attachments instead of directly in the mail body.

Distractions from worry about something as minor as fonts really keeps us away from focusing on research and other important activities. Remember, no one was ever denied tenure for bad font selection.

--
Posted by Lance to Computational Complexity at 10/13/2005 10:05:00 PM

I doubt the content of the weblog or its existence or popularity played negatively towards his tenure case. Perhaps some feel his time would have been better spent on "real academics" but most likely they considered his more traditional academic writings and, frankly, it's very difficult to get tenure at the U of C, particularly in the social sciences.

Will Drezner's weblog help him in his future job hunt? Ivan Tribble argued that weblogs can hurt a candidate for an academic position.

The content of the blog may be less worrisome than the fact of the blog itself. Several committee members expressed concern that a blogger who joined our staff might air departmental dirty laundry (real or imagined) on the cyber clothesline for the world to see. Past good behavior is no guarantee against future lapses of professional decorum.