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?

Interesting Math related to the Unexpected Hanging Paradox

In a prior post I pondered if there was interesting MATH that relates to the Unexpected Hanging Paradox. At the time none of the comments really had any and, alas, I thought there was not. (Thought looking back at the comments, the first one by Jeffe may be relevant.) But recently Ran Raz emailed me a pointer to this paper by Kritchman and Raz: The Surprise Examination Paradox and the Second Incompleteness Theorem. See also this post by Sam Alexander which explains some of the paper very well. The paper contains the following:

1. A new proof of Godel's incompleteness theorem that resembles the Surprise Exam Paradox. This is EXACTLY the kind of thing I was looking for.
2. An argument that suggests that Godel's incompleteness theorem can be used to resolve the paradox.

What does it mean to resolve a paradox? I resolve the unexpected hanging paradox by saying that the notion of Surprise is ill defined. The paper has a much more interesting viewpoint but that does not mean that it is correct. Which resolution is better the papers or mine? Not clear since it is unclear what it means to resolve a paradox. So what should YOU do? Read the paper and decide! Or just read it for the math.

What I Tweeted

Various thoughts not restricted to 140 characters.

Congrats to Mihalis Yannakakis for his election into the National Academy of Engineering as well as new Sloan Fellows Julia Chuzhoy, Rafael Pass, Chris Peikert, Mark Braverman and Anup Rao. TTI-Chicago gets no respect with TTI-C Prof Chuzhoy listed at University of Chicago but it should be fixed soon.

I called the Watson-Jeopardy match in 2009. The IBM segments during the show were great selling points for computer science. John Markoff wrote a nice wrap-up article for the Times but note the correction

An article last Thursday about the I.B.M. computer Watson misidentified the academic field vindicated by Watson’s besting of two human opponents on “Jeopardy!” It is artificial intelligence — not computer science, a broader field that includes artificial intelligence.

I skipped the various university viewing parties in favor of watching the shows with my daughter Molly. During current events in history class she went on a rant why everyone should think the Watson victory was "so cool". That's my girl.

Wolfram Alpha knows Computational Complexity. Pretty impressive but doesn't know everything. Jeff tweeted

When I ask "Is multiplication in AC0?" it tells me about the Ace of Clubs. Fail.

So we need Watson and Wolfram Alpha combined to make sense of our field.

Next week I'm off to Porto, home of Complexity 2012, for some Port Wine, a Francesinha and the thesis defense of co-author André Souto.

Aaron Sterling starts his own blog!

Aaron Sterling recently had an AWESOME guest post about Cheminformatics. That got such a great response that he has started his own blog Nanoexplanations. It shot to the TOP of our blogroll because we list thing alphabetically by first name. Kudos to Aaron's parents for seeing this day and naming him appropriately.

What will it be about? His guest post was on chemo-computing. More generally Aaron has been looking at nonstandard applications of theoretical computer science. That will be his topic.

A good blog should fill a need that is not being filled. His seems to be in that category--- I do not know of any blog covering non-standard applications. Not surprising- they are nonstandard! Is his goal to make these topics standard? At that point will he cease blogging? Only time will tell.

In the 2009 Year in Review post we noted that in 2009 we had annouced and added to our blogroll FIVE new blogs. In the 2010 Year in Review post we noted that in 2010 we had annouced and added to our blogroll NO new blogs. So blogging seemed to be in decline (granted this is a very small sample in a very small corner of the blogsphere). What is the trend? It is trendy to say that blogging is just so 2009 and that tweeting is the future, at least for the next 10 minutes. But to make predictions based on such little evidence is just so redonk.

Lincoln's Dog-Tail question (in honor of Presidents Day)

(Posted in Honor of Presidents Day.)

The following is NOT a trick question; however, I have heard two different answers for it.

How many legs would a dog have if we called the dog's tail a leg?

1. The answer is clearly 5- since 4+1=5. Duh.
2. Calling the tail a leg does not make it a leg. A dog has 4 legs. Duh.
3. I have seen people on either side not be able to even understand the other side's point.
4. This question has been attributed to Abraham Lincoln; however, just as Bogart never said Play it again Sam and Kirk never said Beam me up Scotty, Lincoln (likely) never said calling a tail a leg does not make it a leg (though he might have said Play it again Sam or Beam me up Scotty). See this interesting and serious post for information on what Lincoln said.
5. In our terminology Lincoln's point was that definitions should conform to reality and if they do not then it is the definitions that are wrong. I suspect he would not have liked the Banach-Tarski Pardox.

How would you answer the question? Do you understand the opposing viewpoint?

CCC 2011 papers- you heard it here first

The complexity papers for CCC 2011 are posted HERE. (They might not be at the official CCC site yet; however, I have permission to post here.)

1. Kudos to Omer Reingold- the notifications were sent out on TUESDAY, three days BEFORE the promised FRIDAY deadline.
2. Tuesday was also the ICALP deadline! I wonder if anyone took there CCC reject and submitted to ICALP. It would take rather fast turn around and they use diff formats.
3. I wondered why there was any delay between the notification to authors and the list being posted. Omer Reingold emailed me the following which explains it: ... it's important to make sure that authors provide updated information (updated title, list of authors affiliation) before posting
4. Some people have emailed be privately complaining that there is a bias towards complexity theory in CCC. I was at first skeptical (such talk was false for STOC 11), but after looking at the list of papers there seems to be some foundation to this concern. Of the 30 papers only 5 were on algorithms! If this conference is going to be that biased they should change the name from CCC to Conference on Computational Complexity.

If I tweeted here is what I would tweet

If I tweeted there is what I would tweet:

1. There was an interesting blog post that responded to Aaron Sterling's Chemoinformatics Post. See here for this interesting discussion.
2. See here for info on the Watson's performance on Jeopardy.
3. Why did Watson bet $937 on the Final Jeopardy question yesterday? (Tuesday) Zero would make sense. The max amount to guarantee victory even if he got it wrong would make sense. A nice round number to look more human would make sense.
4. The winner gets $1,000,000, second place gets $300,000, third gets $200,000. Ken Jennings and Brad Rutler have said they will give half of their winnings to charity. Watson said he would give all of his to charity. QUESTION: If you were on the show would you give 1/2 to charity? For Jennings and Rutler it isn't really hard to do since they already have lots of money from their prior Jeopardy appearances (though it is still admirable). But how about YOU?
5. Officially the authors of the CCC papers will be notified on Friday Feb 18. I have been told that this is an approx both ways. Could be earlier, could be later.
6. Some CCC notifications (all?) have been emailed. The list is not posted! At one time the quaint notion was that people should not find out if there paper got in or not by seeing someones telegraph message, website, or blog. Is this quaint-but-idiotic notion still in effect?
7. I got a copy of the complete Knuth Vol 4 in the mail today. How long have we been waiting for this? Knuth held a contest to name what we now call NP-completeness for use in this book.
8. Publishers have lists of people they send books to. As an editor for SIGACT NEWS I am on some of those lists. Today I got two copies of the exact same book. Both mailed to William Gasarch, SIGACT NEWS book review editor, Dept of CS, College Park MD, 20742. What was the book: Bijective Combinatorics.
9. CafePress.com emailed me a subject heading of gift of infinite choices. Alas, the actual letter said you can choose from 250 million styles and designs..
10. 12 days of Christmath (That is NOT misspelled.)
11. Also this one (I give two pointers in case one goes away.)

