Acknowledging anonymous blog comments

Twice times now I have gotten an anonymous comment on this blog that I may want to use in either a paper or my (never-ending) web-monograph on VDW stuff. They are

1. Anonymous posted a combinatorial proof of a summation. See comment 6.
2. Former VDW ugrad posted that the exact bound of polyvdw(x2,3)=29. See comment 11. I asked the obvious people, and they all deny they posted it.

If I use these proofs then I will reference the blog link (how long these links last?) and also give the full proof. I would also like to acknowledge the people who came up with those proofs. How to do this

I would like to thank Anonymous ....

and

I would like to thank Former VDW ugrad...

do not seem like I am really giving them credit. So, what to do? I make the following request:

If you are one of the two people above please email me who you are and which entry you posted.

Will this work? There are two concerns.

1. That nobody will respond.
2. That too many people will respond. How do they verify who they are?

Will this be a bigger problem in the future? If so then future textbooks may have

P vs NP was resolved by kittykat17.

Amihood Amir more famous than Dick Cheney

(Guest post by Richard Beigel.)

Top-9 list of internet fame criteria. You know you are famous when ...

9. You show up on the first page of google hits for your full name (Richard Chang)
8. You take up all 10 slots on the first page of google hits for your full name (Carolyn Gasarch)
7. You show up on the first page of google hits for your last name (Lance Fortnow, Johnny Carson)
6. You take up all 10 slots on the first page of google hits for your last name (Bill Gasarch)
5. You show up on the first page of google hits for your full name ... even when it is misspelled (Richard Beigel)
4. You show up on the first page of google hits for your job title (Richard Cheney)
3*. You show up on the first page of google hits for your first name (Amihood Amir, Don Knuth, Lance Armstrong, Johnny Depp, Johnny Cash)
2*. You show up on the first page of google hits for your initials (Richard M Stallman)
1. You show up on the first page of google hits for your middle initial (George W Bush)

*It was hard deciding which of these two should come first, but Richard Stallman shows up under both and, surprisingly, Don E. Knuth doesn't show up under 2.

Disclaimer: These criteria are intended for the purpose of humor only. They do not represent the opininion of the Natiοnal Science Fοundation or the the Federal Gοvernment, and they will not affect your chances of getting a grant. ~

Olympic Markets

What do the Olympics have to do with computational complexity? Not much, so while I have spent much more time watching the games than proving theorems this week I couldn't think of the right way to fit it into the blog. Until I got the following email from David Pennock yesterday.

We implemented Olympics medal count prediction on Yoopick. Since it was your idea, you now have a moral obligation to blog about it, use it, and evangelize it to all your friends. :-)

Where most prediction markets track binary events, like whether the Obama will win the election, the Facebook-plugin Yoopick, developed at Yahoo Research in New York, is a fake-money market that predicts distributions over a range like the number of points scored in a basketball game. I suggested using Yoopick to predict the distribution of medals won by county and now you too can make your predictions and win some Yootles. I hear 100 Yootles and 2 Dollars will get you a subway ride in New York.

In other Prediction Market stuff at Yahoo, Sharad Goel used Amazon's Mechanical Turk to offer 100 people three cents each to predict the probability that Obama will win. The predictions were all over the place but average them up and you get exactly the same value as Intrade. Not the first time we've seen this phenomenon and it seems hard to explain.

And don't forget to check our our Electoral Markets Map. Obama has the slight edge as we get closer to the conventions and start of the real campaign season.

AI Follows Theory

In one of the 2006 AAAI Outstanding Paper Award Winners Model Counting: A New Strategy for Obtaining Good Bounds, Gomes, Sabharwal and Selman show how to approximately count the number of satisfying assignments of a Boolean formula with a SAT solver. They add random parity constraints ala Valiant-Vazirani and approximate the number of solutions based on the number of constraints needed until the formula is not satisfiable.

Sounds like a neat idea that complexity theorists should have come up with in the 80's. And we did, where by "we" I mean Larry Stockmeyer in his 1985 SICOMP paper On Approximation Algorithms for #P. Stockmeyer uses random hash functions from Sipser but it is essentially the same algorithm and analysis as Gomes et. al.

Stockmeyer wrote a purely theoretical paper. Since then we have better algorithms and much faster computers and one can now solve satisfiability on non-trivial input lengths. Gomes et. al. write the paper as a practical technique to approximate the number of solutions and even implement their algorithm and contrast with other programs that exactly count the number of solutions.

Gomes et. al. mention Toda's paper on the hardness of exact counting but don't cite Stockmeyer or any other paper in the vast theory literature on approximate counting.

We complexity theorists know many other nifty things one can do with an NP oracle such as uniform sampling and learning circuits. Read them now so you don't have to reinvent them later.

Ridiculously hard proof of easy theorem

Justin Kruskal is a High School Student working with me on VDW stuff (of course). The following conversation happened recently.

BILL: Justin, you've seen a proof of VDW's theorem, but there are easier things you haven't seen and should. Can you prove that the number of primes is infinite?

JUSTIN: Thats easy.

BILL: Good. How does it go?

JUSTIN: By the Green-Tao Theorem there are arbitrarily long arithmetic sequences of primes. Hence there are an infinite number of primes.

What to make of this?

1. Justin does not know how to proof the Green-Tao theorem (neither do I). However, if the proof does not use the fact that there are an infininte number of primes, then Justin's proof is valid. READERS: does anyone know, does it use the infinitude of the primes?
2. Justin now knows the standard proof. However, he should also learn that, at the level of math where he is at, you should be able to prove everything you use.
3. When does one start using theorems whose proofs one does not know? In research this is common. For basic coursework it should be rare.

Math Problems on vacation

SO, as mentioned in my last post, there were two other math-folks on the bus tour I was taking. So what did we do? Exchange problems to solve on the bus. We alternated.

1. I asked them: if there are n couples in a resturant, and everyone sits either across from or next to their darling at a rectangular table (nobody sits at the ends) then how many ways can they be seated?
2. They asked me: A marathon is 26.2 miles. A runner runs in such a way that during EVERY 1-mile interval he averages exactly 10 miles an hour. But his overall time is better than 10 miles an hour. How can this be?
3. I asked them: Show that if no matter how your 3-color the numbers {1,...,2006} there will be two points, a square apart, the same color.
4. They asked me: There is a bus where n people have assigned seats. The first person sits randomly instead of in his assigned seat. Henceforth, every person looks for his assigned seat, and if he does not find it, sits in a random seat. What is the prob that the last person sits in his assigned seat?

How did we do on these problems? They got my problems correctly. I basically got theirs (missed some points).

It was interesting coming up with problems that had not well known. I couldn't ask them truth-teller-and-liar problems or hats problems, since these are well known. Some of the problems above have appeared on this blog before. Not sure if that makes them well-known. At least they didn't know them. I tried asking the following problem that I thought was not so well known (I read it in American Math Monthly and told it to Peter Winkler two years ago-- he had not heard of it), but they had already heard it:

Here is a game: There are initially two piles of stones with a in one pile and b in the other. Every move a player removes a multiple of the smaller pile from the larger. If either pile has 0 in it then you cannot move. THe first player who can't move loses. For which (a,b) does player I have a winning stradegy.

Readers- I am not going to post solution. But you can in the comments!

What is the probability that ...

