Phillipe Flajolet passed away

Today I read on Lipton's Blog that Phillipe Flajolet passed away (1948-2011). Flajolet worked in Analytic Combinatorics. His book with Sedgewick on the field (see this review) practically defined the term Analytic Combinatorics.

Most of the math we use in Theoretical computer science is discrete math. However, analytical mathematics is also useful and I wonder if its potential has been fully tapped yet. Here) is an example: a paper by Flajolet that uses Complex Analysis to show that certain context free languages are inherently ambiguous.

I am teaching 30 students a course on Formal Language theory now and I suspect that less than 3 know any complex analysis. I suspect that in earlier times more would have. I do not miss those times; however, it means that results like the one cited above cannot be taught.

An unusual Voting Scheme

(I want to thank Bobby Kleinberg for bringing this to my attention.)

Consider the following voting scheme

1. Choose a random person A₁.
2. A₁ chooses a set at random of 30 people. Call the set A₂.
3. Choose a random set of 9 from the 30 in A₂. Call this set A₃.
4. The members of A₃ pick a set of 40 people. This is NOT random. In fact, every person they choose must be approved by at least 7 of the 9. Call this set of 40 A₄.
5. Choose a random set of 12 from the 40 in A₄. Call this set A₅.
6. The members of A₅ pick a set of 25 people. This is NOT random. In fact, every person chosen must be approved by at least 9 of the 12.
7. Choose a random set of 9 from the 25 people in A₅. Call this set A₆.
8. The members of A₆ pick a set of 45 people. This is NOT random. In fact, every person chosen must be approved by at least 7 of the 9.
9. Choose a random set off 11 from the 45 people.
10. These 11 chose a final set of 41. They do this by every member choosing a candidate which they may examine in person. The candidates with the most approvals are picked.
11. THESE 41 chose the WINNER - but the winner had to get at least 25. (It is not clear if any of them could be the winner.)

Which of the following is true?

1. This is a real scheme that was really used.
2. This scheme was part of a BREAKTHROUGH!!!! result.
3. This scheme is a counterexample to a conjecture about voting schemes.
4. This scheme (with parameters) is an example of a voting scheme that is NP-hard to manipulate.

I would have guessed that it is a contrived scheme to serve as a counterexample, but NO- this scheme was really used to pick the new doges of Venice from 1268 until roughly 1768. Why so complex? To avoid anyone rigging the election. You can read more about it here. I suspect it would be hard to manipulate, though I don't think it is known to be NPC to manipulate.

Why did this come up? Bobby Kleinberg gave a talk at UMCP where he brought it up to show that his results (about how randomness can help make mechanisms hard to manipulate) had a real world counterpart. See here for his paper, which has co-authors Jason Hartline and Azarakhsh Malekian.

How I'm Spending my Spring Break

This week I returned to Dagstuhl for the workshop on Computational Complexity of Discrete Problems. I come here so often that when I tweeted that I was om way Dagstuhl tweeted back that they want another typecast. But no Bill here so no typecast.

This has been a theory-friendly month for Dagstuhl. Last week the Geometers and two weeks before that Algorithms. One of the algorithms attendees thought he saw me at the Frankfurt airport on his way home but didn't think I would have any reason to be in Germany. But it was me returning from Porto.

Dagstuhl really gives me a chance to find out the latest and greatest of what's going on in complexity. No major breakthroughs but lots going on down in the low complexity range (low-depth circuits). Keep watching my Twitter for Dagstuhl updates.

There's a conflicting complexity seminar in Paris that's splitting our crowd. If you happen to be in Paris tomorrow, Avi Wigderson is giving a popular talk on P v NP.

Dagstuhl is expanding to have either larger or more seminars. There is also a new Dagstuhl-like seminar in Japan and the Banff center has new housing. Seems to be the model we are in: Big conferences to publish your papers, small workshops to mingle and collaborate. I love these small workshops but I do worry they silo us theorists even more.

Travel Support for Students going to STOC 2011

If you are a grad student and want to goto STOC 2011 there is travel support money that you can apply for. See here for details.

