Using Mobius numbers for a lower bound

I have occasionally seen some comments on this blog as to how one can never know too much math. To support this statement, here is an example of a beautiful application of math to proving lower bounds.

Given n numbers, the k-equal problem must decide whether there are k numbers which are equal. When k=2 this is the classic element distinctness problem, and when k>n/2 this is a classic exercise. What is the complexity of the problem for general k? In 1992 Bjorner, Lovasz and Yao proved a lower bound of at least a constant times n*log (2n /k). Here is an executive summary (summarized from Bjorner and Stanley's paper, A Combinatorial Miscellany).

From computational complexity to algebraic topology: Each equation x(i1)=x(i2)=...=x(ik) defines a (n-k+1) dimensional subspace. Removing all these subspaces defines a space M, and it can be proved that the complexity of the k-equal problem is at least logarithmic in b(M), the sum of the Betti numbers of M.

From algebraic topology to combinatorics: Let P(n,k) denote the partial order whose elements are the partitions of {1,2,...,n} whose parts all have size either equal to 1 greater than or equal to k, ordered by the "merging" partial order. A combinatorial formula of Goresky and MacPherson implies that b(M) is at least the absolute value of m(n,k), the value of the Mobius function of the set {1,2,...,n}.

Definition: Given a partial order with a bottom and a top element, the Mobius function is defined recursively by: m(bottom element)=1 and m(x) is the sum, over every y less than x, of -m(y).

Enumerative combinatorics: As it turns out, m(n,k+1) can be expressed in terms of the complex roots of the polynomial 1+x+x^2/2!+...+x^k/k! From this, for k fixed and n variable, one can prove that there is a subsequence of m(n,k) which grows quickly enough to prove the stated lower bound.

Comments page (Usual comments link does not work properly, use this instead.)

Claire

Refereeing: Go with your Guts, or Let Reason Rule?

My usual way to review conference submissions is to ask myself a few standard questions:

1. What is the problem being studied? Is it motivated in a compelling manner, by either practical or theoretical considerations? New problems warrant more careful scrutiny.
2. What is the result? If there are several results, usually I only look at the main result and evaluate the paper based solely on its best result.
3. Is the proof clever or difficult? Can I identify the key idea, and is it novel?
4. Finally, I give the paper a bonus if it is particularly well-written and a big malus if it is particularly poorly written, especially if the authors are all well beyond their student years - I get impatient with them, and think to myself that they should know better.

At this point in my career, this is usually all fairly routine. However, as Daniel Dennett suggests: "Perhaps our approximation of a perfect Kantian faculty of practical reason falls so far short that our proud self-identification as moral agents is a delusion of grandeur. " I was recently given a paper to review for a conference, and something strange happened. Based on my usual criteria outlined above, I sent to the program committee a mild recommendation for rejection and promptly put the submission in the trash. But instead of instantly forgetting about it, I kept remembering bits and pieces of it and found myself trying to reconstruct parts of the proofs. After a couple of days, it dawned on me that, even though the submission did not pass the filter of my "objective" criteria, still, I was interested in it and actually liked it!

I wonder what one should do in that case. Should you trust your instinct, or obey your evaluation rules? Go with your Guts, or Let Reason Rule?

Comments page (Usual comments link does not work properly, use this instead.)

Claire

Gin and vermouth

Here is a puzzle from Schelling's book, Micromotives and Macrobehavior:

You have a glass of gin and a glass of vermouth. You lift a tablespoon of gin and pour it into the vermouth. You then take a tablespoon of the liquid in the second glass, vermouth with some gin in it, and transfer it to the first glass. Which is now the greater quantity, vermouth in the gin glass or gin in the vermouth glass?

Comments page (Usual comments link does not work properly, use this instead.)

Correlation Clustering

Last year Ailon, Charikar and Newman designed a very simple algorithm for correlation clustering. Suppose you have a set S of n data items, and for each pair of items, you know whether they are similar or dissimilar. How do you partition S into clusters according to similarity? Ideally, any two similar items should be in the same cluster and any two dissimilar items should be in different clusters. This is not always possible: for example, with three items a,b,c, if a and b are similar, b and c are similar, but a and c are dissimilar, there is no way you can cluster them satisfactorily (call this an inconsistent triangle). In correlation clustering, one aims to find a clustering minimizing the number of disagreeing edges.

The algorithm is wonderfully simple: pick an item at random, form a cluster consisting of that item and of all the items which are similar to it, remove the items of that cluster from S, and recurse.

The analysis is wonderfully simple. If you just picked item a, you will create a disagreement on edge {b,c} exactly when triangle abc is inconsistent. For any inconsistent triangle abc, let A(ab,c) denote the event that a,b,c all stay together in S until a is the vertex chosen at random by the algorithm, and let p(bc,a) denote its probability. The expected cost of the algorithm is exactly the sum over inconsistent triangles abc of p(ab,c)+p(ac,b)+p(bc,a). So, if we write q(abc)=p(ab,c)=p(ac,b)=p(bc,a), the cost is 3 times the sum of q(.) over all inconsistent triangles.

Notice that A(ab,c) and A(ab,d) are disjoint events. Thus the sum over c of p(ab,c) is at most 1. So, q defines a fractional packing of inconsistent triangles, and any clustering will have cost at least equal to the sum of q(.) over all inconsistent triangles. This proves that the algorithm is a 3-approximation.

This result is perhaps not a great leap forward in our understanding of TCS in general, but it is a very beautiful illustration of linear programming duality, a little gem of simplicity and elegance that is a pleasure to look at.

Comments page(The usual comments link does not work properly.)

Claire

Funding

Hi, this is Claire Kenyon and I am the guest blogger while Lance is away. I have spent the last few weeks traveling and have heard many US academics express worries about possible pending money troubles. The precarious state of NSF funding is on everyone's mind. Like everybody else I know, I have sent a proposal in answer to NSF's last call for grant proposals in TCS, and I am now considering what the next step should be if it does not get funded. What alternative is there to NSF funding? I have asked this question to a few colleagues and have yet to hear a promising answer. However, I found the answer yesterday on my flight to Berkeley, reading the Kinsella best-seller, Confessions of a Shopaholic: "There are two solutions to money troubles. C.B., or M.M.M. -- Cut Back, or Make More Money." To know how to Cut Back, we can look at our less wealthy sister discipline, Math, for inspiration. For example, we could bypass conferences and submit our results directly to journals.

Comments page (Usual link does not work properly.)

Flying Away with No Water

Next week I am on vacation and off the Internet. Claire Kenyon will be your guest blogger.

I get to experience the new airline rules, no water, toothpaste, gels and liquids of most any kind. The US government is being a bit over reactive but they were only two possibilities

• They can over react to the news and cut back restrictions later as they can more accurately understand the risk factors.
• They can possibly under react where the world learns about a new method to attack planes and the US doesn't try to prevent that new threat.

At least the planes are still flying, the rest are just comfort issues.

A Predictions Markets Mess

The prediction market exchange Tradesports have themselves a little controversy over North Korean missiles.

I have written about prediction (or information markets) before. Consider some future binary event like whether Hillary Clinton will be the democratic nominee for president in 2006. One can create a security 2008DEM.NOM.CLINTON that pays off $100 if Clinton wins the nomination and $0 if she doesn't. Then allow trading on the security including selling short. The price of the security will correspond to the probability that the event will occur, and studies have shown that these probabilities predict better, in general, than experts and polls. Tradesports has such a security on Clinton and the price as I write this for 2008DEM.NOM.CLINTON is 41.9 indicating Clinton has a 41.9% chance of winning the nomination.

Tradesports had another security N.KOREA.MISSILE.31JUL that would pay off if North Korea launces a test missle that leaves North Korean air space by July 31. As you might remember, North Korea did fire test missles on the fourth of July. So it seems like the security N.KOREA.MISSILE.31JUL should have paid off at $100.

Here's the rub. The fine details of the contract required that the US Department of Defense verify that the missiles left North Korean air space. Tradesports couldn't get the verification so they expired the security at $0.

Those who predicted the North Korean missile launch lost real money on a technicality which risks the accuracy of these markets. They no longer predict whether a launch occurs, just whether the DoD would acknowledge it.

More on the Freakonomics Blog.

Missile Season

Eldar Fischer reports from Haifa.

Truth be told, the beginning of the missile season was a surprise for us all. It is true that enough people can claim to have seen it coming, but there was nothing special or expected in the date it started. One day it was business as usual at the Technion and the next day it wasn't.

Haifa has it better than most of northern Israel. We need to stay indoors at all times, and go to the reinforced rooms when we hear the alarm several times a day (our faculty building has a couple of such rooms in every floor, as any post-1992 building is required to have in Israel). Haifa gets hit with actual missiles several times a week—my father told me that it is not unlike the air-raids on Tel-Aviv that he remembers from the 1948 independence war. There are cities to the north that have it much worse, in which life over ground has practically ceased.

All academic interaction with undergraduate students has stopped, as having a concentration of so many people under one roof is deemed to be an uncalculated risk. There will be much work to do when the aborted semester-end tests are resumed and shoe-horned into what is left of the schedule. For graduate student the decision is more personal. Some of them have joined the masses of Haifa residents that have left town (parking space in Haifa has never been so abundant), and others have stayed. A good many of the undergraduate and graduate students (including one of mine) have been called to active reserve military duty, and we all hope they will come back safely.

Faculty members have faced a decision similar to that of the graduate students. Some have taken their work elsewhere (August is considered a good month for academic visits and traveling also in peaceful years), and others like me have stayed. Research at the Technion has not stopped. Thinking is turning out to be possible also in varied settings, and where needed email is taking the place of personal communication. It is not the same as when the hallways were lively with people, but research is done and you can expect good things from the Technion in the upcoming conferences.

Confessions of a Quantum Computing Skeptic

Will we ever have useful quantum computers? Despite the "breakthroughs" we seem to have nearly every month, we are a long way off from controlling even a handful of quantum bits certainly not the tens of thousands of qbits one needs for any meaningful computation.

But I'm not a physicist or an engineer and suppose we can overcome these obstacles and actually build a working machine. Then I can imagine the following conversation in 2025:
Quantum People: We now have a working quantum computer.
Public: Yes after 30 years and 50 billion dollars in total funding. What can it do?
Q: It can simulate quantum systems.
P: I'm happy for you. What can it do for the rest of us?
Q: It can factor numbers quickly.
P: Yes, I know. We've had to change all of our security protocols because of your machine. Does factoring have any purpose other than to break codes?
Q: Not really. But we can use Grover's algorithm for general search problems.
P: That sounds great! So we can really solve traveling salesperson and scheduling problems much faster than before?
Q: Not exactly. The quadratic speed-up we get from Grover's algorithm isn't enough the offset the slow-down by using a quantum computer combined with error correction. But we can solve Pell's equation, approximate the Jones polynomial and a few other things very quickly.
P: Are those algorithms particularly useful?
Q: No.
P: They why did you build a quantum computer?
Q: Because we could.

Optimism and Patience

When looking for a long-term partner, you may have had a long string of failed dates, but you must remain optimistic that the next one will be "the one." You must also have patience to let a relationship develop before giving up and moving on.

The same advice holds for proving theorems. When trying to prove a difficult result, particularly a well-studied open question, it often seems some evil deity finds ways to foil your many proof attempts just as they almost seem to work. Don't give up. Remain optimistic that you can prove this theorem and keep the patience trying new approaches even as each approach gets cruelly shot down. Only when you've exhausted all of your ideas should you move on to the next result.

Over the years I have kept my optimism about proving a result, but I haven't had as much patience as earlier in my research career. Partly because as one gets older one gets more non-research responsibilities both at the university and in the community, though this is more an excuse than a reason. I also find it more difficult these days to focus on a single problem for hours or days at a time.

Let this be a lesson to young researchers. Don't worry that the older famous researchers have not solved the big open questions; most (but not all) do not have as much patience to focus on a problem and explore as many of the possible proof techniques as well as you can.

Zero-Knowledge Sudoku

Victor has tried and failed to solve the latest Sudoku game and exclaims no solutions exists. His wife Paula has already solved the game. How does Paula convince Victor that a solution exists without giving the solution away?
A Sudoku game is a 9x9 board partially filled out with numbers 1-9.

9

2

3

8

4

1

4

5

6

1

7

6

2

1

9

8

2

5

4

2

9

5

8

3

2

The goal is to fill out the rest of the board with numbers 1-9 such that every row, column and the 3x3 sub-boxes all have exactly one of each digit in them.

1

9

7

6

8

2

3

4

5

6

8

5

3

4

1

9

7

2

4

3

2

7

9

5

8

6

1

4

1

8

7

6

3

2

5

9

5

6

9

8

2

4

7

1

3

2

7

3

5

1

9

6

8

4

9

2

6

5

7

1

8

3

4

4

3

7

2

9

8

1

5

6

1

5

8

3

4

6

9

2

7

Sudoku is an NP problem so Paula and Victor could reduce the problem to graph coloring and use the original zero-knowledge protocol for coloring. Or you can view Sudoku as a graph coloring problem. Here is a way for Paula can do a zero-knowledge proof on Sudoku directly, loosely based on the graph coloring protocol.
Paula goes to a different room than Victor and chooses a random permutation σ of {1,…,9} say σ(1)=2, σ(2)=8, σ(3)=6, σ(4)=5, σ(5)=4, σ(6)=9, σ(7)=1, σ(8)=7 and σ(9)=3. Paula then permutes the solution using σ as such.

2

3

1

9

7

8

6

5

4

9

7

4

6

5

2

3

1

8

5

6

8

1

3

4

7

9

2

5

2

7

1

9

6

8

4

3

4

9

3

7

8

5

1

2

6

8

1

6

4

2

3

9

7

5

3

8

9

4

1

2

7

6

5

5

6

1

8

3

7

2

4

9

2

4

7

6

5

9

3

8

1

Paula then puts each entry into a lockbox (which can be implemented using cryptographic assumptions) and gives the lockboxes to Victor.
Victor can make one of 28 choices.

1. Choose one of the rows.
2. Choose one of the columns.
3. Choose one of the sub-boxes.
4. See the permuted version of the original puzzle.

Paula then unlocks the appropriate boxes. If say Victor picked the third row Paula would reveal

6

5

4

3

1

8

7

9

2

Victor will accept if all of the digits in the row appear exactly once. Note that every possible permutation in the row will occur with equal probability over the choice of σ, so Victor learns nothing about the solution from this question.
If Victor picked the last choice Paula would reveal

3

8

6

7

5

2

5

4

9

2

1

9

8

2

3

7

8

4

5

8

3

4

7

6

8

Victor accepts if this is really a permutation of the original problem. Since the permutation σ is chosen at random again Victor learns nothing about the solution from this question.
Why should Victor now be convinced that a solution exists? If there was no solution, Paula could not find a permutation that causes Victor to accept for all of his 28 choices for the permuted puzzle is just the original puzzle in disguise. If Victor makes his choice at random then he will catch a cheating Paula with probability at least 1/28.
That still gives Paula a possible 27/28 chance of cheating. So repeat the protocol 150 times, each time Paula throws away the unused lock boxes and chooses a new permutation. Paula's chance of cheating in every round is at most (27/28)¹⁵⁰ < 0.5%.
Moni Naor gives a different protocol using scratch-off cards where Paula could never cheat Victor.

Fulkerson Prize

The winners of the 2006 Fulkerson Prize have been announced. The Fulkerson prize is given every three years to up to three papers in discrete mathematics.

• Primes in P, Manindra Agrawal, Neeraj Kayal and Nitin Saxena
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Mark Jerrum, Alistair Sinclair and Eric Vigoda.
• Graph Minors. XX. Wagner's conjecture, Neil Robertson and Paul Seymour.

Great papers all. The Robertson-Seymour Theorem required twenty papers. Roughly it states that any graph property (like planarity) closed under edge contractions and edge and vertex deletions has a finite set of forbidden minors. This result has an interesting consequence that all such properties have a polynomial-time algorithm though there is no known method of constructing the algorithm from the property.

I disagree with Luca and Oded on awards. While theory is a team sport, we do like ways to recognize the very best work and individuals in our field. And awards get us talking about the best work. Even when we don't agree with the winners, the discussions that follow help us understand what we think is important.

By the end of the month we'll know the winners of the Fields Medal and the Nevanlinna prize. The excitement mounts.

Privacy

I have used Gmail extensively as my main email system for a couple of years now. I often get asked about letting Google have access to all my email. Is my email more secure on a machine run by Google or by the University of Chicago? Hint: Which one can my employer read without a court order?

Actually I don't care, I use Gmail because I like the interface and the ability to read my email on any browser on any internet-connected computer.

Computer scientists take as a given that everyone worries about privacy. But in fact, outside of computer scientists and a few other techophobes, most people don't. Google not only has my email but also my calendar and if they ever started Google Money, my financials as well. Nearly every major and most minor transactions I make leave an electronic trace. With the right passwords on the Internet you can see what products I buy, what books I read, what movies I rent. So what?

Best as I can tell worries about privacy come from an inflated notion of self-worth. In reality nobody really cares about your private information. The safeguards we have against privacy, while far from completely secure, are enough to deter people for looking for information that just isn't that valuable. Damage will come from people writing in the open; Something someone is writing in their Myspace account today will come back to haunt them thirty years from now when they run for public office.

I do worry about my information online. I worry that people will could delete my files, assume my identity or steal my assets. However I have the ultimate protection against privacy concerns: If you look very carefully at my email, my calendar, the web pages I visit and the stuff that I buy, you'll truly discover that I'm just a really boring person.

Full Derandomization

What does the complexity world look like if we have hard functions that let us efficiently derandomize? All of the results in this post follow from the following open but reasonable hardness assumption.

There is some language L computable in time 2^O(n) such that for some ε>0, every algorithm A computing L uses 2^εn space for sufficiently large n.

First are the complexity class collapses. As always see the Zoo if some class does not look familiar.

• ZPP = RP = BPP = P
• MA = AM = NP. In particular Graph Isomorphism and all of statistical zero-knowledge lie in NP∩co-NP.
• S₂P = ZPP^NP = BPP^NP = P^NP
• The polynomial-time hierarchy lies in SPP. As a corollary PH ⊆ ⊕P ∩ Mod_kP ∩ C₌P ∩ PP ∩ AWPP

One can also derandomize Valiant-Vazirani. There is a polynomial time procedure that maps a CNF formula φ to a polynomial list of formula ψ_i such that

1. If φ is not satisfiable then all of the ψ_i are not satisfiable.
2. If φ is satisfiable then some ψ_i has exactly one satisfying assignment.

Beyond complexity classes we also get some randomized constructions such as creating Ramsey graphs. In polynomial in n time, we can generate a polynomial list of graphs on n vertices, most of which have no clique or independent set of size 2 log n.

This gives a short list containing many Ramsey graphs. We don't know how to verify a Ramsey graph efficiently so even though we have the short list we don't know how to create a single one. Contrast this to the best known deterministic construction that creates a graph with no clique or independent set of size 2^{(log n)o(1)}.

We also get essentially optimal extractors. Given an distribution D on strings of length n where every string has probability at most 2^-k and O(log n) additional truly random coins we can output a distribution on length k strings very close to uniform. The truly random coins are used both for the seed of the pseudorandom generator to create the extractor and in applying the extractor itself.

One also gets polynomial-time computable universal traversal sequences, a path that hits every vertex on any undirected graph on n nodes. The generator will give a polynomial list of sequences but one can just concatenate those sequences. The hardness assumption above won't put the sequence in log space, though we do believe such log-space computable sequences exist. Reingold's proof that we can decide undirected connectivity in logarithm space does not produce a universal traversal sequence though it does give a related exploration sequence.

There are many more implications of full derandomization including other complexity class inclusions, combinatorial constructions and some applications for resource-bounded Kolmogorov complexity.

On Being Color Blind

In the back of my high school Biology book had a big circle with many smaller circles and I clearly made out the word "color". That was easy I thought until I read the caption

If you see the word "onion" you have normal color vision. If you the word "color" you are red-green color blind.

Being color blind is like living in flatland. You miss a dimension and never notice until someone points it out to you. I grew up making the occasional color mistake but just believing everybody saw green and brown as different shades of the same color.

I have had more official tests that show me fully red-green color blind. I don't see the world in black and white; I don't even have trouble distinguishing red and green. I do see certain color pairs as different shades of the same color: green-brown, blue-purple, red-pink and yellow-orange.

As an undergrad I took a course in computer graphics and they did a demonstration where they showed a colorful picture and then showed three variations where they would turn off one color in each. The instructor said that the original and one of the variations would look the same to a red-green color blind person. Everyone laughed but I went up closely and couldn't tell the two apart.

One day shopping with my wife, she held up two shirts and asked me which one I liked better. They looked identical to me. I claimed she was playing games with me. Now with my knowledge of interactive proofs, I could have tested her: Mix up the shirts behind my back and make her tell me which was which.

My father-in-law is also red-green color blind which means my daughters had a 50% chance of being color blind, a rarity for females. We've tested them and neither is color blind, at least not to the extent that I am.

While color blindness has no cure or fix, it is one of the easiest disabilities to live with. My wife and daughters make sure my clothes match. I have trouble when people give color-coded talks but that doesn't happen often in theoretical computer science. I try to keep colors simple on my own talks and webpages. The Red-Green 3-D glasses don't work for me at all, though the newer polarized 3-D glasses work just fine. I don't usually have trouble at traffic lights but I do have trouble telling blinking red from blinking yellow. If I can't tell from context I just stop, sometimes to the chagrin of the car behind me.

But when I look at art or nature I see one less dimension of colors than most everyone else. I will never know what I am missing.

The Collected Works of Lance Fortnow

In the ancient days of the early '80s when you wanted a copy of a research paper and didn't have it in your library, you sent a stamped self-addressed envelope to one of the authors who would send the paper back to you.

I started graduate school in 1985 as a member of that new-fangled email generation. When I got an email request for a paper, I tried sending a LaTeX file, sometimes getting the response "What am I supposed to do with this? Can't you just send me the paper in the mail?"

But as people became more comfortable with email I got many more email requests for papers, and responding to those requests took some time. When the the web started in the early '90s I set up a page for people to download the papers. I would still get email requests for a while, responding to the request but with a reminder that they could download my papers online. Around 1994, there was a phase shift and I nearly stopped getting any email requests, everyone knew to look for downloads first. Now most researchers put copies of their papers online and shame on those that don't.

I use a now ancient version of bib2html to generate the publications page. It makes for a functional but not very pretty page. I use the same bib file to generate both the webpage and the papers list in my CV.

I tell this story because I made the first major change on my publications page in about ten years. It looks pretty much the same, but I added links in the titles to the official publisher's page for the paper. These pages often give an abstract and if you have permission you can download the "official" version of a paper. If you don't have permission you can still download the unofficial version from my page. The publisher's page also gives you a way to link to an official description of the paper without linking directly to a file, something I like to do when I link to papers in this weblog.

I tried to use DOIs when possible or other permanent links so the links shouldn't go bad. The IEEE and the IEEE Computer Society (publishers of the FOCS and Complexity proceedings) maintain two separate digital libraries with some overlap. When I had the choice I linked to the IEEE-CS version because at the University of Chicago we have access to the IEEE-CS downloads but not the general IEEE.

Many other researchers, for example Salil Vadhan, do far better than me, maintaining their own separate page for each paper and sorting their papers by research area. Those young scientists always showing up their elders.

A Metapost

A German student came up to me during the Complexity conference last week. "The Czechs beat the US in the World Cup"

That game happened a month before. "And the Italians beat the Germans. What is your point?"

"You had said in your weblog that the game would long be forgotten before you came to Prague and I wanted to prove you wrong."

I try to keep my blogger persona separate from my real persona and not talk about the weblog when I have conversations with my colleagues. Occasionally I would start to write something down, "Weblog Fodder" I'd say.

Still others bring up the weblog, usually asking the question about how much time it takes (as opposed to say any comments about the content of the weblog). So people will stop asking me, a typical non-technical post takes me about 15 minutes. The key is to not worry about perfection; people forget the silly or sloppy posts and will be very happy to point out any mistakes I make.

Then there are those who want to watch what they say to me because it might show up in the weblog. I try not to embarrass anyone or reveal personal information, but I do get most of my ideas from regular conversations with people. Anything you say to me is fair game.

Favorite Theorems: The Permanent

June Edition

The permanent of a matrix has a simple form

Perm(A)=Σ_σ a_1&sigma(1)a_2&sigma(2)···a_n&sigma(n)

where A is an n×n matrix, a_ij is the element in the ith row and jth column and the sum is taken over all permutations σ of {1,…,n}.

Very similar to the determinant except without the negations and a 0-1 permanent counts the number of perfect matchings on a bipartite graph. But while we can compute the determinant quickly and easily check if a graph has a perfect matching the permanent turns out to have an apparently much higher complexity.

Leslie Valiant, The Complexity of Computing the Permanent, TCS 1979.

Valiant shows that computing the permanent, even for 0-1 matrices, is #P-complete, i.e., as hard as counting the number of solutions for NP problems.

While an important hardness result in its own right, Valiant's theorem becomes even more important with later work. Toda's theorem implies the permanent is hard for the entire polynomial-time hierarchy. The permanent also has two very important properties:

1. The permanent on n×n matrices is easily reducible to solving the permanent on (n-1)×(n-1) matrices.
2. The permanent is a multilinear polynomial on the entries of A.

Those two facts, combined with Valiant's and Toda's theorems, helped the permanent play a critical role in the development of interactive proofs and in some derandomization results, most notably Impagliazzo-Wigderson and Impagliazzo-Kabanets.

The Science and Art of Computation

Amir Michail writes

I was wondering if you might comment on the history behind the formation of computer science, and in particular, on the subsequent overwhelming emphasis on implementation (studied via science/math), rather than specification (perhaps better studied as an art?).

One might argue that two fields should have formed, analogous to architecture and engineering say.

Sure, the implementation part is important (e.g., efficiency), but what to implement should be equally important.

Sure, there are a few subfields of computer science where people try to come up with new sorts of applications, but I think this is worthy of much greater emphasis, a different undergraduate program, a different research methodology (perhaps not so "scientific," but more like "art"). Moreover, I suspect that completely different sorts of people would be attracted to this field.

The MIT Media Lab is perhaps the best example of what such a field would look like.

Would you make the same arguments about physics or biology? Computer science is foremost a science and trying to understand the nature of computation has its own beauty just like trying to understand the fundamental building blocks of the universe.

Can one teach "what to implement" any more than an art class can teach "what to paint"? Best for us to teach the theory and tools of computation and then let the world find neat ways to use computers as they already have in countless ways.

Going Home

Today I fly back to Chicago ending my three country European tour. During this Complexity Conference I stepped down from my role as chair of the conference (organizing) committee and leave the conference in the very capable hands of Pierre McKenzie. I truly enjoyed running the conference over the past six years, particularly in working with different program committee and local arrangement chairs each year. It is time for another leader, but I will miss this role in the conference that has been so central in my academic career.

Other notes from the business meeting:

Pavel Pudlak and Eric Allender are the new members of the conference committee taking over for Harry Buhrman and Avi Wigderson ending their three-year terms.

This year we decided to discontinue the Complexity Abstract program. The abstract program let people write up a one page abstract on any of their papers and Bill Gasarch (later Steve Fenner) would collect and distribute electronically before the conference. The conference started program back in the 80's when people who didn't have their papers in the conference wanted a forum to announce their results. But now with the ECCC and the arXiv, we no longer need this program.

The 2007 Meeting will be June 13-16 at FCRC with STOC and other conferences. Peter Bro Miltersen will be PC chair. There will not be a joint session with STOC as we had at previous FCRCs though there will be some coordination in scheduling the talks during both conferences. The 2008 meeting will be at the University of Maryland.

Complexity Day 1

The Complexity Conference got underway yesterday with an invited talk by Pavel Pudlak on the connections of Gödel's work and computational complexity. Kurt Gödel was in 1906 is what is now Brno in the Czech Republic.

The next talk "Polynomial Identity Testing For Depth 3 Circuits" by Neeraj Kayal and Nitin Saxena is the first paper in Complexity history to win both the best paper and best student paper awards. The main result showed how to deterministically check whether an algebraic circuit was identically zero when the circuit has depth 3 with bounded fan-in on the top gate. Their advisor Manindra Agrawal was program committee chair but he did take the proper precautions in the discussions of the awards.

We had a reception last night at the Michna Palace in Prague. One young student remarked how one must be the smartest person in the world to prove new theorems. Not at all true. We have different backgrounds, different strengths, different experiences, different views on complexity that sets a situation where I can prove something that someone else would struggle with while they can prove something I would never find. Even if you have a similar background to someone "smarter than you", they don't have time to work on every problem so you can find good ones to work on your own.

Most of all my advice is to not worry about others and just work on your own. Be sure to have fun doing your research because if you are not having fun you won't be successful and you can likely make more money doing something else that isn't fun.

Complexity in Prague

I have arrived in Prague for the Conference on Computational Complexity, my favorite conference as you might guess from the name of the weblog. STOC and FOCS get a broader crowd but many of my fellow researchers from the past two decades come to this conference most years and I enjoy talking with them, catching up with research and with life. Just last night I had dinner with Lisa Hellerstein (a COLT person crashing our conference) and Manindra Agrawal, fresh from receiving his Gödel Prize last week at ICALP in Venice.

Blogging will likely be light this week as the conference keeps me busy and I once again have limited Internet access.

One of the students in Chicago had planned to go yesterday to Israel to work for a month with Eldar Fischer at the Technion in Haifa. He postponed his trip, no so much because of the danger, but because getting to Haifa has become very difficult and the University has temporarily closed. The Technion, aka The Israel Institute of Technology, has by far the largest collection of theoretical computer scientists at any single university. Haifa University also has a nice theory group. We sincerely hope the situation resolves itself quickly and they can return to a sense of normalcy, as normal as one gets in that region.

Principles of Problem Solving: A TCS Response

Peter Wegner and Dina Goldin are at it again. The following is from their Viewpoint article Principles of Problem Solving in the July CACM.

Theoretical computer science (TCS) asserted in the 1960s that Turing machines (TMs)—introduced by Turing to help show the limitations of mathematical problem solving—provide a complete model of computer problem solving by negating Turing's claim that TMs could solve only functional, algorithmic problems. The TCS view ignored Turing's assertion that TMs have limited power and that choice machines, which extend TMs to interactive computation, represent a distinct form of computing not modeled by TMs.

In the 1960s theorists (such as Martin Davis of New York University) adopted the inaccurate assumptions that "TMs completely express computer problem solving" as a theoretical (mathematical) foundation of the computing discipline. The TCS model is inaccurate because TMs express only closed-box functional transformation of input to output. Computation is not entirely mathematical, since broader models of thinking and research are needed to express all possible scientific and engineering questions. Computational problem solving requires open testing of assertions about engineering problems beyond closed-box mathematical function evaluation.

The "Choice Machines" from Turing's paper are just what we now call nondeterministic Turing machines. In Endnote 8 of his paper, Turing showed that the choice machines can be simulated by traditional Turing machines, contradicting Wegner and Goldin's claim that Turing asserted his machines have limited power.

But more importantly Wegner and Goldin misinterpret the Church-Turing thesis. It doesn't try to explain how computation can happen, just that when computation happens it must happen in a way computable by a Turing machine.

I admit the original single-tape Turing machine does not model interaction as Wegner and Goldin state. Nor does the Turing machine model random-access memory, machines that alter their own programs, multiple processors, nondeterministic, probabilistic or quantum computation. But what that single-tape Turing machine can do is simulate the computational processes of all of the above. Everything computable by these and other seemingly more powerful models can also be computed by the lowly one-tape Turing machine. That is the beauty of the Church-Turing thesis.

The ongoing support for rationalist over empiricist modes of thought (despite repeated questioning by some philosophers) suggests that human thinking is inherently more concerned with the rationality of human desires than with the empirical truth of human reasoning. Our empirical analysis of interactive problem solving continues to be criticized by incorrect rationalist arguments about the strong problem-solving power of TMs, which are accepted as the proper form of valid reasoning, even though they were contradicted in 1936 by Turing himself.

We hope you accept that empirical (open) reasoning is often more correct than rationalist (closed) arguments, and that modes of thought about truth and problem solving should promote empiricist over rationalist reasoning, as well as definitive truth over questionable a priori value judgments.

Call me a rationalist then as I continue to hold the belief that no matter how complicated the computational model, we can still use the simple Turing machine to capture its power.

Bouncing a Little French Girl

Those who know me well know my addiction to junk food, often referred to as "Lance Food" during my graduate school days. America has its great variety of such culinary delights like Cheesesteaks and Buffalo Chicken Wings but Europeans do very well on their own going well beyond the omnipresent American chains.
 
In Amsterdam I always go for the Uitsmijter (literally "Bouncer", like at a club), basically an open-faced sandwich with fried eggs on top. I usually go for the Rostbief Uitsmijter and the Ham-Kaas version (Ham and Cheese and the Eggs) can really clog those arteries.
But the Uitsmijter is downright healthy compared to the Porto delicacy Francesinha ("Little French Girl"). One starts with a thick slice of bread then add layers of ham, steak and sausage. Cover with another slice of bread and pour melted cheese on top. Then add the fried egg and smother the whole thing in gravy. Right now Porto is having their Festa da Francesinha by the river where restaurants from all over the city come to offer their versions of the Francesinha.
Luis Antunes says "A little bad food is good for stomach every now and then." After eating a Francesinha at lunch today I'm not sure my stomach agrees.

Useful Information

In our sixth Complexitycast live from Portugal, Luis Antunes talks about the Portugal view of theory, research and of course the World Cup. MP3 (13:26, 2.3MB)

Naming Complexity Classes

How do complexity classes get named? A proposal gets submitted to the Complexity Class Naming Commission (CCNC) which makes sure the class was not already named and the name has not been used before. The CCNC then puts out a Request for Comments to the community. Once the community responds, sometimes giving other suggestions for the name, the CCNC makes a formal recommendation to the Complexity Governing Council. The Council takes a final vote on the name.

If only we were so organized. Complexity classes get their name usually from the authors who invent them or occasionally by a later paper if the first paper didn't name the class or gave it an unmemorable name. Too often researchers will give a temporary name so they can work with a class and then keep that name out of laziness. Maybe I've been guilty of this a few times myself.

I could write several posts on badly named complexity classes. For now let me mention two important ones.

• NP for Nondeterministic Polynomial Time. But "nondeterministic" is not very descriptive. Logically ∃P would be better or PV for Polynomially Verifiable.
• PP for Probabilistic Polynomial Time. Since the error is not bounded away from one-half, the class is not a useful characterization of probabilistic computation. A better name would be Majority-P or just MP. BPP would then get the proper name PP and BQP would be just QP.

Someone asked me how to get their class into the Complexity Zoo. You can submit a proposal to the CCNC or just realize the Zoo is now a wiki and edit it yourself.

Definitions of Advice

When Karp and Lipton showed that if NP had polynomial-size circuits the polynomial-time hierarchy collapses, they also give a general definition of nonuniform complexity.

Let C be a class of languages and F be a set of functions. The class C/F is the set of all languages L such that there exists an A in C and an arbitrary f that maps n to strings with |f(n)| in F such that x is in L ⇔ (x,f(|x|)) is in A

Seems natural but this definition has given complexity theorists headaches for many years. The definition works fine for the applications in the Karp-Lipton paper, but it loses the semantic meaning of complexity classes in general.

In particular consider (NP∩co-NP)/poly. We need an A in NP∩co-NP for the definition above, but note that means we need two NP machines that accept complementary languages even for all possible advice strings, not just the correct one. In our toolkit paper we give a relativized world where NP/1∩co-NP/1 is not contained in (NP∩co-NP)/poly. We don't even know if (NP/poly)∩co-NP is contained in (NP∩co-NP)/poly.

At least we can use the terminology NP/poly∩co-NP/poly to nicely capture the class we want. For other classes like BPP/log we have no such clean notation. Once could make some new notation (someone suggested C//F) but instead we usually just state early on that we are not using the official Karp-Lipton terminology and only require the BPP behavior for correct advice.

Karp and Lipton did nothing wrong. They use a very natural definition that works for their purposes. Unfortunately the natural definition does not match the natural interpretation for all classes and will continue to confuse inexperienced complexity theorists for years to come.

On to Portugal

At noon today, as I was checking into my flight to Porto, Heathrow Airport went quiet, part of a nationwide two-minute memorial for the London bombing victims of a year ago. Machines were turned off and everyone stopped talking and just contemplated. The silence was deafening.

So starts the second leg of my journey, a visit to colleague Luis Antunes. As a commenter mentioned I am in Europe but not going to ICALP next week in Venice despite having a paper there. I greatly enjoy going to conferences and workshops but find them quite exhausting and going to three meetings in a row is more, especially with the large and broad ICALP in the middle is more than I can handle. For those in Venice, enjoy the conference and good luck to Italy in the WC final. Afterwards, come on up to Prague for Complexity.

At the workshop in Bristol, the projector was a bit dim and we had some problems reading some colors, green on the white background and red on a black background. This led to a heated discussion on what backgrounds to use. Harry Buhrman argues for white, as one can see the text best. Any background color can work, as long as you don't use too many different colors for text and carefully choose contrasting colors. Though I find any plain color, especially white, a bit boring. I typically use one of the Powerpoint defaults, which Microsoft has designed to both look pleasant and have good readability.

Complexity and Randomness

The Complexity and Randomness workshop in Bristol has an unusual mix of researchers in random graphs and mixing (the British) and complexity (the rest of us). For example Colin McDiarmid talked about the maximum degree of a random planar graph (Θ(log n)) and Mark Jerrum on Monte Carlo mixing methods, in addition to Irit Dinur on her PCP proof, Oded Goldreich on pseudorandomness and coming up Luca Trevisan on Gowers uniformity and Vijay Vazirani on markets.

I don't go to England much because they don't have many researchers in computational complexity, so I get a rare chance to talk to many of the researchers in this area. These workshops give us a chance for us to tell them about the latest in complexity and I can learn about areas I don't keep up with as much as I should.

Leslie Ann Goldberg gave a neat talk on the hardness of estimating the Tutte polynomial of graphs on a variety of points. I never really learned about the Tutte polynomial; it has some cool properties that for various parameters can count properties of graphs such as number of connected components. Goldberg and Mark Jerrum showed some of the approximations are #P-hard, that is hard for counting solutions of NP problems. We rarely see #P-hardness for approximating as all #P problems can be approximated probabilistically with an NP oracle. The Tutte polynomial is harder to approximate on some negative values because of the cancellations given by negative terms.

England on the 4th of July

I have just started a three week European trip. This week at the Randomness and Complexity workshop in Bristol, next week in Porto, Portugal and ending up at the Computational Complexity conference in Prague.

I will celebrate American Independence Day in the country we declared independence from, and not for the first time. You see many European conferences and workshops around this time. You don't notice Independence Day at all in England, the English being more upset at their lost in Portugal in the World Cup then their loss in an 18th century war.

I'm rooting for Portugal to win against France in the semifinals, since I'll be in Portugal for the final game and also because they are playing the French.

Blogging will be light this week as Internet access is not that easy; the Marriott here charges 15 Pounds/day for wireless access, shame on them.

If you don't normally read comments, the recent post on FOCS accepts has generated a record number of comments for this weblog. Check it out and join in the discussion. Nothing gets the emotions up more than discussing the importance of various conferences.

England on the 4th of July

I have just started a three week European trip. This week at the Randomness and Complexity workshop in Bristol, next week in Porto, Portugal and ending up at the Computational Complexity conference in Prague.

I will celebrate American Independence Day in the country we declared independence from, and not for the first time. You see many European conferences and workshops around this time. You don't notice Independence Day at all in England, the English being more upset at their lost in Portugal in the World Cup then their loss in an 18th century war.

I'm rooting for Portugal to win against France in the semifinals, since I'll be in Portugal for the final game and also because they are playing the French.

Blogging will be light this week as Internet access is not that easy; the Marriott here charges 15 Pounds/day for wireless access, shame on them.

If you don't normally read comments, the recent post on FOCS accepts has generated a record number of comments for this weblog. Check it out and join in the discussion. Nothing gets the emotions up more than discussing the importance of various conferences.

A Super Addiction

New superhero movies like Superman Returns and X-Men: The Last Stand remind me of my one time comic book addiction. As a child, I liked to read superhero comics but they had simple stories of saving the world. As I grew up the stories became less interesting and I stopped reading them. In my senior year of college I had a friend who collected comic books and convinced me to start reading them again as the stories have added some sophistication to them. During my last summer before I went to grad school I read through much of his collection. In my first few years of graduate schools I continued to reach comics voraciously and at one point I used a mail-order service to get 25-30 comic books a month.

At some point I realized that I read the books not so much for enjoyment but to finish before the next month's batch arrived. So I went cold turkey, I stopped reading comics and never went back.

However I had gotten my apartment mate hooked and he decided to take over my subscription. Several years later, this would be the mid-90's, the two of us were walking around and entered a comic book store for old times sake. I saw a rack of new releases and we had a conversation that went something like this.

Me: There's Batman, I thought he was paralyzed.
AM: He got better.
Me: I heard Superman was dead.
AM: He got better too.
Me: And the Flash? I remember when he died.
AM: That's Kid Flash all grown up.
Me: At least Wonder Woman hasn't changed.
AM: Actually that's her mother.

The Chicago Tribune just ran an editorial on Spiderman revealing his identity to the world. No worries, in due time the world will forget.

FOCS Accepts and a Movie

The list of accepted papers for FOCS 2006 has been posted. Since I was on the program committee I won't comment on the papers or the process.

So instead I offer to you this short movie (16 MB, 3:14) using soccer to explain Euclid's theorem that there are infinitely many prime numbers. Part of a new British project science.tv.

Finding a Mate

A female professor once told a story of a student who asked her out on a date. After she politely declined, the student asked her if she could be his advisor. Apparently it is harder to find a spouse than to get a Ph.D.

Which brings me to a question asked by a commenter on my Two Body post: How is a CS grad student to find love?

I get asked this question surprisingly often, even though I have been out of "the game" for nearly two decades. My best advice: Find some activity you like and join a club on or off campus that matches that activity. For example, concert band, contra dancing, running, skiing, sailing, etc. You'll meet other lonely people who share at least one interest with you.

I was never good at bars, clubs and blind dates. People like us don't always make a good first impression; that's why it's best to have an opportunity to make friends over time before asking someone out.

I missed the whole on-line dating scene. I have known some people who have had great success with them and others who haven't. Sunday the Chicago Tribune highlighted a new dating site Geek2Geek. Only for the desperate.

Does it matter whether you date an academic or not? Not really, just find the right person for you. Making a two-body problem is often harder than solving it.

FREE REPRINTS

Bill Gasarch is giving away free copies of one of our papers. Get them while they last.

I recently got in the postal mail REPRINTS of a recently published article of mine. This used to be standard—when an article was published you got 50 free copies. Less and less journals do this now.

Are reprints needed anymore?

NO: With everything online nowadays anyone who wants to find or read your article can.

YES: When someone visits you in your office its nice to be able to give them a copy without having to print it out. Also, when I went up for Tenure and Full Prof, I was asked for 14 copies of every article I ever wrote, so it was good to have the preprints around. (some went to my letter writers, which makes sense, some went to the committee deciding my case, which makes less sense, some went to the dean, provost, and for all I know the governor of Maryland, which makes no sense. Well maybe its okay–the governor has a Ph.D. in Mathematics–it was on Recursive Algebraic Topology. I am, of course, kidding–there is no such field.)

Even before the electronic age I never used reprints much (except when I went up for promotion). And the last few times I've written a letter for promotion I was NOT given the set of papers (NOTE: It would have been an appreciated courtesy if they had).

The article A Tight Lower Bound for Restricted PIR Protocols by Beigel, Fortnow and Gasarch (Computational Complexity, Vol 15, No 1, 2006, 82-91) can be YOURS if you send a Self-Addressed Stamped Envelope to

William Gasarch
Dept of Computer Science
University of Maryland
College Park, MD 20742
USA

(I would bet $5.00 I won't get any takers, except that someone may take the bet and request a copy, thus gaining $4.61)

Favorite Theorems: Probabilistic Complexity

May Edition

After we saw several randomized algorithms for primality we needed a way to classify and analyze the power of probabilistic computation. The power of computational complexity comes from not just studying old models of computation but taking new ones and finding ways to analyze their computational power as well.

Computational Complexity of Probabilistic Turing Machines, John Gill, STOC 1974, SICOMP 1977.  A Complexity Theoretic Approach to Randomness, Michael Sipser, STOC 1983.
Gill gave a formal definition of a probabilistic Turing machine and defined the basic classes, PP, BPP, RP (which Gill called VPP) and ZPP and showed the basic relationships between them.
Sipser's main result showed the BPP is contained in the fourth level of the polynomial-time hierarchy and the paper also includes Gács improvement putting BPP in Σ₂∩Π₂. More importantly Sipser introduced new techniques into the complexity theorists' toolbox including

• A new resource-bounded Kolmogorov distinguishing complexity, and
• Using Carter-Wegman hash functions to focus randomness. Perhaps the first extractor.

Sipser's tools go on to play an important role in the complexity of Arthur-Merlin games, graph isomorphism, statistical zero-knowledge and other areas of complexity. But perhaps most importantly Sipser showed you can apply the tools of complexity to really understand the power a new model of computation, the probabilistic machine. How about that newer model of a quantum computer? Bernstein and Vazirani's paper plays the Gill role, in formalizing efficient quantum computation and definining the basic classes like BQP. But while we have had some limited success in understanding the computational complexity of BQP, not only do we not know whether BQP is contained in the polynomial-hierarchy we have not yet developed great tools for understanding "quantumness" the way Sipser has shown we can do for randomness.

Campus Maps

As an academic I can't count how many different college campuses I have visited. Most US universities produce beautiful glossy maps to make it easy to navigate to and around the university but you can't get one of these maps unless someone mails you a copy. So I go to the university's website and can usually find a page of maps.

The University of Wisconsin map page has a beautiful flash version of their campus map. Someone put considerable time to design such a completely useless map. What am I supposed to do, walk around campus with my laptop open to figure my way around? Wisconsin also has a PDF version of their map but when printed the type is so small the map is also useless. Admittedly Chicago does not do maps much better.

The glossy maps are typically much larger than the usual printer page, but still universities can do better than just creating PDFs of shrunken versions of their usual map. Princeton, has their useless interactive map, but their printed map does a nicer job with a second page having a building directory very useful with a duplex printer.

Some day we will carry portable GPS devices which when we visit a campus will download building information and guide us to where we want to go. Until that day universities should take the effort they use to create fancy interactive maps and instead focus on producing a "print and go" map designed specifically for standard letter-size paper.

The Two-Body Problem

Many professional couples can have problems finding jobs in the same city, but for academics the problem magnifies. Even big cities will have only a small number of computer science faculty positions in major research universities and so try to imagine finding two such jobs. This quandary has a name that started as a joke, but no one laughs at trying to solve their Two-Body Problem.

Finding two open positions in the same department and often in the same area (like theory) can be particularly challenging as departments have a limited number of positions available each year. Still a department can often obtain one or two faculty members they might usually lose to a stronger school by going out of the way to solve a two-body problem.

Two-body problems become even more difficult when one member of the couple is considerably stronger than the other, or they are at different stages of their academic careers. In the latter case the older one might have a tenure-track position and then have to go on the job market again to solve their two-body problem. Even if they eventually do land tenure-track jobs at the same department, they will come up for tenure in different years adding more instability.

How about two academics in different fields? Some universities will go out of their way to accommodate such couples, with a dean or provost encouraging one department to hire in order to help strengthen the other department. Many other universities won't try as hard.

Finally are the couples with one academic and a non-academic professional that also has limited geographical jobs opportunities. Here a university can't help at all, one just needs to get lucky.

By US law, one cannot ask a candidate about the two-body problem when they interview, and if they don't mention it one cannot take it into consideration during the hiring process. Nevertheless you should tell the department about your situation. Universities often have ways of solving two-body problems and letting them know about it ahead of time will give them more time to make the right opportunities available.

In the end most two-body problems do get solved, though not always at the place as good as where they might have received a position on their own.

The H-Number

Thomas Schwentick sends me a link to an h-number calculator maintained by Michael Schwartzbach. Jorge Hirsch developed the h-number or h-index as a measure of the scientific output of a researcher.

A scientist has index h if h of his/her N_p papers have at least h citations each, and the other (N_p - h) papers have no more than h citations each.

The h-index discounts researchers who have one or two highly cited articles or books, or those researchers who just churn out mediocre papers.

There are loads of problems with the h-index. Google scholar and other citations counters are inaccurate because of trouble parsing and disambiguating papers. Citation counts do not accurately measure the quality of the paper—a paper that opens a field will get many more citations than a paper that closes it. The h-index rewards fads and cliques who always cite each others work. The h-index gives greater weights to more senior scientists and doesn't separate those who had good early careers from those still going strong.

Having said that we do love to compare ourselves with our colleagues in any way possible. An automated calculator does not work well for even mildly common names but it works great for "Fortnow" and while my h-index of 23 does not put me among the h-number elite, I'll take it.

EC

This week I'm attending EC '06, The 7th ACM Conference on Electronic Commerce in Ann Arbor. The name does not completely fit the conference which focuses mostly on computer science issues in economic models (e.g. computing Nash Equilibria) and economic question related to computer science (e.g. Internet-related auctions, economic mechanisms that solve algorithmic problems). The conference draws a mostly computer science crowd from both the theory and AI communities. Not many economists and most of those from business schools. Some industry folk come but mostly CS researchers from the big internet companies.

So what is a nice complexity theorist like myself doing at a conference like this? I study the power of efficient models of computation and what is an economic market but just another model of computation.

This year's conference had a big emphasis on sponsored search auctions, those keywords you see on the right side of search results. Yahoo, Google and recently Microsoft all run various auction scheme where companies bid on keywords like "mp3 players." Finding the right models, bidding mechanisms and equilibria for these auctions continue to challenge researchers. EC had four submitted talks, an invited talk, a workshop including a panel, and a competition all on sponsored search.

The conference had no overhead projector, white or blackboards. A laptop powered every talk at EC, the first time I've seen that at any conference. However they still had paper proceedings though did talk about possibly eliminating them at future conferences.

EC broke their attendance records with 172 participants who came to the conference and/or one of the workshops. Next year EC will be at FCRC along with STOC, Complexity and many other conferences.

Incomprehensible implies Boring?

Lawrence Downes writes a New York Times opinion Edison, Unplugged talking about the beauty of listening to music recorded in the 20's and 30's on a cylinder.

And there is another pleasure, too. It's the warmth of the technology. There are surely downloadable versions of "True Blue Lou." But unlike the MP3, whose magic is incomprehensible and thus boring, the wax cylinder is viscerally miraculous. It's staggering to think that lungs and plucked strings could vibrate the air, wiggle a stylus and capture a song for 100 years on a fragile thing that looks like a toilet paper roll. Compared with the iPod, it's a lot more human, a lot more accessible, a lot easier to love.

Downes has it backwards. The cylinder technology is very simple and provides a mediocre reproduction of the original music. Meanwhile the MP3 and other compression schemes use beautiful computer science ideas to make a strong digital copy, easily produced and portable, superior to cylinders in every way.

Luckily Downes is the outlier. He can enjoy scratchy music on his "toilet paper roll" while the rest of us enjoy music that sounds like the original on devices we can carry in our pocket, even if most people don't understand the details of technology involved.

EC, PCs and the WC

Fresh off a PC (Program Committee) meeting in NJ (no tellsies), I drove from IL to MI for EC where I was also on the PC. First I spent the day at TTI with lunch at the GSB to watch the USA at the WC. Thankfully by the time I get to CCC that game will long be forgotten.

Time-Travel Circuits

From Computing Like Gods by Jörn Grote

Time travel circuits had been in the first stages of development, but even then it was clear that we had cracked NP complexity. Before TTCs, solving computational problems from the NP-class in polynomial time was like finding the holy grail. And then we got TTCs. They utilized extremely small wormholes, were one opening had been accelerated near the speed of light.

Computers with time travel circuits could easily solve NP-complex problems in polynomial time, but the limit was actually PSPACE. Time travel was characterized by the computational complexity class of PSPACE, a class of problems that was either bigger or at least as big as the NP class.

When the news were out that they had TTCs, most people had no idea what it meant. I can still remember the headlines TIME TRAVEL IS REAL, WE CAN GO BACK, KILL YOUR GRANDFATHER. Naturally all these articles omitted the fact what we really could do with TTCs. It was cheap and easy to create the extremely small wormholes, but bigger ones grew unstable with rising size. The crater where once had been Calcutta tells you that they had found the limit and surpassed it.

Can Settling P vs. NP Get You Sued?

A reader Osias asks

About purported P vs NP solutions…I was wondering what if you, sooner or later, lets say, 10 years from now, solve yourself the P vs NP question. Can those authors sue you, claiming they have solved and you "stole" it from them?

I am most worried about myself too. Cause I am actually reading those papers from them and contributing to a wiki that analyze them. What if those guys decide to sue me? Can they?

I view this question as an extreme hypothetical. I don't expect either you or I will settle the P versus NP problem nor do I believe any of the papers posted on the wiki will play any significant role in the eventual solution.

We rarely see lawsuits in academics and then only when large sums of money are involved, for example patent rights based on research. The Clay Mathematics Institute Millenium Problems do provide a significant sum of prize money but even in the scenario you outline above, the suit would not be against you but instead the Institute for not recognizing the earlier work.

If I write a paper and later learn of some work that overlaps my paper, I will mention this other work even if I was unaware of it at the time of my research. I could imagine a scenario where I don't believe a paper has any connection to my research and the authors of that paper decided to sue me to acknowledge their perceived contributions. In such a scenario I would not be bullied and hold my ground, though not before consulting the university's lawyers.

On a related note, Luca reports on the status of the Poincaré conjecture, likely to be the first Millenium Problem prize awarded by the Clay Math Institute.

Funding Committee Report

At the STOC Business Meeting Richard Karp gave a report from the SIGACT Funding Committee.

Why does TCS [Theoretical Computer Science] have meager funding and little influence with funding agencies?

A possible answer: Unlike the physicists we have no tradition of leadership within the CS community, setting community goals, and advising, serving and lobbying the funding agencies and congress. For physicists this is a normal responsibility and it should be for us as well.

Ways to get involved include

• Write popular articles.
• Contribute short articles for the SIGACT website.
• Serve on NSF panels and as program directors.
• Provide research nuggets to NSF.
• Advise the committee.

The committee suggested two cross-cutting initiatives, Theory of Networked Computing and Computer Science as a Lens for Science.

Theory of Networked Computing will bring TCS into the NSF GENI Initiative. ToNC has already had some influence in the development of the Scientific Foundations for Internet's Next Generation (SING) area of the recent Theoretical Foundations solicitation.

Computer Science as a Lens for Science promotes algorithms as the language of science in many different disciplines including

• Quantum Computing
• Statistical Physics—Phase Transitions
• Algorithmic Economics and Game Theory
• Computational Biology

Most of all the committee wants community action to help in promoting and supporting TCS.

The Funniest Computer Science Joke Ever

My kids watched one of the Disney Channel sitcoms and I caught the following exchange:

Teacher: Do you want to hear the funniest computer science joke ever?
Student: Sure

Customer: My computer crashes every time I press enter.
Tech Guy: So don't press enter.

Teacher: Now wasn't that the funniest computer science joke ever?
Student: Yes it was.

Not so funny. But also nothing to do with computer science. No wonder my kids sometimes think I fix computers for a living.

The May 1 Deadline

In 1964 the Association of American Universities passed the following resolution setting a May 1 deadline for hiring away faculty from other institutions.

The sharp increase in the demand for teacher-scholars of high talent arising from our growing national needs in both instruction and research is now pressing against a limited supply of such talent in many disciplines. To assure the highest possible effect in each university in producing high talent to meet future national needs, sound and orderly planning will be required. When late and sudden, induced departures of personnel assigned to provide instruction to lead in research in one institution may well do more to impair the effectiveness of that institution than is justified by the gain to the institution extending the offer. This is particularly true at the level of tenure appointments where the institution has declared its willingness to undertake a continuing obligation and where there are most likely to be continuing obligations by the faculty member to graduate students and colleagues.

Therefore we consider it incumbent upon the administrations of both the prospective and current institutions of employment to call the attention of the individual faculty member to these obligations when employment changes, not accepted before May 1 for the immediately ensuing academic year, are under consideration. We believe that a responsible approach for both the institutions and the faculty members would be to consider offers made or pending on May 1, or thereafter, to be effective normally only after the intervention of an academic year.

In practice we are strongly discouraged from making such offers after May 1 but if say Harvard wants to hire away a professor from Yale after May 1 for the following academic year, the provost of Harvard makes a request to the provost of Yale and such requests are almost always granted.

Most fields finish up hiring early in the spring and the May 1 deadline reasonably blocks some last minute shuffles. But as the computer science hiring season often goes into June and junior and senior hires often compete for the same slot the May 1 deadline can create havoc in the CS recruiting process.

The high-demand low-supply of faculty in 1964 no longer holds true today. We need to reconsider whether a one-day-fits-all deadline really applies in today's diverse academic hiring environment.

Beauty and the Bee

Last night my daughters and I watched a New Jersey girl win the National Spelling Bee. The final three contestants were all females though my kids were rooting for the boy from Illinois.

Championship spelling requires considerable memorization as you'd expect but it has a mathematical aspect as well. One needs to know how to put together words using very specific rules that depend often on the word's origins, which the spellers can ask about.

A major network (ABC) broadcasted the spelling bee for the first time. ABC once televised the Miss America Pageant, which has since moved to a small cable station because of lack of viewer interest. Amazing to see Beauty lose to the Bee.

Research with Colleagues Visiting for a Short Time

Another guest post by Bill Gasarch

A colleague is going to visit for a short time and you want to get some research done. When does this work? When does this not work? How to you define `work' anyway? Some advice.

1. Have a well defined topic that at least one of you is knowledgeable about.
2. Have complimentary strengths. Or, more accurately, make sure that several strengths are covered (e.g., one knows Algebra, one knows Geometry, so you can do research in Algebraic Geometry. Well, maybe not...) (Better example: one is a knowledgeable about widgets, and one is clever with widgets.)
3. Don't chit-chat or socialize that much, OR at least have it be during a well defined time. For example AT SCHOOL mostly talk about research. AT HOME (if the visitor is staying at your house) socialize. For this reason, having the visitor at your house is a good idea so long as it makes sense logistically and is okay with the spouse.
4. Avoid long big lunches. You feel sluggish afterwards.
5. Right after you've proven something new you are excited about it. Write it up SOON, while you are still excited. For work with visiting colleagues, make sure that ONE of you is assigned to get out the first draft. (This is true of research in general.)
6. How long to stay? Too long can be bad since then there is the temptation to put things off. About a week is good. If someone is visiting for a semester than this is a whole different story, which someone else may blog on.
7. One goal of a collaboration working is that a paper is produced. Other goals could be that you both learn something you didn't know before.