Can we Innovate without Producing?

On Friday I heard a speaker lament about how losing the manufacturing base in the US: "You can move a foundry easier than you can move an Internet company." An article in the New York Times has as its headline New York Times headline reads When Factories Vanish, So Can Innovators acknowledging the last metal flatware (think forks and spoons) plant to close in the United States.

On the other hand watch Austin Goolsbee explain Obama's National Wireless Initiative (via CCC blog).

Note the emphasis on job creation with almost exclusively service sector Internet jobs.

What's driven manufacturing overseas is not the Internet but the Box. Yet somehow we can continue to innovate,  with Microsoft, Google, Facebook, Twitter and Groupon all US made and continue to employ most of their workers in the US. Apple has had great hits with its physical devices like the iPhone and iPad but they are manufactured overseas. Even the next great fork design could easily come from the US even if those forks are made in China.

Our economy won't be won by keeping inefficient foundries in the US rather by improving on what we do best. As Obama puts it in the State of the Union.

Our free enterprise system is what drives innovation.  But because it’s not always profitable for companies to invest in basic research, throughout our history, our government has provided cutting-edge scientists and inventors with the support that they need.  That’s what planted the seeds for the Internet.  That’s what helped make possible things like computer chips and GPS.  Just think of all the good jobs -- from manufacturing to retail -- that have come from these breakthroughs.

Half a century ago, when the Soviets beat us into space with the launch of a satellite called Sputnik, we had no idea how we would beat them to the moon.  The science wasn’t even there yet.  NASA didn’t exist.  But after investing in better research and education, we didn’t just surpass the Soviets; we unleashed a wave of innovation that created new industries and millions of new jobs.

This is our generation’s Sputnik moment.  Two years ago, I said that we needed to reach a level of research and development we haven’t seen since the height of the Space Race... We’ll invest in biomedical research, information technology, and especially clean energy technology -- an investment that will strengthen our security, protect our planet, and create countless new jobs for our people.

Today Obama releases his budget for 2012 that should have dramatic cuts in many programs but growth for scientific research. It's going to be interesting.

PROS and CONS of being on a Program Committee

What are the PROS and CONS of being on a program committee?

1. PRO: Looks good on your resume. Is this true at your school? This PRO may be more relevant for untenured and un-full-prof people. (My spellcheck wanted me to use unturned instead of untenured.)
2. PRO: You get to see what people are working on. This may give you ideas of what to work on or of what papers to look at. You absolutely cannot use the ideas you see until they are in the public domain; however you can learn things and look up some past work.
3. PRO: If there is an in-person meeting then you get to meet some new people. (If there is NOT an in-person meeting then its not the same.)
4. PRO: You get to see how the process works which may help you when you submit later. Or it may help you decide not to submit.
5. CON: It takes a lot of time.
6. CON: You may have to read papers that you don't care about. (This could be good for you.)
7. CON: You may have to read bad papers. Not clear though- if you can tell its bad early on then you can skim the rest.
8. PRO AND CON: IF you also goto the conference then (a) you will understand more talks (b) you will be bored at more talks. I tend towards (a) but others tend towards (b).
9. PRO AND CON: You get to help decide what papers get in. But you may see things not go the way you think they should.

I'm sure there are more PROS, CONS, and THOUGHTS- please share them!

STOC 2011 accepte papers posted.You heard it here...12th!

For those who did not read yesterdays comments or Lance's Tweet (the empty set?) the list of accepted STOC papers is here.

