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.