We are particularly interested in getting people who normally ARE NOT able to get to STOC (or FOCS or...) to go to this. SO, if you know some grad students who would LIKE to go to STOC if they had travel money, but DO NOT have travel money, then urge them to apply.

Update on 17x17 problem

UPDATE: Problem HAS been solved. See Feb 8, 2012 post. There IS a 4-coloring of 17x17 and also of 18x18. Can also see my arXiv paper on grid coloring.


Long time readers may recall that 17x17 problem that I posted on Nov 30, 2009 here. I am sometimes asked if the problem is still open. Alas it is. Is the bounty on it still available. Alas it is. Some thoughts and experiences

1. See this for a different take on it.
2. When I wrote the post not that many people tried it seriously. Because of the post and because Brian Hayes picked up on it (see here) many people have worked on it seriously. This is good in that I now know that its hard, but bad in that its still unsolved.
3. A High School Student wanted a formal contract before showing me his alleged solution. I told him that if he posted a comment with the coloring ON MY BLOG I would have to pay up and would do so gladly. His solution didn't work anyway.
4. Do I still think that 17x17 is 4-colorable? The problem is that this is a finite problem. The fact that nobody has found a 4-coloring MIGHT mean there isn't one. But it might just mean there are very few of them.
5. As a pessimist I think that 17x17 IS 4-colorable. Why is that? The following three problems are open: is 17x17 4-colorable? is 17x18 4-colorable? is 18x18 4-colorable? If 17x17 was NOT 4-colorable then the rest would NOT be 4-colorable with no additional work. We will not be that lucky. By the same reasoning I think 18x18 is NOT 4-colorable. (There are a few other grids where we do not know if they are 4-colorable but not many.)
6. Will future faster computers help? Maybe, but there needs to be a math breakthrough, even a small one, as well.
7. Will future Quantum Computers help? I doubt anyone will go to the expense of building a quantum computer for the 17x17 grid problem. And I doubt there will be general-purpose quantum computers.
8. The following problem is inspired by my problem but has not gotten that much attention: How hard is the following: Given (n,m,c) and a partial rectangle-free c-coloring of nxm, can it be completed to a total rectangle-free c-coloring of nxm. Should be NP-complete but I have not been able to prove this I also haven't tried that hard- Maybe I'll get a bright High School Student to do it and get some free lunches out of it (see here).
9. JohnPaul Adamovsky claimed that they had a proof that 17x17 was NOT 4-colorable and had comments on it on my blog here. I could not make sense of his proof. I suspect he no longer believes this since recent email from him describes an approach to finding a 4-coloring. He also made an offer that if I bought him some type of computer (he says which type) he will solve the problem. I have declined it; however, I offered to do a post on updated status of the 17x17 problem so he could make a comment on it offering it to others (I am doing that NOW). Note that if he posted on my older posts very few people would see it. He did not respond kindly to my offer; however, we'll see if he comments.
10. I gave a talk on grid colorings at an Algorithms and Theory of Computation Day that Zachos invited me to in New York. A the end I had the following exchange with Lane Hemaspaandra who had also given a talk.
    
    LANE: What does this have to do with Algorithms or Theory of Computation?
    
    BILL: I could make something up but I respect you and the audience too much for that. The answer is NOTHING.
    
    LANE: Then why are you giving a talk on it at Algorithms and Theory of Computation day?
    
    BILL: Because Zachos invited me. You could ask why he invited me, but I think it is because he knows my parents live in the area so I would be a cheap date- no housing costs.
    
    OTHER AUDIENCE MEMBER: Actually this material does have applications. This is part of Ramsey Theory and there is an entire website of applications of Ramsey Theory to Computer Science.
    
    BILL (Thinking- there's ANOTHER one aside from mine? I should take a look at it) OH- that's good to know- what is the pointer to it?
    
    OTHER AUDIENCE MEMBER: Its http://www.cs.umd.edu/~gasarch/ramsey/ramsey.html. Oh- that's you! (READERS- see here.)
    
    BILL: YES, Ramsey Theory has had applications to computer science and that's great! However, I am not going to make the following incorrect claim: (1) Ramsey theory has had apps to CS, (2) The Grid problem was inspired by Ramsey Theory. Hence (3) The Gird problem has apps to CS. That would be bad logic.

TAMC conference accepts are out/What does a name tell you about a general theory conference?

The TAMC conference list-of-accepts is posted here. TAMC stands for Theory and Application of Models of Computation.

For general theory conferences does the name tell you anything? I will consider FOCS, STOC, ICALP, TAMS, COCOON. (I am sure there are more general-theory conferences-- I invite you to comment on them and on if their name tells you anything.)

1. FOCS- Foundations of Computer Science. Are there more papers on the Foundations of computer science here than at STOC or ICALP or TAMS or COCOON? Since people speak of STOC/FOCS papers the question is- are they different?
2. STOC- Symposium on Theory of Computation. What is Theory? There are large parts of theory that are left out such as Semantics.
3. ICALP- International Colloquium on Automata, Languages, and Programming. AH- its a Colloquim not a conference. ICALP does has a different flavor than FOCS and STOC; however, I don't think the name captures it. By the name it could be more of a PL conference, and its not. Also- I had thought they changed the A to mean Algorithms. Is that one of those items they debate in the business meeting? Should they change it to Algorithms?
4. COCOON-Computing and Combinatorics Conference. Does this have more Combinatorics then STOC, FOCS, ICALP? Is this intended to be a general theory conference?
5. TAMC Theory and Application of Models of Computation. I don't think the papers are more on models than the other conferences.

The best way to tell what a conference is about is to look at the Call for Papers list of topics. The name does not tell you much.

Computer Science Takes Over

We live in our own research areas. I focus on computational complexity and marvel at what our field has accomplished over my over 25 years in the field as well as the simple problems we have failed to solve. But every now and then we should pull ourselves our of our forests and take a look around. The whole of computer science has dramatically advanced and as the Internet have changed the way we do almost everything, be prepared for a whole new change.

My daughter is about to get her driver's license. Her children won't need one as their cars will drive themselves. One issue I have as SIGACT chair is gathering information together from various old proceedings and newsletters. In a few years computers will do this for me as quickly as I can ask for them. Right now we have great tools for finding information on the web. In the future our tools will make sense of that information.  In the near future there will be no such thing as unstructured data. Where will all this lead us? I wish I knew--I could be a wealthy man.

Machine Learning has become a very mathematical and statistical-based research area yet the theoretical computer science community hasn't played the role in this area that we could have.

The New York Times have been running a series of articles about AI and its implications to society. A recent article talked about how legal firms save considerable money by using computer software for document discovery. Less money means less white-collar employees needed to sift through documents, a point Krugman pointed out in his column. Krugman also says

Conversely, jobs that can’t be carried out by following explicit rules — a category that includes many kinds of manual labor, from truck drivers to janitors — will tend to grow even in the face of technological progress.

I don't expect truck drivers will exist in 10-20 years either. Technology has so far tended to create more jobs than it destroys but will there be any safe jobs in the future?

STOC 1989

A student at Northwestern gave a presentation about a STOC 1989 paper. I've been to well over a hundred conferences and the memories of many just merge into each other. But some conferences stand out in one's life and STOC 1989 was definitely one of those for me.

I was just finishing my Ph.D. at MIT and took my first trip to Seattle for this conference. The Boston Red Sox were staying at the conference hotel and we saw them lose to the Mariners in the Kingdome, a stadium I do not miss. I gave a talk on a paper that we later had to retract.

But above all I remember going to this mid-May conference with no job offers for the next year. I had planned to spend the reception asking people about job opportunities but my heart wasn't in it and I started drinking instead. Janos Simon came up to me and told me that Chicago would be making me an offer. It took all I had to give a coherent response and not toss my cookies on him.

The student was a baby at the time.

Les Valiant wins the Turing Award

In a definite case of when not if, Leslie Valiant will receive the 2010 ACM Turing Award, the highest honor in all of computer science. Valiant has done incredible work in learning theory (he invented PAC learning), parallel and distributed computing and more recently holographic algorithms. Valiant's brilliant work in counting complexity, including the #P-completeness of the Permanent and his work with Vijay Vazirani that shows that solving NP problems with a single solution is as hard as arbitrary NP problems, have played a critical role in much of my own research.

Valiant will give his Turing Award lecture at FCRC in San Jose on the evening of Sunday June 5th, which will be a special treat for those of us going to STOC or the other FCRC meetings.

Three Questions that I think Watson would have trouble with

Here are two questions that were on Jeopardy (the shows slogan: Watch "Jeopardy!", Alex Trebek's fun TV quiz game show!) that I do not think Watson would have gotten right. I have added a third that I also think Watson would not have gotten right. What do you think?

QUESTION ONE: The FINAL JEOPARDY category was Computer Science. Here is the question. I mean the answer.

John Tukey coined this compound word in 1959 saying it was as important as "Tubes, transistors, wires, tapes ..."

Person A wrote WHAT IS A MOTHERBOARD. Wrong. Person B wrote down WHAT IS. Wrong. (This might have worked if the question was in philosophy.) Peron C wrote down WHAT IS WI-FI. Wrong. I got it right from reasoning not memory. I do not have the quotes of John Tukey memorized. Does Watson? I doubt it. I think he would have gotten it wrong. (The answer can be found HERE.)

QUESTION TWO: The FINAL JEOPARDY category was 1930's Films. Here is the... answer

In this classic film, one of the characters tries to quote the Pythagorean theorem, but gets it wrong.

Two of the contestants wrote Gone with the Wind. The third one wrote the correct answer which I will not reveal here in case you want to try it. (The contestant who got it right won the game.) I doubt Watson would know it--- too much to correlate. (The answer can be found HERE.)

QUESTION THREE: This was not on Jeopardy. I am asking it in the form of a question: What is unusual about the Jeopardy Slogan? (The answer can be found HERE.)

Greetings from Porto

Today we just finished the thesis defense of Andre Souto at University of Porto. Good News: He passed the defense so now we call him Dr. Souto. Better news: By law he has to be paid more in his current teaching job. Not so good news: They will fire him before they pay him more. First time I put someone out of a job by passing them in a Ph.D. defense.

His thesis was in Kolmogorov complexity. One particularly neat trick from his thesis: A PRG that under reasonable assumptions maps strings of length O(log n) to strings of length 2^O(n), a double exponential jump done by combining two PRGs based on Nisan and Wigderson.

I love doing these defenses outside the US. We got to dress like monks when quizzing the defendant. After the defense we had a wonderful lunch with Port Wine from Porto of course.

Andre the Defender

The Jury: Harry Buhrman, Luis Antunes, me and Armando Matos

A good article on how science is publicized gets the science wrong

(Guest Post by John Rogers)

I have just been reading the recently published book "Seeing Further". Edited by Bill Bryson, it contains essays commissioned for the 350th anniversary of the Royal Society. Among the contributors are James Gleick, Neal Stephenson, and Richard Dawkins. The last essay is written by Martin Rees. A cosmologist and science writer, he was president of the Society from 2005 to 2010. On page 476 of the U.S. edition, he writes on how today scientific results are publicized in ways different than even in the recent past:

A few years ago, three young Indian mathematicians invented a faster scheme for factoring large numbers - something that would be crucial for code-breaking. They posted their results on the web. Such was the interest that within just a day, twenty thousand people had downloaded the work, which was the topic of hastily convened discussions in many centres of mathematical research around the world.

As readers of this blog know, the result he refers to is the 2002 paper PRIMES is in P by Agrawal, Kayal, and Saxena. Now the point of the paragraph is how the web is changing the way scientific results get promulgated. Still, I thought it odd that he would mis-state the result. He does mention that faster factoring would have cryptographic import so he (or an editor?) has some knowledge beyond what was in the headlines.

My question is: Is it indeed odd that a scientist would not realize that this is a result about decision and not about search, that if a "faster scheme" had been found to solve the search problem then even a very quick literature search would have turned about up quite a bit more about the code-breaking implications?