1. 84 papers accepted. I personally think that there is enough high quality work that they should have more. However, I do not know what constraints the Program Committee had in terms of scheduling.
2. Lance thinks we should give up this model of high-prestige conferences all together and grow up. I am less radical--- I think that conferences should have higher acceptance rates and have other activities for people to get information out there. Posters, satellite workshops, rump sessions, and half-day seminars are all good. FCRC will have some plenary talks which is also good (I am not sure if they will have any of the other items I mentioned.) At a math conference I went to they had a Math Jeopardy competition for undergrads. That was JAWESOME!!! (My ugrads tell me this is the new `Awesome and it means Jaw-dropping Awesome. They could be punking me.)
3. Some people have said that there are less algorithms papers than usual or more complexity papers than usual (is that the same thing?). Is this a general trend for STOC and FOCS or is that just this one time?
4. Is it true? I tried doing a count but it was hard to tell how to classify things. Some papers were in both, some in neither, some hard to classify, The whole endeavor reminded me for the W(4,5)th time how pointless some classifications can be.
5. Is it important? If GREAT papers in algorithms do not get in because GOOD papers in complexity (or something else) do, that would be a problem. Other than that it is not a problem.
6. Lance has suggested that we should have a conference where all the subdisicplines of CS get together and hold hands and sing Kumbaya. Is FCRC like that? Is it as close as we'll ever come? Are there too many different subfields of CS that don't care about each other to really have a conference like that?

The Theory Postdoc Culture

FOCS Call for Papers posted. Deadline April 13.

The CRA organized a committee that put together on a white paper on whether postdocs are healthy for Computer Science. They are looking from thoughts and comments from the CS community that you can leave on that page. Suresh gave his thoughts last week.

Theoretical Computer Science, for better or worse, is ahead of this game. We have a plethora of postdoc positions available in our field. Combined with a relatively tight job faculty job market in the past few years, it is quite rare to see students in our community going immediately into a tenure-track job without a postdoc and a number of people are doing second and third postdocs. We haven't quite hit the point where it is impossible for a student to go right from Ph.D. to a tenure-track job at a major research university, but we are awfully close.

The computer science academic job market has ebbed and flowed since I was a graduate student. Most students believe the academic job market they see when entering graduate school will be similar when they get their Ph.D. Most students are wrong. Postdoc positions give some elasticity, filling in the gaps until the market moves back the other way.

When I got my Ph.D. I had a choice between a tenure-track at a good liberal arts college or a two-year assistant professor, basically a teaching postdoc, at the University of Chicago. I took the latter to keep my research career going and it did pay off for me--I had a good rookie year and the U of C kept me. It doesn't work as well for everyone but if postdocs can keep people's dreams alive that's a good thing.

All the news that fit to tweet

The Daily Shows Slogan used to be When news break we fix it! This raises the question: When does breaking news actually break?

1. (My memory of this may be hazy but something like it transpired.) In 1995 Bob Dole went on The David Letterman Show and said

   I will announce that I am running for president next week.

   David Letterman pointed out

   You just DID. NEWS ITEM: Bob Dole announces his candidacy on the David Letterman Show.

   I agree with Letterman- announcing that you are going to announce something is announcing it. I think Bob Dole got confused--- The David Letterman Show probably got more viewers than his press conference.
2. In this Jan 25, 2011 post Richard Lipton thanked me for my review of his book (and said some very nice things about me. THANKS!) Why Jan 25, 2011? Because this was shortly after the review appeared IN PRINT. However, in my Sept 9, 2010 post I had posted my review. Does appearing in print still have a certain Je ne sais quoi?
3. One of the many comments on Aaron Sterling's post on chemoinformatics was by Aaron Sterling himself. He wrote:

   It will be a while before this goes to press, so I can correct inaccuracies or address concerns before this becomes unchangeable.

   This is rather quaint. First off, goes to press? I think Aaron's guest blog will have more readers than my column. Aaron, your review is already out there. What does goes to press even mean anymore? Second off, what Aaron writes is not quite true. I keep all of the reviews online. If the review appears and 10 years later Aaron spots a typo and wants me to fix it on the online version, I would do it. For a big change I would make it a footnote and put a date on it. Page numbers are not a problem since the page numbers on my website copy are not the same as those in SIGACT NEWS anyway. And someone looking for the review would more likely find my website rather than there paper copy or the official ACM site (behind a paywall?) I will also keep the copy the Blog post points to up to date, so that is another free and easy-to-find place to find it.
4. A colleague was mentioned in The Online New York Times. The colleagues aunt wanted to know

   When will you be in the REAL New York Times.

   Is the aunt right? Does the REAL New York Times have a certain I-know-not-what that the online version lacks? The colleagues teenage son commented:

   Aside from far less people reading it, and getting ink on your hands when you do, what advantages does the so-called real NY times have?

   That may be an exaggeration (ink on your hands?) but he does have a point. See this for a counterpoint.

Is Cheminformatics the new Bioinformatics? (Guest Post by Aaron Sterling)

Chemoinformatics for Computer Scientists

Guest Post by Aaron Sterling

I recently completed a review of Handbook of Chemoinformatics Algorithms (HCA) for SIGACT News. (See here for the full 12 page review. I have tried to recast the language of HCA into something more accessible to a computer scientist.) Somewhere along the way, my goal for the project changed from just a review of a book, to an attempt to build a bridge between theoretical computer science and computational chemistry. I was inspired by two things: (1) none of the computer scientists I talked to about this -- not even ones who did work in bioinformatics -- had ever heard of chemoinformatics; and (2) the state of the art of chemoinformatics algorithms remains rudimentary from a TCS perspective (though the applications and the problems being solved are quite complex). I believe this represents a tremendous interdisciplinary research opportunity: hundreds of millions of dollars are riding on the speed and accuracy of the techniques presented in HCA, and I suspect that "small" mathematical improvements could yield large payoffs.

My quick-and-dirty definition of chemoinformatics is, "Algorithms, databases and code to help chemists." A more thorough description can be found at this Wikipedia article. (The linked article provides a gentle overview of chemoinformatics, with links to several more specialized articles.) The most discussed applications in HCA are in silico pharmaceutical discovery, solvent discovery, and petroleum reaction improvement and analysis.

The TCS community has formally recognized the importance of working more closely with chemists since at least the 2007 Computational Worldview and the Sciences Workshops, which discussed the tradeoff between "chemical cost" and "computational cost" of producing nanodevices. The report on those workshops speculates, While the computational costs are fairly straightforward to quantify, the same is not true of the chemical costs. Perhaps the Computer Science lens can be used to construct a formal, quantitative model for the relevant chemical processes, which can then be used to optimize the above tradeoff." After reading HCA, I believe formalizing such tradeoffs is important for all computational chemistry, not just nanochemistry.

Unlike the field of bioinformatics, which enjoys a rich academic literature going back many years, HCA is the first book of its kind. There are a handful of graduate textbooks on chemoinformatics, but HCA is the first attempt to collect all chemoinformatics algorithms into one place. The difference in academic development is due to the proprietary nature of chemical databases, in contrast to biological data, which has a long history of being publicly available. As a result, thoroughgoing academic investigation of chemoinformatics is quite new, and there does not appear to be an overarching mathematical theory for any of the application areas considered in HCA.

To provide an intuition for the type of problems considered, suppose you want to find a molecule that can do a particular thing. We assume that if the new molecule is structurally similar to other molecules that can do the thing, then it will have the same property. (This is called a "structure-activity relationship," or SAR.) However, we also need the molecule to be sufficiently different from known molecules so that it is possible to create a new patent estate for our discovery. The naive way to check for structural similarity would be to compare two molecules by solving the Subgraph Isomorphism Problem. There are some algorithms currently in practice that do this, but we expect that problem to be infeasible to solve in general. Therefore, we take graph-theoretic representations of the molecules we want to compare, and extract structural information from them in the form of real numbers called molecular descriptors. (An example of a molecular descriptor that comes up in TCS is the number of distinct spanning trees that spans the molecular graph. There are over 2000 descriptors in the literature, and most require knowledge of chemistry to describe.) If our two molecules are close with respect to a metric in a descriptor space, we predict that they have the same functionality. Then we can test in a wetlab whether or not the prediction is true. The objective is to use computational resources to save time and money by "preprocessing" the laboratory experimental steps.

As this is the Computational Complexity blog, I will provide a quote from HCA on "complexity indices" for molecules. HCA, in turn, is partially quoting from Complexity and Chemistry: Introduction and Fundamentals by Bonchev and Rouvray.

A complexity index should

1. Increase with the number of vertices and edges
2. Reflect the degree of connectedness
3. Differentiate nonisomorphic systems
4. Increase with the size of the graph, branching, cyclicity, and the number of multiple edges

Still, this is an ongoing discussion, with even conflicting positions.

Both Chapter 4 of HCA and (in much more detail) Complexity in Chemistry provide many complexity indices that appear to have these properties. However, the argumentation is one of induction on small examples. There is no formal mathematics comparing different indices, and the explanation of usefulness of a complexity index is limited to, "It worked for this particular application." This currently ad hoc state of the field leads me to believe that there could be a significant interdisciplinary research opportunity available for theoretical computer scientists willing to put in the time to learn the vocabulary and perspective of the computational chemist.

I believe chemoinformatics, like bioinformatics, will provide an important source of problems for computer scientists, and I hope the publication of HCA, and (to a lesser but real extent) this guest blog and my review, encourage greater participation between computational chemistry and TCS.

Update 2/13: Chemist Rajarshi Guha has posted a response on his own blog

The Ideal Conference

I found the perfect CS conference. A meeting where computer scientists from all its subdisciplines come together. Not with the purpose of presenting their current research and padding their CVs, but to hear about the latest ideas in the field, learn how to be stronger members of the CS community and above all network, meeting other computer scientists making connections and sharing ideas. This meeting draws a large segment of its intended audience, so popular it has to close registration. A conference that fulfills that most important conference mission: building community.

The only problem: I'm not invited to the party, the Grace Hopper Celebration of Women in Computing and its over 2000 attendees.

The Grace Hopper is a great event but why can't computer science also have such a meeting the embraces the entire CS community? Are we just too big? We could have a large meeting in January built around academic recruiting, where job candidates and hiring committees can have initial discussion and narrow the number of interviews needed later on. Many other academic fields, including mathematics and economics, follow this model.

The most important the purpose of this meeting would be for people to meet, build a strong CS community and make us feel proud to call ourselves computer scientists.

Why My Kids Trust Wikipedia

Guest post from Annie and Molly Fortnow

Our teachers used to tell us not to use Wikipedia because anybody can edit it and therefore it isn't trustworthy. A couple of years ago we decided to test it out. [Not with my knowledge - Lance]

We went to the Cow page but it was locked showing that some subjects can't be edited. We then proceeded to the Grapes page which was unlocked. So we added to the bottom: "Grapes are good. Nerds are cows." We immediately got a message popping up on the screen that said something like "That's an inappropriate remark. It's being deleted. You are getting a warning."

Now we know that if someone edits Wikipedia with something silly it will always be edited back. So, now we trust Wikipedia and use it often. Every time one of our friends asks us why we use Wikipedia we tell this story and everyone always believes us. Now all our friends trust Wikipedia too.

Does Tiger Woods know what a Venn Diagram is?

In prior blogs I noted that the terms Turing Test and Prisoner's Dilemma have been used in articles for non-math people. In the age of Google people can look things up (recall that Google makes us smarter). I have since seen Prisoner's Dilemma used as the name of an episode of the TV show White Collar. They used it mostly correctly in the show.

I have spotted some more math term in a non-math context.

VENN DIAGRAMS!

In an article entitled Rachel Uchitel is not a Madam., which is about the world Tiger Woods was involved in, the following was mentioned. (The context is a comparison between the options men have for affairs: a prostitute or a civilian.)

Both methods of slaking the hunger have their pros and cons. Men like to hunt, and there is no need to hunt a prostitute. Men like to cheat without strings, and you can't stop a civilian from falling in love. But (Tiger) Woods found a way to enjoy the best of both worlds in one type of woman, a Venn diagram of sexual satisfaction. Most of his women lived in a nebulous in-between world.

Will this enlighten the masses as to what a Venn diagram is? If they look it up then yes; however, the actual statement is wrong. What they really mean is an intersection of sexual satisfaction, or, as it is commonly known, an intersextion.

ZENO'S PARADOX

An article entitled Harry Potter and the Dragged out final act began as follows.

When Warner brothers announced that the seventh and final book of J.K. Rowling's Harry Potter series, Harry Potter and the Deathly Hallows, would be two movies, it occurred to me that the company had been insufficiently ambitious. If, as reported, Warner executives are scared of running short of tentpoles (i.e., the so-called franchises that prop up a studio), they should at the very least divide the next half in half. Following Zeno's paradox, they could even turn Deathly Hallows into an infinite number of sequels with Becket-like arcs of nonaction: "Let's apparate." [They do not move.]

Is this the correct usage of Zeno's paradox? Becket? Apparate? I was inspired to look up apparate and put in a pointer so that you can learn what it means too!

n+1

There is a general interest magazine called n+1. I emailed the editors to ask why they chose the name and got this enlightening response:

Well, as a non-math person and one of the founding editors of n+1, I can tell you that we still don't know very much about math, but we did have some vague high school memories of set theory and algebra and knew that n+1 could mean, if it were a set, an infinite series or open-ended expansion, or just that for any quantity (n), there's often more than meets the eye, or is commonly thought or known (+1). That was the sense that Chad Harbach, another founding editor, had in mind when he first thought of the title as a placeholder, a math metaphor for human potential, back when he was a Harvard undergrad. Over time, the title also seemed to work in response to the "End of History" crowd, all those people who told us that no new ideas were really possible in the humanities, no new writing was possible, that it was foolish to start a magazine of politics, literature, and culture in these times. So we took on n+1 as a rallying cry, of sorts. Someone might also hear it as "end+1," after the end, a new beginning, that sort of thing. We did have a math PhD friend who suggested that, if we really wanted to designate an infinite universe of possibilities, we should have called it omega plus one, but that seemed too much for us non-math types. As far as I know, omega plus one is still available as a title.

Thanks for writing in to ask and best of luck with the blog and other endeavors,

I wish them well too!

Will any of these terms enter the common vocabulary? I suspect that Prisoner's Dilemma will as it is a nice shorthand for a common phenomena. I suspect that Turing Test, Venn Diagram, Zeno's Paradox, and n+1 do not come up often enough to break out into common use.

What math terms have you seen used in articles for non-math people? Were they used correctly? Will they become common? Are they common already? If so have then are they related to the original meaning?

Coloring Maps

The four color theorem means you can color the United States in four colors. But can you color it in three? Try it before you read on.

The answer is no. Consider Nevada. It takes three colors to color that states that surround Nevada (Oregon, Idaho, Utah, Arizona and California) and then one more for Nevada.

I use this as an example of a heuristic in the P v NP book I'm working on. But what about the converse: Can a map have no internal states with an odd number of neighbors and still require four colors. I can come up with some examples but they all require either a lake separating states (like Lake Michigan) or more than three states coming together at a point (like the Four Corners of Utah, Arizona, New Mexico and Colorado).

I wrote this question in terms of planar graphs and asked it on Theory Q&A. Turns out there are no other examples. Take any map, where all internal states have an even number of neighbors with no lakes and no point that borders more than three states and that map can be three colored. Cool.

I'd like to find natural examples, real maps of anywhere where
1) At least two internal regions (to make it interesting)
2) All internal regions have an even number of neighbors
3a) The map is not three colorable (has lakes or more than three regions meeting in a point), or
3b) There are no lakes or more than three regions meeting in a point (so three colorable).

If you are the first to give me an example I use in the book, I'll send you a free copy of the book when it is published.

Are you a Ringer? A Reverse Ringer?

A ringer is an impostor, especially one whose pretense is intended to gain an advantage in a competition. This definition is from Wikipedia and agrees with what I thought the term meant. (Wiktionary has a similar definition. Spellcheck insists that Wiktionary should be either Dictionary or Visionary.)

The following problem appeared in The Bent Winter 2010 issue. (The Bent is a publication of Tau Beta Pi, and Engineering Honor Society.)

Al's job is testing bowling balls. He has two identical bowling balls and is to test their impact resistance by dropping them out of windows on various floors of a 100-story building. He is to determine from which exact floor a dropped ball will shatter on impact with the pavement below. Al knows nothing about the strength of the balls. They may shatter when dropped from the first floor or not until dropped from the 100th floor. What is the minimum number of ball drops needed to guarantee that Al can uniquely determine the floor fro which the balls will shatter. Balls that do not shatter may be dropped again. Both balls may be destroyed during the test. Include a brief outline of how testing is done.

This problem raises questions and metaquestions.

1. What is the answer?
2. A while back I had an undergrad work on the general problem of f floors and e eggs (we used eggs not bowling balls). Hence I know the answer with matching upper and lower bounds for all f and e. Should I submit my answer? If I did would I be a ringer? All you get for submitting a correct solution is your name in the next issue so that would be okay(?). Even so, its seems like cheating. (See here for my students paper. We didn't publish it since a similar paper had already appeared: The Egg Drop Number by Michael Boardman, Mathematics Magazine, Vol 77, No. 5, Ded 2004, 368-372. You can find it here.)
3. When is one a ringer? In a later issue there was a problem I had not seen before but was able to solve easily with graph theory. For that problem am I a ringer?
4. The intent of the problems (I think) is to test your cleverness not your repository of knowledge. With this in mind, clearly if I send in a solution to the Bowling Ball problem, I am being a ringer. For the graph theory problem it is less clear.
5. Once in a restaurant I was doing the kids math puzzles on the paper placemats with my great nieces and nephews. There was one problem that I could solve by brute force but tried instead to find a clever solution (there probably wasn't one). Hence I could not solve it. Or at least that is what my great nieces and nephews think. This might be called being a reverse-ringer. Is there a better term?
6. Here is a problem from Activity book from the NSA on Codes, Ciphers, Puzzles) that is geared towards kids. I was able to do every puzzle in it very quickly except this one. If you know the answer please tell me before some kid asks me:

   Logic Puzzle Number 1: If a railroad train is moving northward, there is a part of each car on the train that is moving southward at each instant, no matter how fast the train is going. what is the contrary piece moving southward? Hint- sketch a train moving on a track and examine the parts you sketch.

What has been your experience with solving (or not) problems that are, in some sense, below your ability and knowledge level?

LICS and TAMC call for papers

Two Call For Papers Announcements:

1. LICS 2011 (Logic in Computer Science) has posted its call-for-papers here. (It was probably posted a while back- the submission deadline is Jan 12, two days from now.) I noticed some people on the committee that are regularly at CCC. How much do LICS and CCC overlap?
   
   In 1987 CCC (then called Structures) co-located with LICS at Cornell. I do not know if that many people went to both (I did not). Some years later I noticed that LICS and CCC were at the same time on different coasts, hence it would be impossible to go to both. Nobody complained (in fact, nobody seemed to notice) so I assumed there is not that much overlap.
   
   SO-I throw the question to those who go to both conferences- is there much overlap? Would people from CCC benefit by going to an occasional LICS? Would people from LICS benefit by going to an occasional CCC? Surely the answer is YES in terms of getting exposure to some new things. But is there a benefit beyond that?
2. (Disclosure- I am on the program committee for this one.) TAMC 2011: (Theory and Applications of Models of Computation) has posted its call-for-papers here. Note that the Submission deadline is Feb 5 and its in Japan. Is it being in Japan make it more or less likely for you to want to go? If you are a theorist in Japan (or close to Japan) then I would assume this is GREAT since its a local. If not then do you view it as (1) too expensive, too much time away from home, so DON"T want to go, or (2) get to see another country! so do want to go! Obviously different people think different things at different times.

The Enduring Legacy of the Turing Machine

Last Februrary Peter Wegner asked if I would be interested in writing an article for a series in ACM Ubiquity on "What is Computation?"

Our expanding collaboration with other fields is broadening our understanding of computation, and it is appropriate to take stock of where we are.  It is likely that the question "What is computation?" will never be completely settled, just as the question "What is life?" is never settled in biology and "what are the fundamental forces?" is never settled in physics.  Engaging with our question is valuable even if we may not find a completely satisfactory answer.

Well I know exactly what computation is, thanks to the beautiful paper of Alan Turing in 1936. My initial reaction was to stay far away but then I realized I had a forum to truly make the point that Turing had the right notion from the start. But as I started writing I realized I didn't have to make any new arguments, Turing himself anticipated the future objections. I just used his words.

The Ubiquity "What is Computation?" papers are coming out once a week. My article, The Enduring Legacy of the Turing Machine, was publshed last week.

Also check out the article by David Bacon who turns the question around. Instead of asking "Can the universe compute beyond Turing Machines", he asks "Why can the universe compute at all?".

What is a breakthrough? Lets have an intelligent discussion!!!!!!

In 2010 this blog announced the following Breakthrough!!!! results: (Listed chronologically.)

1. Better Algorithms for Unique Games, by Arora, Barak, Steurer. (We refer to this as AUG.)
2. Better Circuit Lower Bounds, by Williams. (We refer to this as CLB.)
3. Erdos Distance Problem mostly resolved, by Guth and Katz. (We refer to this as ED.)
4. Progress on Density Needed to Guarantee a 3-AP, by Sanders. (We refer to this as 3AP.)
5. Better Approximation Algorithm for (a version of) Metric TSP, by Gharan, Saberi, Singh. (We refer to this as TSP.)

Some of the comments on those posts questioned if these results really were breakthroughs. This is a fair question; however, in order to answer it the question arises What is a breakthrough? I list some criteria. I'm not sure how many of these a breakthrough needs.

1. The result is correct and the paper is posted. This is mandatory.
2. The problem that the result concerns has to be important. This might be subjective.
3. There has to be substantial progress on the problem. This could be a matter of debate.
4. There has to be a reason why the problem was thought to be hard. E.g., a proof that a new technique is needed, problem has been open for a long time, smart folks say its hard.

So, how do the five breakthrough results look with these criteria? I will now do the very silly exercise of actually giving numeric values to these criteria. The scale is 1 to 10. I do not take these numbers seriously; however, being forced to assign numbers forces one to think about the criteria.

1. AUG: The Unique Game Conjecture is important, hence progress on it in either direction is important. The result was surprising since it may indicate that UGC is not true. IMPORTANT: 8. PROGRESS: 8. THOUGHT HARD: 8. TOTAL SCORE: 24.
2. CLB: If you view this as an attack on P vs NP then the problem being considered is important but the progress on it is not impressive in absolute terms. However, it is very impressive in terms of getting around current barriers. IMPORTANT: 10. PROGRESS: 8. THOUGHT HARD: 10. TOTAL SCORE: 28.
3. ED is certainly very interesting, but is it important? There is a website devoted to it but does that make it important? It has lead to mathematics of importance but that's not quite the same thing. The result makes substantial progress in that it SOLVED the problem (up to a log factor). Smart people thought the proof would require new techniques. It did. IMPORTANT: 6. PROGRESS: 10. THOUGHT HARD: 9. TOTAL SCORE: 25.
4. 3AP is certainly important and has lead to important mathematics. But there are people working in complexity, even complexity bloggers, who do not think this sort of thing is important. They are wrong. Hold the flames- I am kidding. The progress made is more one of technique then result. Many people thought it was hard. IMPORTANT: 7. PROGRESS: 7. THOUGHT HARD: 9. TOTAL SCORE: 23.
5. TSP: The metric TSP problem has had that constant of 3/2 for a very long time. It was possible that 3/2 was optimal. Getting any kind of improvement on it, even a very tiny one, would be very important and would be real progress. Alas the paper didn't quite do that--- it made progress on a version of the problem. Still impressive. I will leave it to people in algorithms to argue if it is a breakthrough or not.
6. In November I heard about the result of on Network flows by Christiano, Kelner, Madry, Spielma, Teng. I had heard that it was a breakthrough. I emailed 5 friends in algorithms asking if they wanted to guest post on it. Nobody wanted to. This is NOT a statement about the paper itself. Reasons were a combination of (a) too busy, (b) don't know the area well enough, and (c) don't want to deal with the idiotic comments your blog often gets. This does NOT mean it was not a breakthrough. It may have to do with my choice of friends. Was it a breakthrough? I still don't know. However, I will now open it up: If someone wants to guest blog about it, let me know.

These are my opinions. What are yours? On these results or on any other ones?

Complexity Year in Review 2010

Complexity Theorem of the year goes to Ryan Williams for his exciting separation of NEXP from ACC⁰. The runner up is Arora, Barak and Steurer for their algorithm for unique games. Also some great progress on some of Bill's favorite questions including Arithmetic Progressions and the Erdos Distance Problem.

None of these papers got mentioned in the New York Times so the most notable paper of the year goes to Deolalikar's P ≠ NP. Many of you got upset that I didn't give this paper the respect it didn't deserve. I did appreciate the publicity the paper generated for our great open problem but the status of the P versus NP question remains: still open.

Last year we highlighted several new blogs. This year the trend is reversing as several theory bloggers have slowed down or stopped blogging. A few of our commentors got very ugly on our blog this year and finally we have given in to comment moderation, though we rarely block.

But social networking in the theory community continues on in other ways highlighted by the Theoretical Computer Science Q&A site. The SIGACT Facebook and Twitter pages have well over a hundred followers each.

The jury is still out on how a near complete change of NSF personnel and the fall elections will affect funding for theoretical computer science. We can always hope.

In this year I started a discussion on remaking STOC. The most popular thing I ever wrote is now this tweet. And don't forget my daughter Molly and her friend Danielle as NP and P.

Gone but not forgotten: Martin Gardner, Joseph Kruskal, Avner Magen, Benoît Mandelbrot, Robin Milner, Partha Niyogi, Sam Roweis and Numb3rs.

Thanks much to our guest posters: Daniel Apon, Paul Beame, Rance Cleveland, Ben Fulton, Josh Grochow, M.T. Hajiaghayi, Bernhard Haeupler, Nicole Immorlica, Subrahmanyam Kalyanasundaram, Clyde Kruskal, Michael Mitzenmacher, Rahul Santhanam, Aaron Sterling, Richard Taylor and Vijay Vazirani. We also thank guest photographer Evan Golub.

Looking forward to 2011 with the big FCRC meeting, learning the location for the Simons Institute for the Theory of Computing and just maybe I'll finish writing my P versus NP book (a bit more than half finished).

America's Most Important Algorithm

Yesterday the Census Bureau announced the new apportionment of the 435 representatives to states based on the 2010 census. Illinois lost one representative. Texas gains four. Not only do these affect the makeup of the House of Representatives but also the Electoral College that chooses the president.

Since 1940 the apportionment is not done by a specific formula but by an algorithm.

• Input: Pop, a population array for the 50 states.
• Output: Rep, a representatives array for the 50 states.
• Let Rep[i] = 1 for each state i.
• For j = 51 to 435
• Let i = arg max Pop[i]/sqrt(Rep[i]*(Rep[i]+1))
• Rep[i] = Rep[i]+1

This algorithm, called the Huntington-Hill method or the Method of Equal Proportions, minimizes the relative difference between sizes of congressional districts.

Check out the Census Bureau video The Amazing Apportionment Machine. 

Implemented naively the running time is O(rn) for n the number of states and r the number of representatives. I'll leave it to you readers to find better implementations. Can I compute how many representatives New Jersey gets from Pop in o(n) space?

Of course with n=50 and r=435 the numbers don't get big enough to cause any problem at all for today's computers. I wonder how long it took in 1940?

BREAKTHROUGH in algorithms: Improved algorithm for Metric TSP!!!!!!!!

BREAKTHROUGH in Algorithms: Improved Algorithm for Metric TSP,

(Guest Blog by Mohammad Hajiaghayi)

We all recently heard about the breakthrough complexity result by Ryan Williams on non-uniform circuit lower bounds. Here is a breakthrough from algorithms side.

All of us may heard about the Christofides' algorithm from 1976 for metric Traveling Salesman Problem (TSP), in which, given an undirected graph G with nonnegative edge weights on the edges satisfying the triangle inequality, the goal is find a shortest possible tour that visits each city once. The algorithm and its analysis is very simple. Create the minimum spanning tree (MST) T of G, find a minimum weight perfect matching M (T-join) in the complete graph over the vertices with odd degree in T, combine the edges of M and T to form an Eulerian circuit and shortcut the circuit by skipping visited nodes. This simple algorithm is a 3/2-approximation algorithm for metric TSP since both the weight of T and twice the weight of M are lowerbounds for the optimum. You can write a natural LP known as Held-Karp relaxation for the problem, for which one can show an integrality gap of at most 3/2 essentially via Christofides' algorithm. For lowerbounds, we know that the integrality gap is at least 4/3 for this LP. (ADDED BY BILL: According to Wikipedia it is known that you can never get an approx better than 220/219=1.00456... times opt, unless P = NP. ADDED LATER: Here is the link to the Wikipedia post and here is the paper by Papadrimtriou and Vempala that contains the result. The post lead me to find it. )

Though Christofides' algorithm seems very simple and easy to improve, so far there has been no progress in this regard despite consistent efforts from 1976. Today I'm happy to announce a breakthrough for this problem by Shayan Oveis-Gharan, Amin Saberi and Mohit Singh.

They obtain a (3/2-c)-approximation algorithm, for some positive constant c, for the graphical TSP where the metric is the shortest path distance in an unweighted graph (a very natural case considered by many so far). Their approach is natural also, they find the tour by sampling a random spanning tree from a maximum entropy distribution defined by the linear programming relaxation of the problem (similar to the approach of Asadpour, Goemans, Madry, Oveis-Gharan, and Saberi from SODA'10 on improved algorithms for asymmetric TSP). Since again the cost of this tree is upper bounded by the optimum solution, it suffices to show that the cost of its Eulerian augmentation (or T-join) is strictly less than half of the optimum. Of course the analysis is not simple at all. According to the authors:

``The first ingredient of the proof is a deeper study of random spanning trees and their corresponding generating functions. We build on a recent and very interesting study of real-stable polynomials and their applications in discrete probability. In particular, we use these techniques to bound the probability of events defined on the parity of the number of edges chosen from a certain subset to be in the random spanning tree. This is crucial for bounding the cost of the T-join.

The other essential ingredient of our proof is a more detailed analysis of the near-minimum cuts of the LP solution. We study the cross graph of (1+d)-near minimum cuts for some d < 1/100 and observe several interesting properties. In particular, we show that the cross graph corresponding to these cuts has a structure very similar to cactuses. Our analysis generalizes to all graphs and it could be of independent interest.''

Amin told me that they should post the paper in arxiv by the end of this month.

Low, Superlow, supersuperlow sets, and Paywalls

Recall the following:

1. If A is a set then A' (pronounced 'A jump') is the halting set relative to A. Formally it is:

   { e | M_e^A(e) converges }

2. A set A is low if A' &le_T HALT.
3. A set A is superlow if A' &le_tt HALT.

There is a well known construction of an undecidable low c.e. (What I call c.e., computably enumerable, used to be called r.e., recursively enumerable. See Soare's article for why the change makes sense.) This is one way to get an intermediary Turing Degree. However, it turns out that the set is not just low, its superlow. Consider the following definition of supersuperlow which I made up:

A set A is supersuperlow if A' &le_btt HALT.

I wondered if there exists an undecidable supersuperlow set. I asked four prominent computability theorists (spellcheck wanted me to write computable theorists). They all (1) thought it was a good question, (2) thought the answer was NO and KNOWN, and (3) didn't have a proof or reference. I then asked Carl Jockusch and he (1) thought it was a good question, (2) knew the answer was NO and KNOWN, and (3) had both a proof and a reference.

Since they all thought it was a good question, and because papers that contain the needed results are behind paywalls or unpublished, and hence lost to humanity forever, I did an exposition, which you can get free online here where I present the following:

1. The classic proof that there exists an undecidable c.e. low set.
2. Comments on this classic proof that show how it really resulted in an undecidable c.e. superlow set.
3. A complete unpublished proof that if A is supersuperlow then A is decidable.

Should I add more to it and make it a real survey for a real journal?

1. PRO: The referees comments may help improve it.
2. PRO: If the journal is free online then it will be better archived.
3. PRO: I will get to learn all of this material.
4. PRO: A paper on my resume.
5. CON: Referees can be a pain in the neck.
6. CON: Math arXiv is just as good, perhaps better, than a journal for archiving (I will certainly polish it a bit and submit it to math arXiv at some point)
7. CON: I will have to learn all this stuff. Do I care beyond what I have already found out? I stopped doing recursion theory back when it was still called recursion theory. Now I'd rather spend my time and energy on Ramsey Theory and other things. (I could, of course, do a survey of Computable Ramsey Theory. Sample theorems by Carl Jockusch: (1) If COL is a COMPUTABLE 2-coloring of the edges of the complete graph on N then there exists a &Pi₂ homogeneous set. (2) There exists a COMPUTABLE 2-coloring of the edges of the complete graph on N such that no homogeneous set is &Sigma₂. There is one problem with that: I already did! Its part of my survey of recursive combinatorics.
8. CAVEAT: Is having a survey on my resume that valuable? I ask this non-rhetorically which is why this is a CAVEAT rather than a CON.

Math- Old School

In the last month we have reported on NEW RESULTS by Williams, Katz and Guth, Sanders, and Pinkerton and Setra. For a change of pace lets look at some really OLD math from a really OLD book- the Bible. (NOTE- this has nothing to do with whether the Bible is true, just that its old.)

In Genesis 18 God wants to destroy Sodom and Gomorrah. Abraham wants to argue against this. Here is a paraphrase using modern terms.

GOD: If there are 50 righteous people in Sodom then I will spare the city.

ABRAHAM: What if there are 45? 45 is pretty close to 50.

GOD: Okay. If there are 45 righteous people then I will spare the city.

ABRAHAM: What if there are 40? 40 is pretty close to 45.

GOD: Okay. If there are 40 righteous people then I will spare the city.

ABRAHAM: You know, uh, 30 is pretty close to 40.

GOD: Okay. If there are 30 righteous people then I will spare the city.

ABRAHAM: 20 is only 10 less than 30 so how about....

GOD: Okay. If there are 20 righteous people then I will spare the city.

ABRAHAM: 10 is only 10 less than 20 so how about....

GOD: Okay. If there are 10 righteous people then I will spare the city.

ABRAHAM: Good. (He stops bargaining. Perhaps he shouldn't have--- They couldn't find 10 and the city was destroyed.)

I think Abraham should have used smaller increments as he went down since going from 20 to 10 is cutting it in half which sounds like a lot. But who am I to argue--- he got God down to 10 which is impressive even though it didn't work.

This reminds me of two paradoxes:

1. The Small Number Paradox. All numbers are small. Proof by induction. Clearly 0 is small. If n is small then adding 1 can't make it much bigger, so n+1 is small. Hence all numbers are small.
2. The Sorties Paradox also called The Heap Paradox. 1,000,000 grains of sand makes a heap. If n grains of sand make a heap then so do n-1 grains of sand. Hence 0 grains of sand make a heap.

Is the passage in Genesis 18 really math? In a very primitive form I would say yes. Is there any older source for anything that resembles math?

46 free lunches!

(CONGRADS to all the new ACM fellows. Among them are theorists Jennifer Chayes, Anne Condon, Phil Klein, S. Muthu, and Dan Spielman.)



In my post about mentoring High School Students I noted that for every $1000 my HS mentees win in math and science research competitions I get a free lunch. Two of my students, James Pinkerton and Rafael Setra entered the Team Siemens Competition and won $23,000 each! (The article says $20,000 but James and Rafael tell me it's $23,000.) Looks like I will be eating well for a while. If you visit UMCP and they are free for lunch with us then you can have a free lunch from them.

1. Here is the announcement of the winners. They came in third place in the team category.
2. Their project was on DUPLICATOR SPOILER games. (Like most games defined in math papers this game is not fun.) Recall that these games provide a way to prove certain properties are not expressible in certain languages (e.g., well-foundness for linear orderings is not first-order expressible). These games go for a FINITE number of moves that is specified before the game begins. They looked at these games when the number of moves can be an ordinal. Here is how it works: (1) at the beginning of the game there is a counter that has in the ordinal &alpha, and (2) after SPOILER makes his move he decrments the counter to some ordinal &beta < &alpha of his choice. Here is one result: for any ordinal &alpha there exists two linear orderings L₁ and L₂ such that if the game is played with these two orderings and both DUPLICATOR and SPOILER play perfectly then SPOILER wins the game in exactly &alpha moves. This is not just an existence proof- they actually say what the orderings are. They are natural in that they were not constructed just for the purpose of having this property.
3. Here is their paper.
4. The money actually goes towards tuition and other college-related expenses.
5. What is the secret of mine or their success? There are two things that are needed here (this applies to ugrad projects, Masters Thesis, PhD thesis, and, if properly generalized, to life):
   1. Student that are hard working, intelligent, and care about the material. (James actually thinks Dup-SPOILER games are fun!)
   2. A project that is doable.
6. Note that if a project doesn't go very far it might be that the PROJECT wasn't good or that the STUDENTS weren't good. This happens quite a bit, though ALWAYS something can be salvaged for a high school project.
7. I usually get to re-use projects since some students don't do a good job or give up. This was the FIRST TIME I had done the DUP-SPOILER GAMES WITH ORDINAL NUMBER OF MOVES project. Now, alas, I can't use it again.

Do Uniform Lower Bounds Matter?

From Ryan Willams' paper:

Non-uniform lower bounds establish impossibility results for computation in the physical world: it could be that P ≠ NP, yet NP-complete problems can still be efficiently solved using a “bloated” program with sufficiently many lines of code. Non-uniform circuit size lower bounds for NP would rule out this possibility.

The class P contains a language L where have a single fixed program that efficiently solves L for all inputs at all lengths. L is in P/poly if for every length n there is a program of size polynomial in n that efficiently solves L for all inputs of length n. The programs for two different lengths may have no relation to each other.

Karp and Lipton showed that if NP is in P/poly then the polynomial-time hierarchy collapses so we generally don't believe that NP is in P/poly. Suppose though we lived in a world where NP is in P/poly but still P ≠ NP.

In one argument, even though we study complexity in asymptotics we generally live at one input length, the size of the problems we want to solve. Once we find the program that works at this length then P = NP for us, even though P ≠ NP in general.

But the only constant over time is time itself. An hour now is the same as an hour in 1971, but the amount we can compute in that hour has grown dramatically. We don't care about fixed problem sizes, rather we care about the largest problem we can solve in a given amount of time. As our technology gets better, those input sizes also grow. For problems in P, like linear programming, the algorithms we have for smaller inputs also work on larger inputs by just increasing the computation time. However, if NP is in P/poly the code for NP-complete problems that worked a few years ago may fail miserably now as we may have to find completely different code for the larger inputs we care about now. If P ≠ NP we can't have an efficient process to find that code even though we know it exists.

A BREAKTHROUGH result on density and 3-AP's

We use the following terminology: [n] means the set {1,...,n}. k-AP means an arithmetic progression of length k. A 3-free set is one with no 3-AP.s in it. We use the following conventions: (1)all inequalities have a big-O or big-&Omega which we do not include, and (2) we have the pointers to the papers be at the authors name when possible.

The following result was posted Oct 30, 2010 by Sanders.

For large n, for all A &sube [n], |A| &ge n(log log n)⁵/log n then A has a 3-AP.

I give the history and some misc information about the result.

1. In 1927 van der Waerden published the following theorem which is now known as van der Waerden's theorem:

   For all k, for all c, there exists W=W(k,c) such that for all c-colorings of [W] there exists a monochromatic k-AP.

   Online sources: (1) Wikipedia, (2)blog by Gilish Varma, and (3) preprint of a book by Gasarch et al .The upper bounds on W(k,c) from the original proof and the links (which are essentially the same) are BIG. In particular they are not primitive recursive. (NOTE- if you know of an online source for van der warden's original article and/or a translation into English, let me know.)
2. Erdos and Turan(you'll need to scroll down some) wanted an alternative proof of this theorem with smaller bounds. To this end they made the following conjectures:
   1. (ER1) For all k, for all &epsilon for large enough n, for all A &sube {1,...,n} such that |A| &ge &epsilon n, A has a k-AP.
   2. (ER2) Let A be a set of natural numbers. If &Sigma_{x ∈ A} 1/x diverges then A has arbitrarily long arithmetic sequences.
   Both of these imply VDW's theorem. The hope was that they would provide new proofs with better bounds.
3. Roth showed ER1 for k=3. In fact, he showed the following: for large enough n, for all A &sube {1,...,n} such that |A| &ge n/log log n, A has a 3-AP. The proof used non-combinatorial methods. For an online proofs see either Terry Tao's blog or Alex Iosevich's notes.
4. Szemeredi proved ER1 for k=4 and then for general k. The proof for general k used VDW's theorem and hence did not provide better bounds for W(k,c). Szmeredi's Regularity Lemma which he developed to prove it, has found many many applications. His proof for k=4 was purely combinatorial. A scaled down version of it for k=3 was presented in Graham-Rothchild-Spencer in about 2 pages. For an online exposition of this see pages 121-130 of Gasarch et al. For an online exposition of the proof for the general case see this exposition by Tao.
5. Furstenberg obtained a different proof of ER1 using ergodic theory. This proof was nonconstructive and hence yielded no bounds on the VDW numbers. His technique was later used by Bergelson and Leibman to prove the poly VDW theorem and Poly HJ Theorem. Later Walters found a combinatorial proofs for both. See also the exposition by Gasarch et al.
6. Shelah obtained primitive recursive bounds on the VDW numbers. His proof was purely combinatorial.
7. Gowers proved ER1 in a way that lead to much better bounds on the VDW numbers.
8. A purely combinatorial proof of the Density Hales-Jewitt theorem was done by the polymath group. This is likely the easiest proof of ER1.
9. Green and Tao showed that the set of primes have arb large arithmetic progressions. Aside from this, there seems to have been little progress on ER2. Some people think ER2 should replace Poincare's conjectures on the list of Millennium Prizes.

That would seem to be the end of the story for now. ER1 was proven in a way that lead to better bounds on VDW numbers. But notice Roth's theorem. The condition on the density of a set that lead to a 3-AP are better than ER1. There have been improvements on Roth's theorem.

1. Szemeredi and Heath-Brown obtained the following result independently: There exists a constant d such that, for large enough n, for all A &sube [n], |A| &ge n/(log n)^d, A has a 3-AP. There is a nice exposition by Green (NOTE- if you know of an online source for the original papers let me know.)
2. Bourgain obtained the following result: for large enough n, for all A &sube [n], |A| &ge n((log log n)/log n)^0.5 A has a 3-AP.
3. Bourgain improved his result to: |A| &ge n/(log n)^2/3-o(1)
4. Sanders improved Bourgain's result to |A| &ge n/(log n)^3/4-o(1).
5. Sanders NEW result is that we only need |A| &ge n(log log n)⁵/log n.

OKAY- why is this important? It breaks a barrier that seemed very stubborn and it also leads to better bounds on W(3,c):

Let f be a function such that for large enough n, for all A &sube [n], |A| &ge f(n), A has a 3-AP. Assume [n] is c-colored. Some color must appear n/c times. If n/c &ge f(n) then there is a 3-AP. Hence we need n/f(n) &ge c. So if n/f(n) &ge c then W(3,c) &le n.

1. Roth's result yields that W(3,c) &le 2^2O(c). ( Graham and Solymosi obtained this result purely combinatorially.)
2. Szemeredi's and Heath-Brown result yields W(3,c) &le 2^cO(1).
3. Bourgain's first result yields W(3,c) &le 2^{c2log c}.
4. Bourgain's second result improves the exponent of c from 2 to 3/2-o(1)
5. Sanders's result results improve the exponent of c from 3/2-o(1) to 4/3-o(1).
6. Sanders NEW RESULT yields W(3,c) &le 2^{c(log c)5}.

The theorems above are of the form: If A is big enough then A has a 3-AP. What about the other side of the ledger: How large can 3-free sets be? There has been an empirical study for small n by Gasarch et al., an unpolished (not yet submitted) survey by Gasarch et al.. (ADDED LATER- SOMEONE POSTED A WEBSITE WHERE YOU CAN FIND ACTUAL LARGE 3-FREE SETS. here it is.) Behrend had the largest 3-free sets for about 50 years before Elkin obtained an improvement. A shorter proof of Elkin's result was given by by Green and Wolf. The current state of affairs on this was summarized in a nice blog entry by Gil Kalai.

Do these result help find lower bounds on W(3,c)? YES! Chandra-Furst-Lipton in their paper on multiparty protocols (of all things!) showed that if A &sube [n] and A is k-free then there is a coloring of [n] with nlog n/|A| colors without any k-AP's. Its an easy prob argument.

SO- how far are we from showing ER2 in the case of k=3? If Sanders NEW result could be improved to |A| &ge n/(log n)^1+&delta or even |A| &ge n/log n (log log n)^1+&delta or any function such that if you divide by n² the series converges then ER2 for k=3 would be proven. How far away is this result? A few weeks ago I would have told you that getting NEXP not in ACC⁰ was not in likely for at least 20 years. Ryan Williams proved me WRONG! Two different knowledgeable sources told me personally that the Erdos Distance Problem had reached an impasse at n^0.864. Guth and Katz proved them WRONG and me WRONG for believing them. Hence, for this one, I do not venture a guess.

What about k-AP's and k-free sets?

1. Gowers has shown that there is a constant c such that if |A| &ge n/(log log n)^c then A has a 4-AP. Gowers also proved that a function c(k) such that if |A| &ge n/(log log n)^c(k) then A has a k-AP. In the paper cited he takes c(k) to be 2^-2k+9; however, I have heard this has been improved.
2. Green and Tao. have shown that there is a constant c such that if |A| &ge n/(log n)^c then A has a 4-AP. Tao's website also indicates they have improved this and a paper is in preparation.
3. Laba and Lacey have a construction of k-free sets which it turns out was already known.

This post has 35 distinct links (UPDATE- now its 37) and mentioned four Field medalists: Roth (1958), Bourgain (1994), Gowers (1998), and Tao (2006). These are probably both complexityblog records.

For more information on this NEW result see also a nice blog posting by Gil Kalai.