(I've been on vacation for the last 10 days on a Tauck Bus Tour of Canada with Heli-hiking.)

What is the probability that a bus tour has on it two people that know the proof that S2S is decidable? (Original Proof by Rabin is here. For reviews of several books on the topic see here.)

1. Not a trick question. The bus tour was not organized by the Association of Symbolic Logic.
2. The prob seems like it would be low. But this is not the right way to look at it.
3. This did happen. Suzanne Zeitman was on the tour. I learned about the proof from her (excellent) writeup which, alas, is not online. It is incorporated in the book The Classical Decision Problem by Borger, Gradel, Gurevich.
4. Should I be saying `WOW! that is so unlikely, yet it happend!'. No. Consider the following fictional conversation:
   
   BILL: The most amazing thing just happened! I just tossed a coin 40 times and got HHTTTHTHTHTHHTTTTHTHTHTTHTHHHTTHHTHTHHTH.
   
   LANCE: Why is that remarkable?
   
   BILL: Because the prob of that particular sequence is so small!
5. The prob that someone the distance away from me which Suzanne Zeitman is (I have written some math reviews for her and been in some email contact) happens to be on the same bus trip as me may be low, but its not so low as to be astonished if it happens. This is my third bus trip and the first time it happened. Is the probably 1/3? I doubt that, but its not so low as to be notable.
6. If before going on the trip I had said Gee, I wonder is someone who knows the proof that S2S is decidable will be on the tour? then THAT Would be notable.
7. What is the prob that the maintainer of the Erdos-Number Website was, Jerry Grossman, was on the trip? This is a trick question-- Jerry Grossman is Suzanne Zeitman's husband.
8. What is the prob that on the trip there were people who know, through their homeowners association, Steven Simpson an eminent logician who works on Reverse Mathematics, who I know. This did happen. Not a trick question, but again, not that notable.

Discounted Time

A write-up of some ideas I presented at the Complexity Conference Rump Session.


In computational complexity when we talk about time it usually represents a hard limit in the running time, solving the problem in time t(n). So we are happy, say, if we can solve the problem in one hour and miserable if it takes 61 minutes. But our real gradation of happiness over the running time is not so discontinuous.

Let's take an idea from how economists deal with time. They discount the utility by a factor of δ in each time step for some δ<1. What if we did the same for complexity?

Let δ = 1-ε for ε>0 and very small. Think ε about 10^-12. We then discount the value of the solution by a factor δ^t for t steps of computation.

Discounted time gives us a continuous loss due to time. It has the nice property that the future looks like the past: The discount for t steps now is the same as the the discount for the t steps already taken.

When t is small, δ^t is about 1-εt, a linear decrease. For t large, δ^t is about e^-εt, an exponential decrease.

We can also recover traditional complexity classes. DTIME(O(m(n)) is the set of languages such that for some constant c>0, δ^t>c for δ=(1-1/m(n)).

I'm not sure what to do with discounted time which is why this is a blog post instead of a FOCS paper.
Some ideas:

• What does average case and expected time mean in the discounted time model?
• What if you take the value of the solution of some approximation problem and discount it with the time taken? Can you determine the optimal point to stop?

The Gaza Fulbright Story

A story that has gotten far less press than it should have.

Seven Palestinians in Gaza received Fulbright grants this year. In May the US State department cancelled the grants because Israel closed the border between Gaza and Israel and the State department was afraid they couldn't get them out. After some noise got made, Condoleeza Rice stepped in and got the grants reinstated. Israel let in four of the seven so they could go to the American consulate to get visas but denied the other three for security concerns. For the other three, Rice got the state department to send a team and equipment into Gaza to help the remaining students who eventually got visas on July 30th.

Sounds like a happy ending. Alas that's not the end of the story.

A few days later, Fidaa Abed, one of the three, flew from Jordan to Washington and when he landed he learned that his visa was no longer valid. He was put back on a plane to Jordan. The other two hadn't left yet but their visas were also canceled. The decision to revoke the visas came after the US State Department received more information, probably from Israel.

More from the New York Times and the BBC.

A Theory of Reductions?

A guest post by Jens Zumbraegel

I am working on cryptography, and I came across complexity theory only recently. My question is whether a general framework for the various types of reduction exists. Let me give motivation:

The concept of reduction in order to compare the computational hardness of algorithmic problems is a very important one. However many types of reductions are used in the literature for different purposes. Trying a rough classification:

• "Classical" complexity theory: Karp/many-to-one or Cook reductions
• Average-case complexity: Karp reductions with a domination condition between distributional problems
• Cryptography: "reducibility arguments" in "provable security", i.e. ad-hoc reductions of the problem BREAKING-THE-CRYPTOSYSTEM to some well-known hard number theoretic problem, like FACTORING

I believe that a reduction theory for cryptographic purposes could simplify and structure many results in the area of provable security. Apparently there is not yet such a theory. One reason might be that although informally stated problems like "breaking the cryptosystem" have been formalized they do not fit into the framework of decision or search problems (they often involve oracle access for e.g. deciphering).

Back to my question - I wonder whether there is a general abstract theory of reductions, probably similar to category theory: One defines the class of algorithmic problems (the objects of the "category") and the type of reductions (the morphisms) one would like to consider. For example: (decision problems for languages in {0,1}^*, Karp reductions). Such a general framework could help to set up a reduction theory for cryptography.

Comments most welcome!

A Simple Heuristic

When I started off as a professor, my wife worked at a company called Teradyne, which makes testing equipment, as a master scheduler. A master scheduler makes the master schedule of what jobs get run on which machines at what time. As you readers already know, almost every interesting variation of job scheduling is NP-complete. As I was teaching intro theory at the time, I thought about bringing her in to give a lecture on how people deal with NP-complete problems in the real world.

So I asked my wife what algorithms she uses to make up the schedule. She had a simple rule:

Whomever yells the loudest gets their job scheduled first.

Needless to say I didn't bring her into class.

Analysis in Complexity

A shout out to my colleagues who have gathered in Banff for the BIRS workshop on Analytic Tools in Computational Complexity.

An important development in the study of computational complexity has been increased role of analytic methods. Fourier analysis has become an essential tool of the field, playing a critical role in the study of interactive proofs, the computational hardness of approximation problems, and the learnability of Boolean functions. The notion of Gowers uniformity (which was introduced by Gowers to give an analytic proof of Szemeredi's theorem on arithmetic progressions, and whose use can be viewed as "generalized Fourier analysis") has also been recently employed in the context of Probabilistically Checkable Proofs and hardness of approximation. A new paradigm in computational complexity is beginning to emerge, which involves reducing high dimensional discrete problems that arise in the study of Boolean functions to high dimensional continuous problems and then applying analytic methods to the resulting continuous problems.

I started graduate work in complexity right before the algebraic revolution that drove Razborov-Smolensky's circuit lower bounds, Toda's Theorem on the power of the permanent, the power of interactive and probabilistically checkable proofs and much more. But now, two decades later, algebraic techniques are producing diminishing returns and we have seen a growth in using real analysis in complexity as highlighted by this workshop. Avi Wigderson is giving a two-hour survey on "The Power of Partial Derivatives." Hard to have imagined a connection between partial derivatives and complexity.

What about those of us who went into computational complexity because we enjoyed discrete math? Should an old dog like me try to learn new tricks? Ah, the challenge of keeping up with a field that moves in mysterious new ways.

Complexity Special Issue

Here are the results of the vote taken after the special issue debate at the Complexity conference business meeting. The conference committee decided to stay with the Springer journal Computational Complexity for three more years and revisit the issue in 2011.

For those not invited to the special issue: I'd love to see your papers in ToCT but in any case please do submit to any of our community's fine journals. A conference proceedings should not be your paper's final resting place.

Psychological Proofs and Reverse CAPTCHAs

Guest Post from Amir Michail.

The goal behind a psychological proof is simply to convince most people of something. And that's all that's required. A psychological proof may be complete nonsense but as long as it convinces most people—namely, those of average intelligence—then it can be considered a success.

Such proofs can be useful on the web, particularly when a proof that would be convincing to intelligent experts is impossible. Moreover, such proofs need not be deceptive (e.g., as with phishing). You could have a nonsensical/weak psychological proof to convince most people of something that is actually true anyway, so no harm done.

As an application of psychological proofs on the web, consider "reverse CAPTCHAs" within the context of chatbots. It is important to give people chatting with chatbots some confidence that *all* the bot replies are really bot replies—and not something typed in by a human watching the chat.

The problem is to somehow convince most people that you are really a chatbot and not a human. The method used should give them more confidence than simply telling them so.

While chatting with the bot from chatbotgame.com, you can get this confidence by clicking "Convince me you're a bot!". The idea is to show you the rule/method that was used to generate each bot response. Note that you can see rule usage in other chats by clicking accepted/rejected. This gives you more confidence that a rule was submitted prior to seeing its bot response in your chat.

I would be interested in knowing about other uses of psychological proofs on the web to convince most people of something that is true anyway.

Proceedings

Conference proceedings used to be dirt cheap. The ACM and IEEE would supply proceedings to a conference at a small loss because they could sell later copies of those proceedings to libraries and individuals at a large mark-up. Conferences would order extra proceedings because they could sell the excess at double the price during the conference to attendees who wanted copies for friends. I remember going to STOC or FOCS and buying an extra 7 or 8 proceedings and shipping them back to Chicago for those who didn't go.

But that's all changed. Libraries now subscribe to digital libraries—they don't buy paper proceedings anymore. Hardly anyone ever opens their proceedings anymore after the conference ends so no extra proceedings are sold. The per proceedings price goes up as the number printed go down and conferences try to order just to cover the number of expected attendees. For a typical medium-sized conference, the proceedings can add $50 to the average registration fee. That's expensive for a book that will only be used for a couple of days. So why should conferences stay with paper proceedings instead of going electronic (via CD or Internet)?

• Tradition.
• Some people like to look at a paper for a talk during the presentation. Sometimes I see a speaker say something that doesn't sound right and looking in the proceedings to figure out what they really meant. Some other people even take notes in the proceedings.
• Status. Until STOC and FOCS move to electronic proceedings, other theory conferences might worry about their relative importance if they don't do paper.
• Authors like to see their papers in print. And the vast majority of attendees at any theory conference are authors.

Eventually this point will be moot when electronic books become an acceptable reality. Even today the NSF could save money by buying each of their PIs a Kindle and refusing to fully reimburse conference fees that have paper proceedings. But computer scientists always do seem behind the curve in adapting new technologies.

Rules for Success

Randy Pausch, a CS professor at CMU, passed away on Friday. That gave me the impetus to watch his famous last lecture video. You should really take the time to watch it if you haven't already.

Pausch talks mostly about childhood dreams. Makes one think about my own childhood dreams: Alas, someone else beat me to Fermat's last theorem and driving the A-train doesn't seem as exciting now as it did to the 5-year old me.

But Pausch's talk really emphasizes his simple keys to success:

• Make the right connections.
• Be Persistent.
• Be Patient.
• Work Hard.

Now those are rules to live by.

Movie Time

Catching up with some more movies, 21 on DVD and Dark Knight in the theater. Usual minor spoiler warnings.

We've already talked about the Monty Hall problem in 21. But what I don't really understand is why does this math whiz want to be a medical doctor? Is it just a given that this is a better direction in life than getting a Ph.D? Not that card counting has anything to do with real math.

There has been quite a bit of talk of game theory in the Batman movie (e.g. here, here and here). But the whole point was that the people did not play to their own self interests, it was more of a psychological/moral study. It did remind me of the best strategy in the game of chicken, to tear out one's steering wheel and throw it out the car (making sure the other person sees you doing it).

For anyone who lives in Chicago, Gotham City was Chicago in the movie, not really hidden at all. In fact one could consider this movie the best Chicago movie since the Blues Brothers. This caused some confusion in the plot. After all where are those ferries going to? Michigan? No I had to remind myself this was Gotham, not Chicago, and those ferries must be going to, um, New Jersey.

Nick Reingold

Nick Reingold passed away July 3 from a pulmonary embolus. As a graduate student at Yale, Nick co-authored one of the classic papers in computational complexity, PP Is Closed under Intersection, and Nick and I worked together on a follow-up. He then moved to AT&T and wrote many more papers mostly on on-line algorithms.

Nick was a good friend and colleague. The theory community lost a good man.

Vinyl Record Bowls

Walking through an small art fair recently we came across a booth selling vinyl records deformed into bowls. They proudly kept a long list of classic rock albums they had desecrated to create those bowls. What kind of world do we live in where one takes great music and turns it into a vessel to hold dog food?

I reacquired a phonograph player a couple of years ago but I admit I rarely use it. The problem is technical: You can only get at best 23 minutes of continuous play from a record, as opposed to 75 minutes from a CD or days from my iPod. Somehow I survived childhood changing the record every 20 minutes or so but I'm not sure how.

When my children first saw a vinyl record they just called it a large CD and they didn't know who I would fit it in a player. Their children will likely never know physical media for music at all. Let's see them make a bowl out of an MP3.

A Nonconstructive argument about the election

I have heard several times in the media the following nonconstructive proof that Obama will win the election. They, of course, do not call it a nonconstructive proof. Since politics is far less predictable and rigorous than math I do not really buy the argument, but its of some interest to me that there is a nonconstructive argument in politics. Here is how we might phrase it. There are two cases.

1. The Iraq war goes well. Then the Iraq war is off of the front pages. In this case, McCain's advantage, that he is seen (rightly or wrongly) as being better to have as prez when we are at war, is nullified. Hence Obama, which is seen (righly or wrongly) as being better on domestic issues will win.
2. The Iraq war goes badly. Then Obama can say (or he might not even need to say so explicitly) that he was right about the war being a mistake in the first place.

What is wrong with this argument?

1. The election may hinge on so many other things: a scandal, a mistatement, obvious things I am not mentioning, nonobvious things that have not come to light yet.
2. The Iraq war might go (or be portrayed as going) some intermediary thing which is neither well or badly. In fact, the very terms well and badl are not well defined.
3. More generally, its very hard to apply simple logic to an election. Or complex logic.

Open Math Problems easy to state to layperson

What open math problem is the easiest to explain to the layperson? Fermat's Last Theorem and the 4-color problem used to be the gold standard. How about now? Here are some candidates:

1. Goldbach's Conjecture Is every even number (except 2) the sum of two primes? PRO: If the layperson knows what primes are then this is easy to explain. PRO: Give examples easily: 4=2+2, 6=3+3, 8=3+5. The layperson can even generate these! CON: Can't really say why its important. THOUGHT: You can say that primes are important for crypto.
2. Twin Primes Conjecture. Are there are an infinite number of p such that both p and p+2 is also prime?. PRO: If the layperson knows what primes are then this is easy to explain. PRO: Give examples easily: (3,5), (11,13), (17,19), (21,23). CON: Can't really say why its important. THOUGHT: You can say that primes are important for crypto.
3. Chromatic Number of the Plane How many colors do you need to color the plane so that there are never two points an inch apart that are the same color? PROS: The layperson can probably show that 2 colors is not enough, and perhaps 3. PROS: Can easily show the layperson that 7 colors suffices. CON: Can't really say why its relevant. CON: The notion of a coloring of the plane (or even a piece of paper which is what I would use) is somewhat abstract.
4. n²+1 prime problem Are there an infinite number of primes of the form x²+1. PRO: If the layperson knows what primes are then this is easy to explain. PRO: Give examples easily: 5=4+1, 17=16+1. CON: Can't really say why its important. CON: Not as well known as the others on this list (I could not find it on wikipedia since I didn't have a good keyword. It may be there someplace.) THOUGHT: You can say that primes are important for crypto.
5. 3x+1 problem. Also see this website. Consider the following process. Take any number. If its even half it. If its odd then add 1 and divide by 3. Repeat with your result. Keep on going. Will you will eventually get to 1? PRO: They can do some computations. CON: Can't really say why its relevant.
6. P vs NP. If I phrase it as can you solve the TSP problem without going through all of those possibilities then the laypeople might understands it. I might add that there are many problems with the same flavor. I avoid SAT and I avoid NP. PRO: Practical problems! Relevant! CON: Just the notion of what a problem is might be hard. To most people a problem is easy to solve if there computer can solve it in less than a second.
7. Can we factor quickly?. Similar to P vs NP for the layperson, You can say that factoring is important for crypto.

The One Who Walked Away

I caught a rare sighting of Noam Nisan at the GAMES congress. Many of you young complexity theorists may not have ever met Noam or even cite many of his papers anymore. But his research lies at the heart of most of today's complexity research.

Using hard functions for psuedorandom generators started with Nisan who also had breakthroughs in space-bounded generators. Using Forier transforations in complexity got its start with Linial-Mansour-Nisan. Nisan did fundamental work on Communication Complexity and co-wrote the Book on the topic. Nisan may never had directly worked on quantum computing but the polynomial method for proving quantum lower bounds basically follows from Nisan-Szegedy. Not to mention Nisan was the first to show the surprising power of PCPs that led directly to IP = PSPACE and the PCP/Approximation lower bound revolution.

But around 1997 Noam walked away from computational complexity. Just ten years after Ph.D., he felt he had reached his limits in complexity and could no longer produce strong results (despite the fact that he continued to produce papers others could only dream about). Noam shifted gears focusing on economics. Sure he has had his successes there mostly in auction theory. Still what a loss to complexity to lose him over the past decade. If you ever want to return to your roots Noam, we'd be more than happy to have you back.

GAMES and Computer Science

About 30 computer scientists attended the recent GAMES (Game Theory Congress), a tiny fraction of the participants but a noticeable force including several theory heavyweights from a variety of backgrounds: Joe Halpern (Logic), Silvio Micali (Cryptography), Noam Nisan (Complexity) and Éva Tardos (Algorithms). There we also a few AI researchers shuttling between GAMES and AAAI.

The game theory community has made some efforts to welcome the computer scientists. There is now a Game Theory and Computer Science Prize given to The Complexity of Computing a Nash Equilibrium with a lecture given by Constantinos Daskalakis and co-authored by Paul Goldberg and Christos Papadimitriou (noticeably missing from GAMES). Goldberg also has several posts on his blog about the award and the conference.

The Shapley lecture, given each congress by a researcher under 40, was given this year by computer scientist Tim Roughgarden. Afterwords there was a CS-Game Theory lovefest between Tim and Ehud Kalai, one of the leaders of the game theory community. It doesn't hurt that Ehud's son, Adam, is one of our own.

On Monday the conference had a panel by recent Nobel prize winning game theorists Eric Maskin, Robert Aumann and Roger Myerson on the recent history and future of the field. Mostly the expected preaching to the choir but at the end Aumann did talk about the importance of computer science in games in the areas of crypto, games played on computers, auctions and real-time algorithms. He followed up with a memorable take on the future by singing the chorus of Que Sera Sera.

Sergiu Hart, new president of the Game Theory Society, gave an invited talk on his paper with Yishay Mansour showing exponential lower bounds for convergence to a Nash equilibrium in certain models. A nice result but he unfortunately picked up the CS habit of using "natural" as shorthand for "the set of assumptions needed to prove the main theorem."

Computer science showed up in several other presentations. For example, Iter Sher uses max-flow to analyze persuasion. Nearly every topic in game theory hits on CS issues and many (though not all) game theorists seem welcome to have computer scientists work on their problems. There are still many language, technical and cultural issues to overcome to have true collaborations but I foresee a bright future between our fields. So go talk to a game theorist. They don't bite.

Not CS related by on Wednesday we had lunch-time entertainment presentation by Yoram Bauman, self-proclaimed stand-up economist. He opened the talk with his translation of the 10 Principles of Economics which you can watch yourself in this video.

Topics for theory grad course for non theorists?

(Guest Post by Kirk Pruhs.)

I am taking over teaching our graduate CS theory course. I will be teaching to PhD students who will not become theoreticians. I want to emphasize concepts and broad knowledge, not formal proofs or training students to do formal proofs. The plan for most classes is to get the students to understand the statement of one theorem, and the significance of that theorem, with the remaining time devoted to some intuitive explanation of why the theorem is true. I want the the course to be at least a little bit broader than a standard complexity class. For example, possible topics that are not standard complexity topics:

1. Impossibility of distributed consensus with faults
2. von Neumann minimax theorem
3. no minimum energy for computation

I would like to solicit suggestions as to what theorems and topics one should teach to CS PhD students who will not become theoreticians. I probably will have time to 25 to 30 topics.

An Interesting Summation- NOT new but raises some questions

In my last post I asked for information about the summation &sum_i (-1)ⁱ (k choose i)(a+i)^k (Where the sum goes from i=0 to i=k.)

I knew it was (-1)^kk! but wondered if this was already known and if there was a combinatorial proof. The comments said YES to both questions. (Side Note: THANK YOU READERS. The comments were INTELLIGENT and HELPFUL!.) This raises some questions.

1. The book A=B gives a way to determine for a large class of sums if they are expressible in closed form, and if so what that form is. My sum did not fall into there category since mine has that pesky a in it.
2. Since my summation is solvable with calculus of finite differences is there an algorithm, perhaps an extension of A=B, that will also deal with summations like this. Might be hard to define like this.
3. One of the commenters gave a combinatorial proof but then said that it was better understood using calculus of differences. Doren Zeilberger might agree. In this interesting essay he seems to be saying that once you have a mechanical proof of something (e.g., like those in A=B) then having combinatorial proofs of them that are over a page then such proofs are not that interesting. The combinatorial proof was under a page, but I think Zeilberger was really referring to how complicated things are rather than actual page length. Might be a close call.
4. Dear Anonymous 6 on my last post: When I write a paper that uses this sum I will include your combinatorial proof. I will of course credit you. What name should I use? Anonymous 6 (and point to the website) of course.

An interesting summation- new?

I recently came across the following sum in my research:

&sum_i (-1)ⁱ (k choose i)(a+i)^k (Where the sum goes from i=0 to i=k.)

I had reason to believe that this summed to (-1)^kk! (which is independent of a). A mathmatician from Univ of MD, Brian Hunt, proved it for me and I wrote it up here.

1. Is this result already known? I suspect yes but was unable to find it.
2. I was unable to find a table of known sums on the web. Does anyone know of one?
3. The techniques of the book A=B do not seem to apply. Does some modification of them suffice?
4. Is there a combinatorial proof where you show that both sides solve the same problem? Is there a more elegant proof?

GAMES

Now I am attending GAMES 2008, the third World Congress of the Game Theory Society being held at Northwestern. A real shame that GAMES will prevent me from visiting AAAI also in Chicago.

GAMES has about 800 participants much larger than any theoretical computer science conference I've ever attended (which was STOC 1987 in New York at about 500). Are there that many more game theorists than CS theorists? No, just that GAMES is held only every four years and has massively (up to 14) parallel sessions where most everyone who wants to talk can talk. This gets the whole community together, much like how Mitzenmacher describes ISIT, an information theory conference. The invited plenary and "semi-plenary" (5 parallel sessions) talks at GAMES are reasonably strong invited talks, though the regular sessions are more mixed.

So should we have a TCS Congress held every n years with theory broadly defined and massively parallel sessions to encourage participation to bring our community together at least once in a while? (And no, FCRC doesn't count.) Unless we have a corresponding reduction in emphasis of the other conferences, having one more conference to attend will not likely have the desired effect.

Some NSF notes of interest

Notes from NSF.

1. The core theory soliciation for fiscal 2009 is online.
2. A grant annoucment that may be of interest here.
   
   Deadline: October, November, or December 2008 depending on the size of the project
   
   Estimated number of awards: 36 to 50. (WOW!)
   
   Synopsis: The program will support projects that strengthen the scientific foundations of trustworthiness, in order to inform the creation of new trustworthy technologies. We especially seek new models, logics, algorithms*, and *theories *for analyzing and reasoning about all aspects of trustworthiness-- reliability, security, privacy, and usability about all components and their composition. Building on its predecessor program Cyber Trust, the Trustworthy Computing program will also continue to support projects that explore the fundamentals of cryptography, that examine and strengthen security weaknesses in current algorithms or protocols, and that explore new computing models that promise to improve trustworthiness or our reasoning about it.
3. As Richard Beigel (NSF Theory Director) mentioned at the Complexity Conference, interdisciplinary programs have been noticeably theory-friendly of late. AND Note to PIs: Your proposal title should could enough information so we can figure out which panel your program belongs in.

Electoral Markets Map

Two years ago we created maps to show state-by-state how the 2006 US Senate and Gubernatorial races were shaping up, based on security prices at Tradesports. These markets did very well in predicting the outcomes of those races.

Now in a presidential election year, we have recreated a map, this time for the electoral college and gave it its own URL electoralmarkets.com. This map takes its prices from Intrade, Tradesports current site for their non-sports securities. Once again darker blue indicates a more likely vote for the Democratic candidate (Obama) and darker red more likely for the Republican McCain. Roll over a state for more information or click on that state to go to the Intrade site for that security with historical information.

We created these maps to promote prediction markets as a useful tool for information aggregation. The Third Workshop on Prediction Markets was held at EC yesterday.

As the summer goes on we plan to add several new features so keep checking back and watch the election play out in probabilities in real time.

Attendence at CCC: We have no edge people

This summer the Computational Geometry Conference (SoCG) and the Conference on Computational Complexity (CCC) were both held in College Park Maryland. Hence a direct comparison is possible. Here are some numbers:

1. SoCG drew 140 people. Recent America SoCG confs that were not to FCRC or co-located with anything: 2006-AZ: 125 people, 2004-NY: 180 people.
2. CCC drew 80 people. Recent America CCC confs that were not FCRC or co-located with anything: 2005-San Jose: 67 people, 2004-Amherst: 82 people, 2001-Chicago: 96 people. For more complete data see this post

Some thoughts on these numbers:

1. SoCG has more people then CCC. Why? (1) more people are working in it, and (2) more people on the edge--- people in graphics or vision or Comp Biology or algorithms who, IF SoCG is local then these edge-people might go. CCC doesn't really have this.
2. We do not have edge people. Who should our edge people be? Crypto? Algorithms? Combintorists? Quantum People? Philosophers/Historians/Sociologists of Science? For Crypto and Algorithms there have been some results (though not alot) of interest to them. For Quantum People they should care about Quantum Computing , but do they? Phil/Hist/Soc of science might be interested in seeing a young field where they can still interview some of the founders, but that is not the same as going to the conference. Besides, they probably don't have grant money.
3. I can count about 5 people who often go to CCC who missed CCC08 and 10 more who I think should go (who am I to say they should go?) who didn't. Some of those who missed it had pretty lame reasons (e.g., a daughters wedding). Before trying to outreach to Crypto, Algorithms, Combinatorists, Quantum Physicists, P/H/S of science to go, we should get our own people to go.
4. Are there othere potential edge-people I have overlooked?

Busy Conference Week

I don't travel far for my next conference, the ACM Electronic Commerce conference being held in downtown Chicago. Tutorial and workshop sessions start today.

The conference is not about using credit cards on the internet, but rather a slew of topics connecting computer science and economics, lots of auctions and networks for instance. I am general chair this year, a bit more challenging than the six years I spent in the same position at the Complexity conference because of having to integrate the different cultures of CS theory, AI and economics.

But EC is not the only game going on right now. ICALP, the major European theory conference is happening as we speak in Iceland while in Finland we have COLT, the learning theory coference starting Thursday. The sun won't set on ICALP or COLT this year.

Let's not also forget the IEEE International Symposium on Information Theory in Toronto so nicely described by Mitzenmacher.

Unfortunately conflicts like these require difficult choices. I (and many others) have attended and had papers in ICALP, COLT and EC in the past. Why do we have these conflicts? These conferences need to be planned out years in advance with a number of various date constraints making coordination very difficult and early to mid July makes for good conference dates as a post-classes, pre-vacation time in many countries. As CS expands and adds more conferences to cover the increasing number of papers we produce, this problem will only get worse in the future.

Attendence at CCC I: History

(This is the first of two postings about Attendencd at CCC. Todays is about history. Next time I post (probably Wedensday) I'll talk about College Park and modern times.) Here is attendence for all years of CCC.

Where	Year	Attendence	Comment
Berkeley	1986	110	co-locate with STOC
Cornell	1987	100	co-locate with LICS
Wash, DC	1988	89
Oregon	1989	63
Barcelona	1990	108	Europe
Chicago	1991	100
Boston	1992	100
San Diego	1993	123	FCRC
Amsterdam	1994	110	Europe
Minnesota	1995	80
Philadelphia	1996	90	FCRC
Ulm	1997	80	Europe
Buffalo	1998	84
Atlanta	1999	84	FCRC
Florence	2000	66	Europe
Chicago	2001	96
Montreal	2002	140	Co-located with STOC
Aarhus	2003	78	Europe
Amherst	2004	82
San Jose	2005	67
Prague	2006	75	Europe
San Diego	2007	85	FCRC
College Park	2008	81

1. As part of FCRC: 123, 90, 84, 85. So lately this has not been a real boon, but not a loss either.
2. Co-locate with STOC, non-FCRC: 110, 140.
3. Co-locate with LICS. 100.
4. Europe Attendence: 108, 110, 80, 66, 78, 75. I suspect that Florence drew so badly because there are no complexity theorists in Italy (at least not since Luca was in High School.)
5. American non-co-locate, non-FCRC: 89, 63, 100, 100, 80, 84, 96, 82, 67, 81. Note that the two in the 60's were on the West Coast. Chicago did very well: it was there twice and we got 96 and 100. Boston is the other 100. 100 is a suspiciouly round number- I suspect they only had 99.
6. Lessons Learned: Good to co-locate with stoc, and good to have it in a place that has a strong complextiy community. We might have very high attendence in Boston co-locating with STOC in 2010. Mitigating factor: the price of gas.

The Great Procrastinators

A chemist earlier this week called computer scientists famous procrastinators with our uncanny ability to put off to tomorrow what we could have done today. I'd feel insulted except that he's absolutely right. For those who disagree, aren't you supposed to be working on your SODA papers now?

Why is procrastination seemingly part of our culture? Much has to come from our deadline-driven conference and grant system. If deadlines motivate us highly then not having a specific deadline for a task (say writing or refereeing a journal paper) tends to push that task down to later when we'd rather be doing something else like research.

Sometimes people take it to the extreme: One time someone decided to skip a workshop months in the future because a STOC deadline was at the end of the same week. I convinced that person to sign up for the workshop by tricking them into thinking the deadline was one week earlier. Maybe I lied but wasn't everyone better off for it?

And then, of course, as computer scientists we are always on a computer with access to the web, the great distractor. It's just too easy to catch some videos, catching the latest political news, reading and writing email and blogs…OK, back to work for me.

Enjoy the 4th everyone and we'll be back on Monday.

A NEW Blog in Town-kdphd

(***SORELLE*** requested and approved this message, though I wrote it.)

There is a new theory blogger on the scene and as you read that sentence you may be wondering `oh, who is he?' That would be the wrong question.

Check out kdphd.blogspot.com a new blog by a ***SORELLE*** a female theorist. Her first blog is a short intro to herself. The second one is about a women-in-computing workshop she went to.

What will ***SORELLE*** blog about in the future? She says it will be women's issues (a term she doesn't like- perhaps she'll blog about what to replace it with), computer science, grad school, politics, the politics of computer science grad school, and whatever else comes up. She is multi-dimensional and so I assume her blog will be too.

She is a Comp Geometry student from The University of Maryland. I am happy to say I have had no influence on her whatsoever. She is her own women.

Why is her name ***SORELLE*** ? Because I was once asking people what their stage names would be if they had one. Sorelle is one of those people like MADONNA and CHER and others celebs that have one word names. Hence she will always be ***SORELLE*** to me. Actually, I don't know her last name.

A pointer to her blog can now be found on our blog under `Sorelle'. (Lance is not big on asterisks and capital letters.)

NSF and CACM

I received two "Dear Colleague" letters over the weekend. Jennette Wing, current head of the Computer & Information Science & Engineering directorate at NSF, describes the restructuring of CISE including a new Algorithmic Foundations program, of interest to many readers of this blog. Many program solicitations have already been posted with deadlines much earlier than in previous years.

Moshe Vardi tells us that we all ought to join the ACM, partly to help support the main computer science society, but also because now you will receive the new redesigned Communications of the ACM under Vardi's editorialship.

ACM serves two very different communities, academic computer scientists and practicing computer professionals. The flagship magazine, CACM, has to cater to both groups to succeed. The old CACM mostly had articles around some common topic written by academics, aimed at practitioners and not fitting the needs of either group.

So how is the new CACM? The first redesigned issue (July) just came out and is available online. It hasn't reached the full vision but does give a taste with some opinionated pieces on topics from XML to quantum computing. It also has interviews with Donald Knuth and the Turing award winners.

Definitely an improvement but I didn't find any articles that truly excited me. If CACM hopes to become the "first magazine I want to read each month," it will have to take more risks, producing articles that give new perspectives to up and coming topics in computer science and lead the field instead of just reporting on it.

The Special Issue Debate

A commenter requested a written post on the special issue debate (our podcast already has it but he or she and others may have a hard time accessing our words of ... wisdom(?)). Here are all the opinions that I heard at the meeting and later. I do not attribute them since we are not yet at the point where making a good point at a meeting is something to put on your resume.

1. Background: The special issue for CCC (and most theory conferences) had been JCSS (Journal of Computer and Systems Sciences) for many years. When prices began going up many theory conferences switched to non-commercial publishers, some affiliated with societies like SICOMP. CCC went from JCSS to CC (Computational Complexity) which is owned by Springer, a commercial publisher. Laci Babai has been running Theory of Computing: An Open Access Journal and he wants us to switch to his journal or to have some kind of rotating system. von zur Gathen who is the editor of CC wants us to stay at CC. The steering committee wants to DECIDE and STAY with someone for the next 5 years so we don't have to keep having this debate.
2. The goals of a commercial publishers are at odds with the goals of the community. We want our work out there and available. In particular we want out work to be available free online or at a cheap price on line. They want to make money. Therefore we should switch to a non-commercial publisher, as many other theory conferences already have.
3. The distinction between commercial and non-commercial is silly. There are some non-commercial publishers that are not very good (IEEE was brought up). Nobody seemed to be able to bring up the other kind of counter example- a commercial publisher that was very good. von zur Gathen says that CC is reasonably priced but he admits that Springer does overprice other journals.
4. CC is not free online. However, if we go with them they will put the special issue free on line after a year. And they will (as they did this year) provide us with free copies of the journal at CCC. Should we threaten every year to get more and more out of them? One participant told von zur Gathen directly: You make the entire journal free online 6 months after it appears and I will vote for CC.
5. There is something about paper that feels more permenent then just being online. Formats change but paper lasts forever. Then again, Google Caching also lasts forever.
6. Does Theory of Computing: An Open Access Journal have sound financial backing? Laci claims that even if Univ of Chicago blew up tommorow the journal would keep going. However, the journal has not set up the proper paperwork to accept donations.
7. Will Springer raise the price of CC? So far they have not and they regard it as a prestige journal so they are willing to break even. Will this last forever? But even in its current state, there are schools that do not have access to it, while all people have access to TOC:AOAJ.
8. ACM has a new journal Transactions on Computation Theory. This would seem to be a good place to have the special issue. Non -commercial, sound business model, ACM support. But it has not produced a single issue yet. The editor, Lance Fortnow, said he is not seeking the special issue. Since this is an election year it is not clear what that means.
9. The Special Issue of CCC is 1/4 of CC's issues. We are making them prestigous, not vice versa.
10. Rotating seems complicated; however, if we can just have on the CCC website to click here or there to get that years special issue, that could be okay.
11. When the editors raise prices we don't like it. But when the lower them or agree to put things online, thats a bribe. They can't win. Well- if they just put EVERYTHING online and cheap then we will stop complaining and threatening. If they can't find a way to do that and make a profit they should not be in the business.
12. There should be a special issue to honor the good papers and also (and this is a topic for another day) make sure that conf papers get into journals- our field has been bad about that.
13. At the meeting there was a ranked vote: You could vote CC, TOC:AOAJ, write in (likely Transactions), or to rotate. If you voted rotate then you had to say which journals. (E.g., Every year that is a Fiboacci Prime, we got to CC, Fib non-prime TOC:AOAJ, all else: TRANS.) The results of the vote will be posted online.
14. Laci gave his presentation on overheads.

Complexity Conference Wrap

In the second half of our podcast (22:34, 20.6 MB), Bill and I talk about the debate over special issues at the business meeting between Joachim van zur Gathen, editor-in-chief of Computational Complexity (a Springer journal that serves as the current home of the conference's special issue) and László Babai, editor-in-chief of Theory of Computing (an open-access electronic journal). Watch this space for the results of the vote taken after the debate.

Bill and I also talk about Richard Beigel's report on the not-too-bad state of theory funding. An important warning: Regular theory proposals will have a fall deadine, well before the deadlines over the previous few years.

Evan Golub set up a Flickr group for pictures from the conference and uploaded some he took from the business meeting. Feel free to upload your own pictures from the conference.

I really enjoyed the conference for several reasons. For the first time since 1995 I didn't attend the conference steering committee dinner or have any other major responsibilities. I did serve on the PC and hosted the first session, but pretty much I could just relax and enjoy this meeting. Also for the first time since Amherst in 2004 we had the conference by ourselves on an American college campus allowing a very relaxed atmosphere. I really had a chance to talk over some neat research problems and catch up with old friends including a very large presence of former Chicago students. No new theorems for me this week but plenty of neat problems to think about.

Now I go home, switch hats, and get ready for the upcoming Electronic Commerce Conference in Chicago.

See you all at next year's Complexity Conference in Paris!

On being local on the local org comm.

Comments on being on the local arrangements committee for CCC 2008.

1. The local arrangements comm. was a joint effort with Richard Chang and Marius Zimand. Always good to have people checking each other.
2. Lisa and Allison from the Conference and Visitor Services did alot of the nitty-gritty work like reserving rooms, buses, setting up websites, and being around. They have my sincerest thanks. The two student volunteers, Martin and Nicholas, were also helpful.
3. Pierre McKenzie (Steering Committee Chair) and Paul Beame (Program committee chair) made alot of the decisions. This was Great!.
4. Before, during, and after the conference I kept wondering is there something I should be doing?. The wondering was tiring, so if I fell asleep during your talk, thats why.
5. There were many decisions that had to be made. Where on campus to have it? What layout should the room have? Bagels at Breakfast? What should go in the tote bag? What should be the logo on the tote bag? On the name badges? What hotels to use? What time should the shuttle bus be? What time should the business meeting be? Some were important. Some were not. but it drove me nuts and it never seemed to end.
6. The hardest thing was making up the budget. It has to be based on how many people we think will come. Past attendence is some guide, but hard to say how good. (We got 81 which was good.)
7. I got to go to the steering committee meeting this year and last year. I saw the corridors of powers! Alot of thoughtful (i.e. long) discussions on alot of issues- major and minor.
8. Instead of saying `Sasha, congrads for winning the best student award!' I said `Sasha, make sure you fill out the forms to get your money!' Being local arrangements people changes your viewpoint.
9. I am happy nothing went wrong. Before the conference I thought What if we have a loss? What if we have a profit? What if I go to jail--doing a nickel for being falsely accused of ripping of a conference..., Will the room be good?, Will the dorms be good? Will the hotels be good? and of course Will there be enough bagels?.
10. Pierre, Paul, Lisa--Is there something I should be doing?

Podcasting from the Conference

Bill and I revived the Complexitycast by talking about the Complexity Conference. The discussion ran long so we will post the podcasts in parts. In Part I (18:33, 16.9MB) we talk about the award winning papers:

• Ronald V. Book Best Student Paper Award: Alexander Sherstov for Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions
• Best Paper co-Winner: Ran Raz and Amir Yehudayoff for Lower Bounds and Separations for Constant Depth Multilinear Circuits
• Best Paper co-Winner: Emanuele Viola for The Sum of d Small-Bias Generators Fools Polynomials of Degree d

and the beginning of the business meeting including future Complexity Conferences in Paris (July 7-10, 2009) and Cambridge, Massachusetts co-located with STOC in 2010.

FOCS Accepts

Accepted FOCS papers posted.

Seven Dirty Words

In memory of the great George Carlin, we present the seven dirty words you cannot say at the Complexity Conference.

1. Constants
2. Algorithm
3. Application
4. Heuristic
5. Competitive
6. Implementation
7. Wolfram

ACM Awards Banquet

With the kids at camp, after Iron Man, my wife and I hopped a plane to San Francisco. Did some wine tasting, saw some opera, played tourist (even riding the cable cars) all leading up to the ACM Awards Banquet on Saturday night.

While the ACM sponsors many conferences, there is no annual conference that covers our whole field. In non-FCRC years, they hold their awards ceremony at a nice hotel in San Francisco attended mostly by ACM officers and award winners. I was there as a new ACM Fellow to receive a certificate and the Fellow pin and have a rare chance to wear a tuxedo to a computer science event.

The highlight of the evening was, of course, the Turing award. The consulate general of France read a letter from the Ambassador congratulating Joseph Sifakis, the first French winner of the award. No such messages from the US for the two American co-winners, Edmund Clarke and Allen Emerson. But actually Daphne Koller netted the most prize money as the sole winner of the ACM-Infosys Foundation Award.

Many theorists among the award winners including Shafi Goldwasser as the Athena Lecturer (the lecture itself to be given at FOCS or STOC), Sergey Yekhanin (not present) winning the doctoral dissertation award and several other theory fellows. I also liked seeing the young people, including the ACM Programming Competition winners from St. Petersburg (Russia) and David Christopher Williams-King of Edmonton, the high school winner of the CS division of the Intel International Science and Engineering Fairl. Another highlight: David Harel describing how he co-won the Software System Award without writing a line of code.

This morning I hopped a plane across the country just in time to catch the end of the reception for the Computational Complexity Conference at the University of Maryland. On the plane I read the first redesigned CACM under Moshe Vardi's direction passed out at the banquet. More on the the Complexity Conference and the new CACM coming soon.

Karp Wins Kyoto Prize!

Fast breaking news: Karp wins the Kyoto Prize! See here

1. Certainly deserved!
2. Lets all congraduate him (hmmm- this may clog up his email.)
3. Lets hope this gives some attention to computer science theory.
4. Quoting from here about the philosophy of the prize it says Those worthy of the Kyoto will be people who have,as we at Kyocera, worked humbly and devotedly, sparing no effort to seek perfection in their chosen professions. Interesting- seems like you need to be a nice person as well as a brilliant scientist. As such, again, Karp deserves it.
5. Its worth 50 million yen. 1 yen is 0.00942 dollars. So this is 471,000 dollars.

See you at CCC 2008!

Can still register for CCC08: Register here.

1. BILL: Lance, maybe we should have an Anonymous Guest Blogger for CCC 2008 since I am one of the local organizers (along with Richard Chang and Maruis Zimand), hence anything I write might be biased, and we want someone who is free to complain about not having enough Bagels.
   
   LANCE: I can be a non-anoymous non-guest blogger. I have no problem complaining that there are not enough Bagels.
2. After the conference is over I will blog about it from the point of view of one of the local organizers.
3. HOPE TO SEE YOU THERE! If you don't know what I look like see this picture

Guest Post on App of Ramsey to Constraint Satisfaction

(Complexity Conference next week! Register Here)

(Guest Post by Manuel Bodirsky on a paper of his that applies Ramsey Theory.)

In a recent paper we apply the so-called product Ramsey theorem to classify the computational complexity of a large class of constraint satisfaction problems.

A *temporal constraint language* is a relational structure &Gamma with a first-order definition in (Q,<), the linear order of the rational numbers. The problem CSP(&Gamma) is the following computational problem. Input: A *primitive positive* first-order sentence, that is, a first-order sentence that is built from existential quantifiers and conjunction, but without universal quantification, disjunction, and negation. Question: Is the given sentence true in &Gamma?

In our paper we show that such a problem is NP-complete unless &Gamma is from one out of nice classes where the problem can be solved in polynomial time.

The statement of the product Ramsey theorem that we use is as follows: for all positive integers d, r, m, and k > m, there is a positive integer R such that for all sets S₁,...,S_d of size at least R and an arbitrary coloring of the [m]^d subgrids of S₁ × ... × S_d with r colors, there exists a [k]^d subgrid of S₁ × ... × S_d such that all [m]^d subgrids of the [k]^d subgrid have the same color. (A [k]^d-subgrid of S₁ × ... × S_d is a subset of S₁ × ... × S_d of the form S_1' × ... × S_d', where S_i' is a k-element subset of S_i.)

In my day...

Can still register for CCC08: Register here.

(A reader emailed me the website and asked me to Blog on it.)

According to this, Math Exams in England have gotten much easier since 1951. The article also points to the exams the exams themselves so you can judge for yourself.

The later exams look easier to me but not that much easier as to be a concern. The earlier ones had proofs, but the later ones had some concepts not on the earlier ones.
1. Every generation tends to think that life has gotten easier since they were a kid.
   1. When I was a kid I we had to go to the library and copy articles! We didn't have your fancy websites and printers. And to get to the library we had to walk 5 miles in the snow, uphill, both ways. And we wore cardboard boxes on our feet for shoes.
   2. You had cardboard boxes!
   3. You had feet!
2. Also, each generation thinks that the way they did things is the way things should be done Young people today don't learn how to use a Slide Rule. Wimps!
3. But never mind what I think. What do you think?

I am Iron Man

Yesterday we dropped the kids off at camp and celebrated our first night of freedom by seeing a movie that does not involve a panda mastering martial arts. In my comic-book reading days of the mid-80's, my favorite hero was Iron Man and I had the chance to catch the movie before it leaves the theaters. Some mild spoilers ahead.

Why Iron Man? He didn't have power thrust upon him like Spiderman or come from a dark background like Batman. Rather Tony Stark was the ultimate engineer. He developed Iron Man out of necessity and and then out of obsession keeps tinkering with the suit, upgrading and adding new features. Happily the movie left off the roller skates from the early years of the comic books.

Stark has his faults. In the comics, back in the 80's, he spent several issues overcoming an alcohol addiction (while he friend Jim Rhodes donned the suit). But in issue #200, he put himself back in the suit to fight to the end the villain Obadiah Stane in his own suit as Iron Monger.

The movie doesn't follow the alcholism theme but does have Stark as a weapons manufacturer, a womanizer and a huge ego. The battle at the end is still quite familiar.

When I gave up comics in grad school, Iron Man was the hardest to drop. In the movie Stark spends more time building the suit than using it. That's the way a super hero should be.

Posting a SUBMITTED paper

(Can still register for COMPLEXITY 2008 at here.)

In a comment on my post SODA 2009 CFP that Shiva Kintali pointed out that SODA is encouraging authors who submit to post their submissions on their own websites. He is correct that they are encouraging it, see here, but is he correct that it is an excellent idea? This raises a few questions.

1. You are on the SODA committee. You read a paper that is very good and that you can build on. You make sure it gets rejected from SODA and then write your own paper that is similar. Obviously unethical. But since her paper is on line early she can easily prove that she obtained the results first. Does just having a paper on your website count? I would say yes, and this would be a good reason to post. However, I doubt this scenario is common.
2. You are on the SODA committee. You read a paper that you can build on. You really want to get a legit copy of it so you can start working, fully intending to credit previous work. You go to the authors website. Its not there! Perhaps you are motivated to get it INTO SODA so that you can use it and reference it. This might be a good reason for the author to NOT post to give them an edge. However, I doubt this scenario is common.
3. If you are on a program committee or a subreferee or refereeing a grant then you are morally obligated to not steal any work that you see in that capacity. You are also not even allowed to build on the work. But are you allowed to look at the authors website to find the work so you can then build on it (and properly credit it)? I would think so. What if the author does not want you to to this. Then she would not put the paper on her website. But now SODA is urging her to do so. Is this appropriate on the part of SODA? Shouldn't the author have the choice of perhaps not going public yet because she wants to work on the problem some more? Of course, at this point its is just urging to post on your website not mandatory. But will this urging turn into mandatory at some point?

Working Outside Our Fields

An economist told me recently how he is often impressed when other economists give talks using tools and working on problems in other academic areas. "They really seem to get it," he said.

After hearing this I first thought about similar experiences I have had when I see computer scientists talk about ideas in physics, biology and economics that they seem to have really learned about the other field and tied the areas together well.

My next thoughts went in a different direction. When I have seen economists talk about computational models and complexity, my bread and butter, I just want to tear my hair out (or more accurately tear their hair out). How they get so excited about some stuff we consider completely obvious or known several decades ago, or worse using the completely wrong computational model for the problem they look at, for example examining the precise number of states of a finite automata when they shouldn't be using automata at all.

On the other hand I have heard many economists and physicists and biologists complain that (with some exceptions) they don't understand the relevance of much of the interdisciplinary research that comes from our community.

Part of this attitude comes from the general arrogance that you find among all academics. We computer scientists feel we know the right way to think about problems in all academic fields and researchers in other fields feel the same.

We give strong weight to interdisciplinary research, a good thing. unforunately we typically do this research in the context of impressing those in our own field with a system that encourages this behavior. It is our peers, other computer scientists, that will hire us, write us recommendation and tenure letters and review our grant proposals. So we find it more valuable to have STOC and FOCS paper than papers in good economics or biology journals that most CS people have barely heard about. And we give these talks mostly to our peers designed to impress them.

True interdiscplinary research is difficult enough because you have to deal with not just another field's language but also their culture about what kinds of problems one finds important. But we need a system that truly rewards those who can truly bring computer science ideas into other fields above those who just try to impress our own.

Complexity Zoo Poster

There is a poster of (some of) the Complexity Zoo that was emailed to me by Ken Regan. It is on line either as a pdf file or a ppt version. (There was an earlier version a while back.)

1. Would this poster make a good syllabus for a basic course in complexity?
2. I prefer it NOT as a poster but as an image on line that I can zoom in and zoom out of.
3. Is there any important complexity class that is not on the poster that should be?
4. Is there any unimportant complexity class that is on the poster that should not be?

Impressions of C++

I have just finished teaching "Programming for Engineers" at Northwestern, my first time teaching a course on the C++ programming language and pushing me to learn the the many fine points of the language. Yes, I know this is a theory blog but I'm giving you my impressions of the language anyway.

C++ was a language written for its time, the 80's, when computers were slow, memory was expensive and machines, for the most part, didn't talk to each other that much. The language, an object oriented upgrade to C, allowed one to write code just above the assembly language code. It kept memory limited to the point of not storing the sizes of arrays and allowed users to have pointers directly to memory. It is a language that, with objects, lets you create whatever you want and overload operators, allowing you to redefine "+" or "=" to do whatever you want. It is also a powerful language, allowing you to build classes based on other classes and, with the Standard Template Library, gives you access to a set of highly optimized data structures.

C++ does create incredibly fast code especially when run on today's processors. On my laptop, looping through a trillion operations takes only a couple of seconds. Because of the popularity of C++, there are C++ compilers for every platform, many of which produced incredibly optimized code. And of course there is a wealth of information and code libraries written in C++.

That's the good. Now the bad: C++ is a complicated language—I spent most of the ten week course teaching syntax and still didn't cover close to the entire language. C++ allows obviously bad statements, for example if you replace the "==" in " if (a == b) d++; " with a single "=" then it still compiles and runs but doesn't do what you wanted. The expression "3^5" outputs 6 and not 243. To make a class abstract you don't say "abstract" but just make sure you have at least one pure virtual function. To make a virtual function pure you add "=0" at the end of its header definition. There is something very mystical about purifying something by setting it equal to nothing.

But those are minor complaints. We don't live in the 80's anymore but in the Internet age which causes two major problems: compatibility and security. C++ has not standard way to access Internet objects like XML. In class I showed how Microsoft's XMLTextReader worked but it is tricky to set up and doesn't port to other systems. Too bad as a computer that doesn't access the Net hardly seems like a computer anymore.

Even worse, C++ is a very trusting language, not having many safety checks and allowing direct access to low-level operations and memory. The Internet is full of non-trusting people. One can write safe code in C++, say that doesn't allow buffer overruns, but it is tricky and a programmer even a little lazy can leave a gaping hole for hackers to climb through.

Legacy code will keep C++ programmers employed for many years, especially as we close in to 2038 and we hit the time limit. But a programmer starting a new project today would do better in a safer language. Python anyone?

SODA 2009 Call for Papers- and a comment on it

(Claire Mathieu requested that we post this.)

The web site for submitting papers to SODA 2009 is up and running. Please see the "Submissions" button in the right-hand side menu of the page at SIAM.

A few important differences from previous years:

1. There is a pre-submission deadline of June 26, one week before the final submission deadline of July 3. By June 26, authors must have entered a title and short abstract of the paper which they intend to submit. (One goal of this is to speedup the assignment of submissions to program committee members.)
2. The submission must contain complete proofs. (Part of the proofs can be relegated to the appendix if they do not fit in the requisite number of pages.)

BILL'S COMMENT ON THE POST: I wonder why they require complete proofs. Did some big result fall apart recently? Is this a good idea? Will it cut down submissions? Drastically? Will the proofs be badly written? very badly written? ignored? Why is SODA doing this and no other major theory conference has required this? Will I refuse to submit my proof that P=NP because of these requirements?

Journals and Information Obsolescence

Eldar Fischer pointed me to the following question asked on Slashdot.

With the ability to get information anywhere in the world in seconds, and the virtually immediate obsolescence of any printed work, why are journals such an important part of academic research? Many of these journals take two or more years to print an article after it has been submitted, and the information is very difficult (or expensive) to obtain. Does this hinder technological advancement? There are certainly other venues for peer review, so why journals? What do they offer our society? Are they just a way to evaluate the productivity of professors?

In our Internet world, the stuff we take in on news sites, blogs, podcasts, youtube, instant messages and social networks are all quite instantaneous. That's the great power of the Internet to get information out there to everyone right away. But does this flood of constantly changing information alter our perceptions, make us believe that anything written yesterday has no value and of the "virtually immediate obsolescence of any printed work?"

Academic research works differently. We don't (or shouldn't) focus on the here and now. A theorem I prove today will still be true 50 years from now and in fact was true 50 years ago. The same holds for other fields from our understanding of the universe to our interpretations of Chaucer. The importance of a particular result can vary in time as some specific questions seem important now and for various reasons, good or bad, not important tomorrow. But the theorems remain true forever.

If anything, especially in computer science, we get judged too much for our short term research and not as much for the stuff we do that stands the test of time.

So why journals? To do it right. To write up your work without the immediate need to announce your results or make a conference deadline. To have your work properly vetted, archived, and written in a way that future researchers can understand your work and build upon it.

These days we seem to live in a world where everything two days ago seems not to matter anymore and what we do today will be forgotten two days from now. But good science creates a tower of knowledge where today's blocks rest on what lies below and journal articles tell us how that tower was built so we can better build it higher.

email: not as useful as it could be

(Can still register for COMPLEXITY 2008: here)

Email stories:

1. Recently a co-author and I both thought that the other one was not responding to emails. We were both annoyed at each other. But it wasn't true! Why did it happen? A combination of both being busy (so maybe it was a bit true), spam filters, and even a few cases where the email really did not get through and was not spam filtered. We figured out what was going on, stopped being annoyed at each other, and made progress on the paper. But I can imagine this sort of thing being more serious and causing a mob war based on a perceived lack of respect.
2. From experience I've leared that emailing ugrads for an event is not enough, even if there is free food. You need to use posters (old school!) and have teachers announce it in class. Why? They get too much email and some put off reading it (or at least reading mine) until after the event is over.
3. I had a Monday 11:00AM meeting scheduled and the person I was going to meet emailed me the prior night at Sunday 11:00PM saying he had to cancel. But email was slow for some reason (nobody knows why) and it got to me at Monday 4:00PM. No big deal, but my annoyance at him was unwarranted.
4. I read an article in a magazine and thought that some other people would be interested in it, so I copied it (with a copy machine). I later found that it was on line. I conducted an experiment: I put it in 4 peoples physical mailbox, and emailed it to 4 other people. Those who got it in their physical mailboxes read it, those who I emailed a pointer did not.

A combination of email NOT working sometimes and of having TOO MUCH email to get through it all, is making it a less useful medium. The ``too much email'' is not about spammers--- there is lots of email that is not spam but you still don't need it. And its getting worse becaue of the following cycle:

1. People don't pay attention to email since they get too much.
2. Hence they need to be send reminders
3. Hence they get more email.
4. People don't pay attention to email since they get too much.

Is this really a problem? If so, what to do about it? Charging people for emailing might help the spam problem, but again, this is NOT the problem I'm talking about.

Nerds

The Chicago Tribune wrote a feature on "nerds" in Tuesday's paper.

Nerds are perceived as authentic because they're unable to follow trends. Authenticity is always in–or a gesture toward authenticity is always in. Nerds are perceived as people who just have to pursue what they're interested in and ignore what's supposed to be cool.

Yeah "authentic," that's what I was in high school. Don't miss the photo gallery of fictional nerds. They forgot to mention the classic movie Revenge of the Nerds.

Fun fact: A nerd first appeared as one of the strange animals in the Dr. Seuss book If I Ran the Zoo. The expression was popularized by the Fonz on Happy Days, a popular TV show when I was growing up. Certainly I exemplfied nerddom in my high school (captain of the chess team, president of the computer club, ugly glasses and socially awkward). I grew out of it a bit, but anyone who writes (or bothers to read) this blog must have some nerdiness left within them.

Is being a nerd cool now? TV shows about nerds—Numb3rs, Chuck, Big Bang Theory, CSI—all got renewed. We have famous nerds like Steve Jobs and Bill Gates. But once nerds are cool, they are nerds no longer.

High Level Monographs- why?

I recently got two checks in the mail: (1) $500.00 honorarium for a talk I gave at a University (more than I thought it would be), and (2) $11.00 for book royalties for Bounded Queries in Recursion Theory. Perhaps I should talk more more and write less. I talk much faster than I write, so I could really rake it in.

Why do we write high level monographs that very few people will buy? Should we?

1. We are delusional. We think that a book will sell and make us real money. (I never thought this for my book.)
2. We want to get a certain body of knowledge out there. (Yes for my book, though I later wrote a survey gems.pdf, gems.ps. that did a much better job. This is partially because AFTER co-writing the book (co-author Georgia Martin) I knew what I wanted to say.
3. We want an excuse to learn a field. (Yes for my book, and even more so for a book I am working on on van der Warden stuff. See later in this post.)
4. We write books to help us get promotions. In terms of time spend, papers are much better for Tenure. For Full Prof books may be okay. (This is not why I wrote my book, though I think it helped my Full Prof case.)
5. We are intrigued by the mathematics that dicates that the book cost $80.00 for you to buy, and for each copy my co-author and I split $5.00.
6. We like the fact that if there is a mistake it's hard to correct, and once a new result is discovered its hard to insert.

Why do we go through a publisher? Note that our goals and a publishes are different. If I found out that there were illegal copies of my book in China I would be delighted!. And surprised. My publisher would not be delighted, though they may be surprised. My goal is to get the information out there. I do not care about the money (this is not altruistic--- we are talking about $11.00). Also, we can update much more easily if all is online. So why do we use publishers? They lend a certain credibility that chairman, deans, and even our colleagues recognize and respect. We need a way to certify that book is valid in some form without going through a publisher. If someone knows of such a way already in progress, please post a comment. This would be a boon to the community and should not be that hard. At least, it seems easier than the Journal problem.

Having said all this, there are two advantages to having a publisher

1. If people refer to a particular theorem or page in the book, its bad if the book keeps changing. I don't take this seriously since the book won't change THAT much and this should not be much of a problem. Of course, you don't quite need a publisher for this, you just need discipline to not change stuff.
2. The books may never get finished. I have 160 or so pages of a book on VDW stuff (co-authored with brilliant undegraduate Andy Parrish) that is on my website. (I am not supplying a pointer- I want to polish it some more before advertising it.) I was planning on getting it into a reasonable state and then blogging about it. But I keep wanting to add more. And its never quite finished. And I don't have a publisher telling me ``The draft is due on Nov 1, 2007'' . If I did then I would be forced to find a reasonable stop point.

Outside In

After Bill's post yesterday I tried watching the I Will Derive video again and just had to turn it off after 30 seconds.

So for the rest of us, here is a video showing how to turn a sphere inside out, first proved by Steve Smale fifty years ago. Not funny but much more interesting. Just make sure you leave yourself twenty minutes before you watch.

Thanks to Prahladh Harsha for the pointer.

I will derive!

BILL: Lance, I have to do a post on the Math Novelty Song I will derive and need you to tell me how to embed a You-Tube Video into a post.

LANCE: I'll gladly tell you (HE DOES) but why do you have to post about it? I've seen it. Its awful!

BILL: Well, clearly I like these sort of things more than you. I've already gotten several emails about the song and if I don't post on it I'll get more.

LANCE: Well, what do you think of it?

BILL: The Lyrics are good but repetitive. I can't tell if the dancing is so bad that its good or just plain bad. Had this come out 30 years ago I would have liked it more, but there is so much better math novelty out there now then there was then, as you can see from this post, this post, and this post and (added in response to comment) this. But our readers can decide for themselves: