Guest Post on Robin Milner who passed away recently

Robin Milner died on March 20, 2010. For obits see here and here. A review of his most recent book will be in a future SIGACT NEWS book review column; however, you can read it here.

This is a guest post by Rance Cleaveland about Robin Milner.

A REMEMBRANCE OF ROBIN MILNER by Rance Cleveland.

Robin Milner died March 20, 2010 of a heart attack at age 76. He made numerous contributions in the areas of automated reasoning, programming languages, software verification and concurrency theory and was awarded the Turing Award in 1991. (British readers will also note his election as Fellow of the Royal Society in 1988.) His contributions to the development of the Logic of Computable Functions, the programming language ML, the Calculus of Communicating Systems (CCS) and the pi-calculus are justly revered and amply documented in the many obituaries that populate the media.



I want instead to offer a recollection of my own about Robin, whom I first met in 1987 while I was visiting Edinburgh, where he was at the time a professor. I had just finished my PhD and had arrived in the UK for a two-year postdoc at the University of Sussex, where I was to work on a joint project (the Concurrency Workbench project) involving that university and Edinburgh. I was not quite 26, very green, unpublished at the time, and star-struck at meeting people like Matthew Hennessy (my supervisor at Sussex) and Colin Stirling (another project member at Edinburgh), whose papers I had read during my studies. I could not fathom meeting an Olympian like Robin Milner, and indeed during the initial days meeting at Edinburgh I kept my mouth shut and tried not to succumb to a sense of surreal disconnect.

The meetings came to a close, and the question arose as to where I was to stay that evening. A PhD student at Edinburgh had been drafted to host me, but when Robin heard this, he instead offered accommodation at his house. More comfortable, you can have your own room he said.

Oh dear.

Of course I accepted his offer, even as the rising thunder in my ears presaged the possibility of a nervous collapse, and we went to his house after a group meal at a restaurant.

Would you like some vodka? he inquired, explaining that a visiting Russian mathematician (recall the Cold War was still ongoing, and meeting a Russian, never mind hosting one in your house, was impossibly exotic to me) had brought it to him a few weeks previously.

Well, yes, I would, thank you very much.

So out came the bottle, and we spent the next two hours talking about process algebra, bisimulations, logical characterizations of system equivalence, you name it. And I began to relax, and enjoy the conversation, because Robin was listening intently, and responding intelligently and respectfully, and offering up intuitions and insights that made concepts I had struggled to understand on my own instantly clear, and even inevitable. And I realized that I could not only follow, but contribute.

The next morning Robin and his wife Lucy made me breakfast, and he and I returned to the university for more meetings, with me leaving that afternoon to return to Sussex. That whole day, though, I remember feeling light as a feather, willing to wheel and dart and engage intellectually with other team members like I had not just the day before. In retrospect, I think I can say I became a scientist that night, sharing a glass of vodka with Robin Milner.

I saw Robin from time to time over the years, every few months during the course of the project, less so as the years passed and my career took its own path. I still can recall with almost crystalline clarity, though, that night, where a great scientist showed a young acolyte one of the greatest kindnesses of all: taking him seriously.

Rest in peace, Robin.

The Base of Computational Complexity

In the April CACM, George V. Neville-Neil wrote a column on a question about the foundations of computer science:

In most areas of science there are a few basic underlying laws that inform the rest of the study of a given subject. Physics, chemistry, and electrical engineering all have these basic equations. What are the basic equations in computer science? Or is computer science baseless?

Neville-Neil goes on to describe data structures as one of the foundations of computer science. John Dupuis led a discussion on his blog.

Computer science does have a problem of focus. What we theorists do can differ considerably from AI and operating systems. Some machine learning people might list Bayes rule as a fundamental equation.

The "base" of a field are not a set of equations but of principles. After all what are the basic equations of biology?

How about computational complexity? 

• The Turing Machine: A robust formal model of computation.
• The idea that we measure resources as a function of the problem size (from the Hartmanis-Stearns paper from which our field gets its name).
• Our Goal: Understanding the power and limitations of efficient computation.

STOC/CCC/EC/THEORYDAY/GRANTS

Announcements:

1. STOC Early Registration closes on April 30. STOC itself is June 6,7,8.
2. CCC Early Registration closes May 3. CCC itself is June 9,10,11.
3. EC Early Registration closes on May 6. EC itself is June 7-11.
4. The IBM Research|NYU|Columbia Theory Day is Friday, May 7, 2010. See here for details.
5. Call for applications for 2011-11 Computing Innovation Fellows. For details see here.

Predictions that are not on intrade.

1. CCC will top 100 for attendance. I think so because (1) In prior years when we co-located with STOC we have topped 100: Berkeley-1986 we had 110, and Montreal 2002 we had 140. (2) I suspect there are people who often goto STOC who will go to CCC this year since it is easy to do. (I am the opposite- I always go to CCC (only missed one) and will goto STOC because it is easy to do.) See here for info on attendance at CCC and here for opinions on the attendance at CCC.
2. STOC and EC overlap may hurt one or both of them. I could be wrong and it may help both of them since you can dash from hotel to hotel depending on the session.
3. CCC and EC overlap may hurt one or both of them. I could be wrong and it may help both of them since you can dash from hotel to hotel depending on the session.
4. Lance is going to ALL THREE: STOC, CCC, EC. I hope he's in good shape to do all that dashing. (This is not a prediction since I know that its true.)
5. Theory Day in New York will be AWESOME! I doubt that can be quantified. Hence it cannot be on intrade. (Alas I cannot go because of other commitments.)
6. The winners of the Computing Innovation Fellows will deserve it, though some of the people who apply who don't get it will also deserve it.

A possible NP-Intermediary Problem

(REMINDERS: STOC Early Registration closes on April 30. CCC Early Registration closes May 3. EC Early Registration closes on May 6. )

(ADDED LATER- AS STATED the problem below has problems with it. After reading see Eric Allenders comment in the comments.)

Here is a problem whose complexity has probably not been studied. I think it is NP-Intermediary. I will also give a version that is likely NPC. I am proposing that you either prove it is in P or NPC or show that if it is NPC then PH collapses (or something unlikely happens).

DEFINITION: We call a coloring of the x by y grid proper if there are no rectangles with all four corners the same color.

Let L be The set of all (x,y,c) in UNARY such that there is a proper c-coloring of the x by y grid.

1. Clearly in NP: verifying that a c-coloring of x by y is proper can be done in time poly in x,y,c.
2. Let L_c be the set of all (x,y) such that (x,y,c) ∈ L. L_c has a finite obstruction set and hence is in O(|x|+|y|) thought the constant depends on c. This can be proven by Well-Quasi-Order theory which yields nonconstructive bounds on the size of the obs set, or there is a proof with reasonable O(c²) bounds. (For ALL info on this problem and links to more info see the links below.) Hence the problem is Fixed Parameter Tractable.
3. I suspect that the problem L is NP-intermediary. Why? I think its NOT NPC since there is not much to play with- just 3 numbers. I think its not in P because my co-authors and I have not been able to do much more than ad-hoc colorings (this is not that good a reason- however the 17x17 challenge (linked to below) has lead other people to think about the problem and not come up with clean solutions.)
4. It is likely that the following is NPC: The set of all (x,y,c,f) where f is a partial c-coloring of the x by y grid such that f can be extended to a proper c-coloring.
5. I suspect that whatever is true for rectangles is true if you replace rectangles by other shapes such as a squares. There are also other Ramsey-Theoretic functions that could be studied (though Ramsey's theorem itself not-so-much--- verifying is hard).
6. This question is related to the (still unresolved) question I posed here and that Brian Hayes explained better here. However, I don't think proving the general problem NPC will shed light on why determining if (17,17,4) ∈ L is hard. That's just one instance.

Trading Money for Computation

Since the beginning of complexity we talked about time complexity t(n) as a function of the input size. But it has been the inverse of this function that we really care about: We have a roughly fixed number t of computation steps available on our computer and we want to know the largest problem we can solve within that running time. The value t has increased dramtically under Moore's Law and we care about how much larger a problem we can solve with our larger running times.

You could get around the limited time with a large investment in additional computer hardware but that rarely made sense to run a single algorithm. But in several (non-theory) talks I've seen recently you see speakers talking about solving their large problems by renting time on Amazon's servers. You can now cheaply buy computing time on the cloud via Amazon or Microsoft and soon via Google.

Cloud computing doesn't make all computing cheap. One still needs to have good parallelization since the problem gets run on many servers with limited communication between them. And all the servers in the world won't beat out exponential growths in running time. The P versus NP problem remains a problem. Nevertheless we need a good formal framework to study these problems.

Computational complexity has in the past adapted well to new computation models from the PRAM to biological and quantum computers. But we are seeing new computing paradigms in multicore and cloud computing and theory seems late to the party. There was a nice SODA paper on MapReduce, the basic cloud computing operation, but for the most part theorists haven't tackled the cloud computing model and only a few have looked at multicore. Theory can say much about new computational methods, both in how we can take advantage of them and what they can't do, but only if we make the effort to develop the proper models to capture these new approaches.

Google VS Experts VS readers VS Bing

If you want to find something out you can ask Google, ask an expert, or (if you have a blog) ask your readers. Google is the most common; however, there are times when asking an expert or your readers does better.

1. In my last post I asked for a Pangramic Palindrome- a sentence that was the same backwards and forwards and had all of the letters in the alphabet. I had spend some time on Google and other search engines trying to find such, with no success. Within an hour of posting Gareth Rees pointed to Peter Norvig's Pangramic Palindrome! I also found out (NOT to my surprise) that someone else had asked about such things. (NOTE- my spell checker wanted me to replace Pangramic with Pancreatic.)
2. In this post I asked if the following was true: Given 2k-1 integers there exists a subset of k of them that sum to a multiple of k. I had looked at Google ALOT for this one and also asked some people, but didn't find anything. The comments pointed to a paper on the subject which answered the question (yes) and also gave additional theorems. If I had asked just a few more people I would have gotten it without asking my readers; however, like the HALTING problem, its hard to know when to stop asking and when to start posting.
3. In this post if a certain sum that my co-author Clyde Kruskal proved was new. (I was sure it wasn't but couldn't find a reference.) I got a WONDERFUL combinatorial proof in the comments. I'm much happier with the combinatorial proof. (I also got a reference- Euler beat Clyde to it. Oh well.)
4. In both this post and this post I asked readers if they wanted to review books for SIGACT NEWS. I got far more responses then I usually do when I just print it in my column.

Will search engines ever be so good that they are better than asking experts or asking your readers? (In the future we will all have blogs and hence we will all have readers--- though with FACEBOOK the future may be now. In the future we will all have 15 readers.) I doubt it. For several of the questions above I didn't know quite what to look for. For example I didn't know to look for Palindromic Panagram.

On a related note- has anyone tried BING? How does it compare to Google?

A Post on the Post Post

On Monday Richard Lipton wrote a nice piece on the work of Emil Post, a famous logician who had great results and even greater questions in the early days of recursion theory. I have a few comments and thought I would follow up with my own post.

As Lipton mentioned, Post showed that every language that is both c.e. and co-c.e. is computable. Lipton talks about the open complexity version, what he calls Post++: L is in P if and only if both L and its complement are in NP, or in my terms P = NP ∩ co-NP. Lipton seems to suggest that Post++ is true but consider the following language:

A = {(n,r) | There is a m that divides n with 1 < m ≤ r}

A is in both NP and co-NP (even UP and co-UP) by guessing the prime factors of n. If A is in P then you can factor n by binary search. So if you believe that Factoring is a hard problem you have to believe that Post++ is not true. Lipton alludes to this when he says Post++ would kill most crypto protocols.

Lipton then talks about Post’s problem: Show there are non-computable, incomplete computably enumerable sets. Post had a program for this problem: Find some property P of sets, show there are non-computable c.e. sets with property P and no complete sets have property P. Out of Post’s program came useful properties such as simplicity, mitoticity and autoreducbility  but it wasn’t the right approach to solve Post’s problem. A decade ago I co-authored a paper that talked about using polynomial-time version of autoreducibility to separate complexity classes but we were also unsuccessful so far in using it to prove any new separations.

Friedberg and Muchnik independently settled Post’s problem in the late 50’s (Ladner proved the complexity version, assuming, P ≠ NP in the 70’s). Lipton asks “why do open problems stay open for years and then get solved independently at about the same time?” The answer is they don’t, most open problems are not solved independently, Fermat’s Last Theorem, Primes in P, etc., but the few that do stand out.

In our field if you look at the most famous examples: Friedberg and Muchnik, Borodin and Trakhtenbrot, Cook and Levin, Immerman and Szelepcsényi, you have two people, one on each side of the Iron Curtain during the cold war in a time before we sent results electronically. It could take several years for results to travel giving a much larger window for “about the same time”.

To solve Post’s problem one needed “computational thinking,” in this case thinking of c.e. sets as being produced by a computational process. Post didn’t think of c.e. sets this way, they were called recursively enumerable back then. Friedberg and Muchnik were children of the new computer age and could make that intellectual leap needed to solve Post’s problem. That’s why Post’s program was solved in the US and Russia at about the same time.

P and NP: A Short Movie

YouTube Link

Is there a pangramic palindrome?

Pangrams are sentences that contain every letter of the alphabet. The classic is

The quick brown fox jumps over a lazy dog.

(NOTE- I had jumped but a reader corrected it to jumps) There are more here.

Palindromes are words, phrases, sentences, or even longer that are the same backwards as forward. See here for history and some examples. Weird Al has an entire song that is just palindromes which is titled bob. (Its the 14th best Bob Dylan satire of all time: See here which has a pointer to a ranked list.)

BUT here is my question: are there any sentences that are BOTH Pangrams AND Palindromes? I really want to ask are there any in English that are not too contrived. However, seaching the web I couldn't find any at all!! So I'll be happy to find any in any language.

Life without Flying

A reminder that registration for all three Cambridge conferences are now live: STOC (early registration deadline April 30), Complexity (May 3) and Electronic Commerce (May 6). The week of June 6th should be quite exciting and busy.

Bill asked me about Europeans who might not want to register early given the disruption of flights due to volcanic ash from Eyjafjallajokull. While the possibility that problems will persist into June is very slight, we will reimburse any registrations for people unable to travel to STOC because of flight cancellations related to Eyjafjallajokull. While I can’t speak for CCC and EC I suspect they’ll have similar policies. So preregister with confidence.

In computer science, we have become quite dependent on air travel, for attending conferences, being able to give talks and discuss research with colleagues, for attending committee meetings and grant review panels, recruiting trips and much more. I’ve argued before that the main reason CS handles conferences and recruiting differently than every other academic field is because CS didn’t really get started until the jet age.

Suppose that the volcano situation happened at a larger scale and prevented air travel worldwide for the next several decades. How would our field (not to mention the rest of society) adjust? We could still travel just a bit more slowly. We wouldn’t revert back to the early 20th century situation with conferences either regional or rare. Rather video and Internet conferencing tools will become much better and widely available.

When we make the effort to travel, we and the people we visit make the effort to focus on the purpose of the trip. Harder to spend the day in my office claiming I’m busy if I’m just working with a colleague over the Internet.

The end of air travel would force the issue making it socially acceptable to virtually travel somewhere. Meanwhile I don’t get jet lag, get to sleep in my own bed and spend more time with the family. I think I’d like the no-flight world.

Is Guessing a good idea?

The following is from an Ask Marilyn Column. I paraphrase this since its from memory.

READER'S LETTER: I have heard of exams where you are penalized for guessing. How do they know you are guessing?

ANSWER: These are multiple choice exams where you get (say) 4 points for getting it right but -1 for getting it wrong. Hence guessing might lower your score. (NOTE TO READERS: Earlier version had an error so I just shortened it to eliminate error.)



I recently gave an exam where part of it was as follows:

For each of the following 10 languages indicate if it is REGULAR, CONTEXT-FREE BUT NOT REGULAR, or NOT CONTEXT-FREE. You may also leave it blank. You get +3 for a right answer, -3 for a wrong answer, and 0 for leaving it blank. DO NOT GUESS! Really DO NOT GUESS! If your total score is LESS THAN 0 then you will just get a 0. (NOTES TO MY READERS: This is DIFFERENT from the SATs and other exams that use this way to grade. For this post I omit the 10 languages.)

This problem inspires a math problem:

Should a student guess? If a student has NO IDEA how to do ANY of the questions then there is no harm in guessing since leaving all blanks will yield a 0, whereas guessing at random might yield a positive score. (If a student has NO IDEA but can do this reasoning then perhaps he should drop my course and take probability instead.)

What if the student is sure of ONE of the answers? Then should he randomly guess the rest? Randomly guess some of the remaining? What if he is sure of x of the answers? What is the value y so that he should guess y of the remaining but should not guess y+1? For x=0 I think the answer is y=10.

Here is one general question: There are n problems on an exam, each one has c choices. You get A points for getting a problem right, B points for getting a problem wrong, and C for writing DK for Don't Know (I had toyed with the idea of giving 1 points for DK.) If you know x of the answers and are clueless on the rest, how many should you guess (as a function of n,A,B,C,x)? We assume that those that you don't guess you write DK (admitting that you don't know something is helpful here, as in life). You can assume A > 0, B < 0, C &ge 0.

One can ask more general questions by dividing the questions into c categories: Those where you can eliminate 0 options (clueless), 1 option, 2 options, ..., c options (you know you are correct).

If a student can figure out how many to guess on during the exam then they are likely a very good student and should guess 0 of them.

The Pad

So I broke down and bought the iPad. Many people have asked whether the iPad is worth buying. The short answer: It will be.

There are many many iPad reviews out there on the web so what can I add? It wins as an entertainment device. My favorite apps so far: Netflix (streaming looks great), Instapaper, The Weather Channel (TWC Max+) and of course MLB. Oddly enough no built-in calculator but the Wolfram Alpha app is pretty cheap now and there is the free Pcalc Lite.

Books look much prettier on the iPad than the Kindle but for reading for a long stretch I prefer the Kindle. Feels more comfortable on my middle-aged eyes.

Based on some suggestions from my Twitter followers, I bought the iAnnotate PDF app which offers some great mark-up tools from PDF. But it is really difficult to move files to the app. I still haven’t figured out how to do it on Northwestern’s network. The next version of iAnnotate should make it easier to move files but Apple really needs a standard way for applications to share documents so I can download from Safari into programs like iAnnotate.

I hope Google optimizes their docs for the iPad. I’d love to be able to edit them.

Supposedly multitasking comes in the fall. But right now I can run two tasks at a time by running one of them on my iPhone. Don’t laugh--I can now stream baseball games while surfing the web.

To make it a reasonable laptop replacement to take on trips, we’ll need someone to write a full-featured latex app including an editor along the lines of winedt. Would be considerable work but it could be done. I’d pay $50 for it. Also the iPad will need someway to connect to a projector.

I just have too many gadgets now: iPhone, iPad, Kindle and a laptop. I could imagine wanting to travel with all of them but at some point that just gets ridiculous. I keep hoping one day we’ll have one gadget to rule them all but I guess a device that fits in my pocket with a big screen and keyboard was just not meant to be.

New Constructive Aspects of the Lovász Local Lemma

Guest Post by Bernhard Haeupler

The Lovász Local Lemma (LLL), slightly simplified, states that: Given a set of “bad” events, if for every event A there exists a subset of events with total probability mass at most 1/e such that A is mutually independent to all other events, then the probability that all the “bad” events are avoided simultaneously is nonzero. The LLL is used in combination with the probabilistic method to (nonconstructively) prove the existence of, e.g., a satisfying assignment for any k-CNF formula in which clauses do not share variables with more than 2^k/e other clauses, optimal routing strategies, and many other (seemingly unrelated) structures of interest to TCS.

In the last STOC, Robin Moser gave his celebrated talk on how to find such structures efficiently, and later he and Gabor Tardos simplified his algorithm and generalized it to the full asymmetric LLL. They assume that the events are determined by a collection of independent random variables, and define two events as dependent iff they share a variable. This is the basic setting in most applications of the LLL.

The Moser-Tardos algorithm (henceforth MT-algorithm) is incredibly simple: Start with an arbitrary assignment and repeatedly take the variables of any one of the given bad events that holds currently, and assign new random values to these variables. Of course, attempting to “fix” such an event can lead to other neighboring events becoming violated, but the beautiful argument of Moser and Tardos shows that this branching process dies out quickly if the original LLL-conditions (even with the optimal constants) are fulfilled. This yields a randomized algorithm with expected linear running time in the number of bad events.

Recently, further important properties of the MT-algorithm have been shown:

1.) It can be derandomized using approximately logwise-independent probability spaces (or logspacefooling PRGs), if one allows an arbitrary small ε-slack in the LLL-conditions. This leads to deterministic (NC) algorithms for most LLL-applications with polynomially many bad events.

2.) It outputs a solution that not only avoids all the bad events, but has some further randomness properties: in exactly the same way as the conditional LLL-distribution (i.e., the distribution that conditions on all bad events being avoided) the output distribution of the MT-algorithm approximately preserves the probability of any event that is sparsely dependent on the bad events. While interesting in its own right, this can also be used to develop efficient algorithms for several LLL-applications in which the number of events is superpolynomial in the number of variables which in turn is the “size” of the desired assignment. It can be shown that even in these cases the number of resamplings done by the algorithm remains small (e.g., nearly linear in the number of variables), but often just finding a bad event that currently holds or verifying that the current solution avoids all the bad events – the two basic steps in the MT-algorithm – is (NP-)hard. The solution to this dilemma is to use the algorithm only on a suitably-chosen polynomial-sized core-subset of events. A union bound over the non-core events in the conditional LLL-distribution than shows that a good assignment is produced with high probability for essentially any LLL-application. This resolves, e.g., the curious situation of the Santa Claus problem for which two completely different non-constructive proofs for a constant LP-integrality gap had been developed, without leading to a polynomial-time constant-factor approximation algorithm.

Tom L DVD and Birthday and You Tube and...

April 9 was Tom Lehrer's 82nd birthday! To celebrate I give you breaking news that a Tom L DVD was released April 13, 2010. It seems to have some videos of him performing and some other things. It also has The Derivative Song which is not available anywhere else (except on You-Tube, so I suppose its actually available to anyone).

I first became aware of this material from someone who thought it would NOT be coming out on DVD. I got this email a few months ago:

I believe (or hope) that you are the blogger Gasarch who in 2007 wrote a blog called The definition of rare. And you had a good point: after some stuff has been made available on You Tube it's not rare anymore. Here are some more examples: Tom Lehrer material that's never been -- and probably never will be - commercially available to the public.

Right before I was going to post this I emailed the author if it was okay. He said that it was and he emailed me (1) about the DVD collection coming out, and (2) some more clips on You-Tube that were posted (I think) to advertise that the DVD is coming out. Here they are:

1. My favorite: Tom L doing a song by Danny Kaye that Tom L himself has said was the inspiration for his classic The Elements. Here it is: here.
2. Tom L singing two of his songs. Nice to see what he looks like, but nothing really new here.
3. Ad for the Tom L DVD.
4. Misc Stuff The first clip shows that Tom L is surprised it is coming out.
5. A letter from Tom L about having his stuff on You Tube. I wish more artists felt they way he did.

Will I find or be send other obscure Tom L stuff for next year. I kind of doubt it. However, I last year I would have doubted I would have more stuff this year.

Choosing a Graduate School

Besides being tax day, Thursday is the deadline to decide where to attend graduate school. How should you choose? I've blogged on this topic before but a few recent new wrinkles to talk about.

Typically Ph.D. programs in computer science offer funding (via fellowships, research assistants or teaching assistants) that cover your tuition and a small stipend. But a few programs at some financially-strapped universities are offering admission to the graduate program without such support. Should you join such a program if you can afford it? Maybe you'll get lucky and find an outside fellowship or an well-funded advisor but you have to worry about how much commitment the school will give you if they don't have a financial stake in your success. You really need to talk to the faculty involved and make sure you are comfortable with the situation.

As the field of theoretical computer science has gotten quite broad, theory groups at most universities cannot hope to adequately cover all research areas. Some departments have made the conscious decision to build strength in a particular area (like Northwestern in Algorithmic Game Theory). Joining such a group can be exciting if you are interested in that line of work but explore what other options would be available if you were to change your mind. 

Perhaps you are looking at the lousy job market for tenure-track faculty and thinking about not attending graduate school at all. Don't worry. As undergraduate enrollment is on an upswing, the economy recovers and the first wave of computer science faculty starts to retire the market should get much better by the time you get your doctorate. (And if I'm wrong this post may mysteriously disappear).

Sum of squares: How much to cheat?

In discrete math (or other courses) we teach AND DERIVE the formula for 1+2+3+...+n. We then look at the sum 1²+2²+...+n². Here there are some options.

1. State the formula and prove it by induction.
   1. PRO: This is a good example of induction.
   2. CON: The formula comes out of nowhere.
2. Do the integral method to show that its roughly n³. Then use constructive induction to get the actual result. (Constructive induction here would be the following: assume the formula is of the form An³ + Bn² + Cn + D and then, by doing the proof by induction, derive what A,B,C,D must be.)
   1. PRO: They get a sense that they have derived the answer.
   2. CON: A bit of a cheat. They didn't really derive it since the fact that it is roughly n³ is not a proof that it is a polynomial.
   3. CON: Messy. (This is probably what I would do in the standard Discrete Math course for Sophomores.)
3. Prove that it is a cubic poly by the method of differences. Then use constructive induction or curve fitting to find the actual answer.
   1. PRO: They really get to derive it.
   2. CON: You need to teach the method of differences.
   3. PRO: You get to teach the method of differences.
   4. CAVEAT: Whether you do it this way depends on what your goals for the course are. For our discrete math course this would be too far a field.
4. There is a clever proof from which you could derive the actual formula. An exposition of this proof is here.
   1. PRO: The method extends to sums of kth powers.
   2. CON: The algebra is a bit too clever. The out-of-nowhere problem again. (I will probably show this to the Honors Discrete Math course.)
   3. CAVEAT: Could use the method to just show that there IS a polynomial of degree 3 and then use Constructive Induction or Curve Fitting to find the exact formula.

What Makes a Lecture "Distiguished"?

In January I gave a Distinguished Lecture in the CS Department at the University of Alberta. In early March I gave essentially the same lecture at Penn State in their regular CSE colloquium. What's the difference?

One is audience. At my Alberta lecture I got a large turnout from the broad CS department. In regular colloquiums I usually just get the CS Theory types and people I know, though at Penn State I happen to know faculty ranging from pure logicians to experimental economists.

I'm more likely to accept an invite as a distinguished lecturer. I don't usually travel to give a regular seminar talk unless I'm using it as an excuse to visit specific people and I didn't really know anyone at Alberta well save for one former NEC colleague. 

Perhaps the biggest difference is attitude. As a distinguished lecturer, people want to talk to me, my schedule is booked solid shuffling from office to office much like an interview trip. People want to hear what I have to say because I was "distinguished". I have no shortage of opinions and I always like an audience willing to hear them.

Baseball violates the rules of mathematics!!

(Looking for a roomate for STOC. Check out this site..)

Baseball Season started this week. I want to point out that Baseball violates mathematics in two ways.

1) By the rules of the game Home Plate is a right triangle with a square adjacent to it. And what are the dimensions of this right triangle? They are 12-12-17. BUT THERE CANNOT BE A 12-12-17 RIGHT TRIANGLE!!!!

2) (Information in this point is from Bill James Article The Targeting Phenomenon.) A players batting average is what percent of the time he or she gets a hit (its a bit more complicated since some things don't count as at-bats: walks, sacrifices, hit-by-ball, maybe others). You might think that the higher the number the less players achieve that batting average. Let N(a) be the Number of players with batting average a over all of baseball history. You might think

N(296) ≥ N(297) ≥ N(298) ≥ N(299) ≥ N(300)

But you would be wrong.

1. N(296)=123
2. N(297)=139
3. N(298)=128
4. N(299)=107
5. N(300)=195

There so many more players batting 300 then 299!. There so many more players batting 300 then 298!. There so many more players batting 300 then 297!. There so many more players batting 300 then 296!.

This would seem to violate the very laws of mathematics! Or of baseball! Or of baseball mathematics! Actually there is an explanation. Batting 300 has become a standard that players try to achieve. If you are batting 300 and it is the last week of the season you may become very selective on what balls you hit, you may ask to sit out a game, you will do whatever you can to maintain that 300. Similarly, if you are batting 296-299 then you will do whatever it takes to get up to 300.

This happens with number-of-hits (with 200 as the magic number), Runs-batted-in (with 80,90, and 100 as magic numbers), for pitchers number-of-strikeouts (with 200 and 300 as magic numbers), and wins (with 20 as the magic number).

If we all had 6 fingers on our hands instead of 5 then there would be different magic numbers.

So what to do with this information? Model it and get a paper out. Hope to see it at next years STOC.

But seriously now folks- what do you make of barrier results?

In my April Fools Day Post I said the following:

Here are problems that I believe can be solved with current techniques.

That was indeed true- since they were all known theorems. However, I was making a more serious point in capital letters. I will make it again here using all small letters.

in theoretical computer science we have some results on what techniques are not going to suffice to solve P vs NP and other problems. the authors of these results claim (correctly) that they are trying to get us to look at other techniques. however, proving barrier results can become an end in itself. what to the barrier results mean both mathematically and sociologically?

1. has there every been, in the history of mathematics, an open problem that inspired so many negative results?
2. one can argue that in logic there was work on negative result. however, before godel's inc. thm, was there the kind of flurry of activity to try to disprove hilbert's program could work that there is now on trying to prove that proving p \ne np is going to be hard. i do not think so. for ch there was more of this before cohen, but again, not as much as now.
4. how about in number theory? i have never seen a result along the lines of the following techniques will not suffice to solve goldback's conjecture. are there any?
5. why is P vs NP different than other problems in math? why have negative results about trying to prove it become a topic people work on?
6. to be fair there aren't that many negative results, though they seem to be growing and are regarded (correctly) as important.
7. the real question is will the barrier results lead to a prove that p is not np (or even that p is np though i find that unlikely).
8. the other real question is, are these results being pursued because they are important or because we are in a rut and can't do much else. i tend to think its because they are important since (a) there is lots of non-barrier work in complexity also, and (b) barrier results are hard! it would be an odd way to get out of a rut by going into a really hard area. when i am in a rut i try to do things that are rather doable.

Finding the Right Model

Last fall I wrote about the different focus on models and proofs in the Econ and CS theory communities. Today I'll focus on the purpose of a model and what makes a good one.

An economist once explained the difficulty in coming up with a good model. A good example is how people prefer one choice to another. In standard utility theory, people assign a value (or utility) to each state of the world and try to maximize their expected expected. But then one notices people tend to give too much weight to low probability events like in the Allais Paradox. So one can look at more general models of preferences such as prospect theory. But these general models might be too general, and thus have little explanatory value and in particular may not allow us to predict future behavior and outcomes, the ultimate purpose of an economic model.

In computational complexity, we don't use our models for prediction of future events. Our models of computation are meant more for comparing different types of resources: Time versus space, quantum versus classical, parallel versus serial and of course, nondeterministic versus deterministic. What makes a good model for us is robustness (small changes to the definition doesn't change the problems it can solve), nice closure properties and some connection to reality. Sure the class P, Polynomial-time, is not equal to efficient computation if the constants or exponents of the running time are large but it's a reasonable approximation.

Part of my research agenda over the past few years is trying to find computation models for agents in economic theory. Many of the ideas of our community, such as connections between randomness and unpredictability, can play an important role in economic theory. But finding and determining what is the right models are the biggest challenge, as even the purpose of models differ in our communities. Communication is the key, working directly with people in the other community. One of the great advantages of Northwestern is having a large strong micro-economics group, many of whom understand that computation is an important resource and are willing to at least listen to us computer scientists.

We also need to keep an open mind--the goal should be making the best connections between communities and not worrying so much about results to impress our direct peers. Having tenure definitely helps.

What Does It Meant to be Published?

I don't remember what prompted it but about a month ago I tweeted

Your paper might appear on Arxiv or ECCC, be widely read and even well cited. But don't think that it is in any way "published".

Suresh responded

Question is, isn't the point of publication to be "widely read and well cited"?

So what is the point of publication? Certainly you want your paper easily read and cited. But also you want a careful peer review leading to a polished version that has the stamp of approval by appearing in some respectable conference or journal. Publishing also acts as a filter, allowing the reader to get some idea of the level of quality of the paper before reading it. Almost any paper can appear on an archive site but it takes more to be published.

Nevertheless if you get major kudos for your archive paper, why bother taking it further? Even if people like your paper now, it may be forgotten years from now. Complain as you will about journal publishers, they are scanning in all the old articles to make them available in a digital age. Papers that years ago appeared as old department technical reports may be lost forever. Nobody can predict what form research papers may take one hundred or even ten years from now. One day those PDF files may no longer be readable. Get your paper really published and you have a much better chance of it surviving far into the future. 

A few years ago, the IEEE saw no reason to scan in old FOCS proceedings thinking that any of the important old papers appeared in better form in some journal. We knew though that if these papers weren't put in digital form, many of them might disappear forever. With some strong pushing by Paul Beame, Bob Sloan and others, those papers are now available on both the IEEE and Computer Society digital libraries.

I wanted to read a copy of Karp's NP-completeness paper which only appeared in the proceedings of a one-shot workshop in 1972. I ended up going to the library to dig it up. But library books get lost and many young people today don't even know where the library is. Later I found out Luca had scanned the paper for a course he taught. But how long will Luca's Berkeley pages last and what about all the papers that don't lead to Turing awards.

So publish your papers, best in a journal as well as a conference. Even if you don't think it matters for you in the short run, it can make a big difference for the community long into the future. What good is pushing the boundaries of science if those boundaries get snapped back because work gets lost.

SIGACT Social Networking

STOC conference and hotel registration now live. Early registration deadline is April 30th. Registration for Complexity and Electronic Commerce coming soon. You can now submit your papers to FOCS, deadline 11 PM Eastern on Wednesday.

We are in the midst of reorganizing the SIGACT web presence. We have redesigned the SIGACT website now under the supervision of Amit Chakrabarti. As I've announced here before we have a new blog Theory Announcements that collects a broad set of TCS related announcements including from TheoryNet and DMANet. If you have an event or announcement you want to appear there, please submit it to one of those mailing lists.

But the days that one needs a theory portal are gone. Google and other search engines work well if you want information on a specific conference, journal or researcher. But what you do need is something to guide you through the clutter. Right now you have to rely on a network of theory bloggers and tweeters to keep you informed. But even then you get important theory information mixed in with personal stuff you may not care about (or vice versa).

So I've started a @sigact twitter where we will point to important information and news relating to the theory community. Recent tweets will also appear on the SIGACT home page. Lets me focus my own twitter and this blog away from announcements (like this one) and more on giving our opinions of the important issues of the theory community.

But that's only the start. We'll continue to search new ways to serve the needs of the theory community: a revamped theory calendar, some sort of jobs database, Facebook and other social networks, and a killer iPad/iPhone app. I don't really have plans for an iPad/iPhone app or know what should go in it but I'd love to have one. 

Lets Prove Something instead of proving that we can't prove something

We complexity theorists seem more concerned with proving that we can't prove things than with actually proving things!!!! There have been two workshop on Barriers - reasons we cannot prove things (See here and here ). In a prior blog entry I pointed out that in an excellent talk by Peter Bro Miltersen he listed as an open problem that he wanted to get a barriers result. In fact, he seemed more interested in proving that nobody could prove the result then in proving it.

We are in a rut. We seem to have the urge to show a theorem is hard to prove rather than to actually prove it! To be fair, many of our conjectures are hard to prove. Even so, we need to get out of this rut. I list several problems that I think can be solved with current techniques. For each one I will say why the current barrier techniques might not apply.

1. Prove that NP not equal to EXP=DTIME(2^O(n)). There are oracles for proper containment either way, and for incompatibility (see this paper) but there are no oracles for which they are equal. Also note that NP is robust and EXP is not. That might be useful. DO NOT TRY TO FIND AN ORACLE TO MAKE THEM EQUAL!!! THAT IS THE MENTALITY I WANT TO BREAK US OUT OF!!!
2. How do NL and P compare? There are oracles to make either properly contained in the other (see this paper). However, Relativized (spellcheck made me capitalize Relativized) space has several definitions and its not clear which one is appropriate (Jonathan Buss's and Ruzzo-Simon-Tompa have worked on this). DO NOT TRY TO FIND THE RIGHT DEFINITION OF RELATIVIZED SPACE!!! JUST PROVE A CONTAINMENT EITHER WAY!!! IT DOESN"T EVEN HAVE TO BE PROPER!!! OR PROVE THEY ARE THE SAME (unlikely).
3. Is NL properly contained in PSPACE? Of course it is, but lets PROVE IT rather than REDEFINE ORACLES to prove that its hard (some of the same comments for NL and P apply here).
4. Lets look at Nondeterminism in a different light- for rather powerful classes and rather weak ones.
   1. Let PR be the set of SETS that are Prim Rec, and NPR be the set of all SETS that are Nondet Prim Rec. Is PR=NPR? DO NOT TRY TO DEFINE PRIM REC WITH ORACLES TO OBTAIN A BARRIERS RESULT!!!! JUST SOLVE THE DAMN PROBLEM!!!
   2. Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA). Do they recognize the same set of languages or not? DO NOT DEFINE DFA'S WITH ORACLES!!! DO NOT TRY TO MAKE DFA's FIT INTO THE NAT PROOFS FRAMEWORK!!! JUST SOLVE THE BLEEPING PROBLEM!!!!

SIGACT Awards

ACM announced the following awards recently. Note that some of the awards are named after theorists and some awards went to theorists.

Any comments on their work are welcome.

See here for the formal list and more information. I also list them here:

1. Eugene L. Lawler Award for Humanitarian Contributions within Computer Science and Informatics: Gregory Abowd, Georgia Institute of Technology
2. Paris Kanellakis Theory and Practice Award: Mihir Bellare, University of California, San Diego, Phillip Rogaway, University of California, Davis
3. Karl V. Karlstrom Outstanding Educator Award: Matthias Felleisen, Northeastern University
4. Grace Murray Hopper Award: Tim Roughgarden, Stanford University
5. ACM AAAI Allen Newell Award: Michael I. Jordan, University of California, Berkeley
6. Software System Award: Mendel Rosenblum, Stanford University, Edouard Bugnion, Scott Devine, Edward Wang, Jeremy Sugerman. They founded the company VMware.

Traveling Too Much

Three recent happenings made me think about the amount I travel.

• I hit the 50K club (Premier Executive) in United for the first time last year. At first I was excited about the extra perks. But then got depressed over so much time away from the family.
• The movie Up in the Air
• A family friend recently died during a business trip. In his hotel room. Alone. Could have been me.

And according to United I've already traveled 18,641 miles in 2010. 

I don't like the hassle of traveling. The excitement of visiting new lands has long past.

So why do I travel? The one-word answer: People. I like to meet my fellow colleagues, talk with them, make myself, my group, my field known and help shape future research. When you travel people make time for you and you make time for them in a way email and conference calls can't do.

Nevertheless I will make an effort to travel less, certainly while I have those last few precious years before my kids go off into the world. If you invite me some place and I turn you down, don't take it personally. I'm just trying to bring back some sanity into my life.

Book Review Column AND request for reviews

A while back I posted a list of books that I needed reviewed for my column in SIGACT NEWS. This was legitimate--- I really did want reviewers--- but it was also an experiment in the power of this blog. Would I get more reviewers? How would the quality of the reviews be?

The results are in: Roughly 40 people asked for books, and 35 are done. Of the 5 left 3 asked for extensions that were legit. Only 2 were really derelict (of those 2, one returned the book). All the reviews I received were of high quality. (If you only asked for an extension in the last month, then you are the derelict one. No more book reviews for you!)

The experiment also indicates that far more people read this blog then read my column, though I already knew that. To extend the reach of my column I will begin posting it on this blog when it comes out, with one change:

1. Here is Volume 41, No. 1, 2010, SIGACT NEWS book review column. Sort of. I intentionally OMITTED the part where I ask people for books to review. That is because the list that was with that column is already out of date.
2. I once again INVITE you to email me that you want to review a book. Here is a list of available books.
3. Here is advice for reviewers. Here is a template for a review.
4. Procedure: If you want to review a book then email me your postal address to send the book to. The review should be ready about 3 months after you receive the book; however, that can be flexible so long as there is some definite due date, past which I can email you `HEY, WHERE IS THE REVIEW!' If you are in America then I will postal mail the book to you and it should get there fairly fast. If you are not in America then (because of postal rates) I will have the publisher send the book to you. It may be a while before you get it.
5. The sooner you ask for a book the more likely you are to get it. I will try to update the list; however, you may end up asking for a book that I already assigned if you see it before I update it.

Turning down a Fields Medal is eccentric, turning down the Millennium Prize is INSANE!

NEWS on Poincare Conjecture:

1. Recall that Perelman was given the Fields Medal in 2006 for proving the Poincare Conjecture. He declined the award.
2. Recent news: Quoting the Wikipedia article on Perelman: Perelman was officially awarded the Millennium prize on March 18, 2010. Note that they are giving it JUST to him. There was some discussion earlier if there would be split credit of some kind.
3. He turned it down! That is, he turned down $1,000,000. See here
4. Perelman's reasons for turning down the Millennium prize are likely similar to why he turned down the Fields Medal. To quote him on the Fields Medal: I'm not interested in money or fame. I don't want to be on display like an animal in a zoo. I'm not a hero of mathematics. I'm not even that successful; that is why I don't want everyone looking at me.

Some random views I've heard about this: NONE are mine.

1. Turing down the Fields Medal ($15,000) is eccentric. Turing down the Millennium prize ($1,000,000) is insane.
2. I have some sympathy. I have a grant and now I have to work on the stuff it says to work on rather than the stuff I later got interested in. Money and prizes should not guide research. Wait, did you say its $1,000,000? My mistake, this guy is not playing with a complete axioms set.
3. By turning it down the Fields Medal, and now the Millennium prize, he gets more people to look at him like he's an animal in a zoo. I doubt he planned that.
4. After turning down the Fields medal, if he had taken the Millennium then it would look like he had compromised his ideals (making him an ideal compromiser). But see the next item.
5. His reasons for turning either prize down do not seem idealistic.
6. It was rumored that Andrew Wiles locked himself in his attic or basement for 7 years to work on FLT. This story is either false or an exaggeration. It made the rounds because it enforces the stereotype of a mathematician. By contrast, Perelman's story IS true but is SO bizarre that I do not think it enforces any stereotype.
7. Is Perelman still doing math? If he solves Riemann then he'll save the Clay Inst. another $1,000,000.
8. What happens to the money? Do the other prizes all get increased by 1,000,000/6 ? Do they find another problem instead?
9. Some in Russia are saying he should have given it to charity. On the other hand, the Clay Inst IS a charity, so in a sense he did give it to a charity. Instead of helping Russian Orphans he is helping Mathematicians.

Laci Babai Turns 60

I'm at Ohio State for the Combinatorics, Groups, Algorithms, and Complexity Conference in honor of Laci Babai's 60th birthday. An incredible turn out with 74 talks. I've never seen a birthday conference with parallel sessions before. A nice mix of computer scientists and group theorists and a surprising number of Laci's former (and current) students made the trip incluing some Hungarians I haven't seen in twenty years.

I gave a talk yesterday on Wednesday about how Laci indirectly and directly affected my early research career. My Ph.D. thesis was on interactive proofs which Laci co-invented in 1985 as Arthur-Merlin games. When I graduated in 1989, I was lucky to get a 2-year position at the University of Chicago, a great theory department with Laci Babai as its star. That 2-year appointment lasted nearly 20 years, much because of the research I did with Laci those first few years.

I wrote four papers with Laci: MIP = NEXP, Arithmetization, Derandomization under worse-case assumptions and Holographic Proofs. These were all exciting papers. MIP = NEXP is surely the most influential paper I had since it led to Probabilistically Checkable Proof Systems.

Even when we didn't co-author, Laci was an invaluable research. My advisor, Mike Sipser, told me his approach to research in complexity: Find the underlying combinatorial problem and solve that problem. I took that a step further: Once I couldn't solve the combinatorial problem I walked down the hall to Laci's office where he could often find a simple trick that gave me what I needed.

Beyond research, Laci really gives himself to the community with his teaching, the Budapest Semesters in Mathematics and his open access journal Theory of Computing.

Thanks Laci for being my Merlin.

What I'm Doing Over Spring Break, Part I

It's spring break at Northwestern and as I write this Tuesday morning, I'm on a plane from San Francisco to Denver on my way to Columbus, Ohio. My kids have their spring break next week during my first week of classes for the spring quarter. So no family vacation for me and instead I'm bouncing around the country.

Stop one is Palo Alto for a meeting of the Council the Computing Community Consortium (CCC), my first since joing the council in January. Not be confused with the other CCC in my life, the Conference on Computational Complexity.

CCC is an NSF-sponsored program of the CRA that finds opportunities for computer reasearchers programs in the NSF and other governmental agencies. CCC acts like a facilitator, an interface between CS researchers and governmental funding agencies and policy makers.

So what does the CCC do? A few of its activities.

• The CI Fellows Program.
• A series of visioning workshops including one that helped created nuggets for theoretical computer science.
• A set of presentations given at the Library of Congress. Luis von Ahn's talk has over 50,000 views.

Many of you are wondering about the future of the CI Fellows program. All I can say is it is still up in the air and as the funding situation is being worked out.

Because of the CCC meeting I missed the first half of Laci Babai's 60th Birthday Celebration Conference at Ohio State. More on that event tomorrow.

Stoc Travel Support/WELCOME BACK LANCE!

(REMINDER AND UPDATE: If you are a a grad student you can apply for travel support for STOC 2010. See here for details. One update on that: since registration and hotel information for STOC 2010 is not posted yet, you can estimate it on your application, or say + registration, + Hotel. NOTE- deadline is Friday March 26. If you are a professor I ask you to email the theory grad students at your school, who don't read this blog (if there are any), about the travel support available.)

To welcome Lance back from his Blog Sabbatical here is a post that will inspire comments like When is Lance coming back? I even tossed in a few mistakes to feed the grammar-trolls. (Is ``grammar trolls'' hyphenated?)

Some states are banning cell phones while driving or texting while driving. Not sure what I think of that. Should they ban putting on makeup while driving? How about arguing with your spouse while driving? Maybe they should have a general rule about driving under the influence of distraction. But that is probably too vague. On the other hand, I think we can all agree that they should outlaw tweeting while piloting:

Notes to My Dad

My father Paul Fortnow passed away thirty years ago today. Five years ago I wrote about some of the lessons I learned from him. 

Suppose I could go contact him back into time. What would I tell him?

I could tell him about his beautiful granddaughters.

I could tell him that his Red Sox won another world series in 2007 but some things don't change, it's the Yankees who are reigning champs.

I could tell him about a device in my pocket called an "iPhone" that lets me contact anyone, access nearly all public information and it plays music and movies too. A big improvement over the Sony Walkman.

I could tell him about how easily we can search for the most trivial information. I learned that he wrote a review article when I was just a baby, that the house he grew up in was torn down and replaced with the Marshfield city hall, and that he died just about the same time that JR was shot. 

I could tell him the answer to the biggest mystery of his generation: FBI Agent Mark Felt was Deep Throat.

But most of I would tell my father that taking one children's aspirin every day reduces the risk of heart attacks and maybe, just maybe, I'd be telling him these things in person. 

Unique Games Redux

With spring quarter arriving, I will take a break from book writing on P v. NP and come back to blogging. I hit my goal of getting past the point of no return (about three draft chapters out of ten) but writing a book is a slow process.

I've been hearing a bit of buzz about a new algorithm from Arora, Barak and Steurer for unique games that I first saw in Luca's blog: Given a unique game where 1-δ fraction of the edges can be satisfied, you can in time 2^npoly(δ) find a coloring that satisfies a constant fraction of edges.

Does this kill the unique games conjecture, that the unique games problem is NP-hard? Not yet. For every ε>0, there are NP-complete sets sitting in time 2^nε. It's possible that there is some reduction from SAT to unique-games will have the property that to get a smaller δ requires an algorithm with a running time whose polynomial depends on δ.

But does it give evidence that unique games may now be false (right after Khot won the Waterman award)? Any improvement in the Arora-Barak-Steurer algorithm would yield a subexponential-time algorithm for NP if the unique games conjecture holds.

But in the end it could go the other way. If no one improves on the ABS algorithm in the next year or so, it will seem like we've hit a barrier right at the edge of where the UGC could still be true. Which will make us think that UGC could be true again and after a while, ought to be true.

As Nietzsche might have said, what doesn't kill the unique games conjecture will only make it stronger.

A prospective Theory Blogger wants your input (Guest Post)

(Guest Post by M.T. Hajiaghayi)

Title: Successful blogs

Now that I'm joining Univ. of Maryland, and there are at several famous bloggers there, I may consider starting a new blog as well. I'm not so sure that this happens at the end, but before that I want to know what the others are thinking regarding a successful blog in CS and its criteria especially now that we have quite a few years of blogging in CS (e.g. see a list containing several of them in the leftside of this blog). I ask some questions below. Feel free to answer them or give any other comments. You may want to give even an example if you feel like it.

1. Do you like blogs which put controversial posts (like FOCS/STOC vs others) or the ones which only mention news? If you think both are necessary for a successful blog give your percentages.
2. Do you like blogs who give short or even long proofs? Do you think people are reading them carefully enough to justify the effort.
3. Do you like blogs who mainly talk about their authors esp. their achievements? In short do you like blogs which essentially say "How great I am?". Again you may give percentages here if you think it is not bad.
4. Do you like blogs which mention opinions of the authors explicitly or the ones that only mention questions without answers?
5. Do you like blogs of short posts or long posts? Give an estimate.
6. Should a blogger answer the comments or it is not necessary?
7. If you do not like a person or its work should you mention his/her name or you should never ever mention any names as a blogger.
8. Do you like blogs who repeat others' posts? If so give an estimate of how often you should do this.
9. Is the number of comments the main measure of successfulness?
10. Does a blog need a focus?
11. Are there too many theory blogs out there already?
12. Will a blog help you on the job market? Tenure? Full Prof?
13. What role do or should Blogs play in our community?

Repost on Turing and Wasserman- lets talk about...

One of the commenters on the post on the recent Turing Award and the Waterman award pointed out that the context I gave lead to a discussion that was NOT about the work of Chuck Thacker or Subhash Khot. The commenter said: Can you post this again without the additional context so that the community could write some comments on their work OKAY, consider it done. Now, commenters, its up to you.

1. The Turing Award for 2009 was given recently to Chuck Thacker LINK. See here. He developed the first modern PC.
2. The Alan T. Waterman award was given to Subhash Khot. See here. He formulated the Unique Game Conjecture and has proven many consequences of it.

Central Website for FOCS as a whole (guest post)

(Guest Post by Paul Beame)

There is now a central website for the FOCS conference as a whole here!!

In addition to links to the most recent and upcoming conferences one useful item that is included are locations and direct links to all the past proceedings on the CSDL and IEEExplore since these are not always easy to find from the IEEExplore search feature directly. (CSDL is pretty good). Proceedings from all prior FOCS conferences are up on the website and linked in. (The 50th FOCS is up on CSDL but not yet on IEEExplore.)

FYI: CSDL is the Computer Society's digital library. IEEExplore is for all of IEEE. Institutions subscribe to one or the other. The CSDL is smaller (since it only does the Computer Society) and cheaper and returns more money to the CS than IEEExplore does which is why the two haven't merged.

Theorems that you simply don't believe

There are some theorems that are surprising. I've already blogged on that (I can't seem to find the link). However, there are some theorems that some people simply do not believe. I mean people who understand the proofs and still don't believe them. Let me give you a contrast- I DO believe that NSPACE(n) is closed under complementation because, while surprising, the proof really does tell you why its true. For the following surprising results the proof does not help. Or at least does not help the people who were surprised by it.

1. Barrington's theorem. I've read it, talked to Barrington about it, and even taught it. I still don't believe that (say) the set of strings that have the number of 1's equivalent to 0 mod 101 can be done by a width 5 branching program.
2. Banach Tarski Paradox A CS grad students who knows some math says that it shows that mathematics is broken. I would prefer to say it casts doubt on the axiom of choice.
3. The classification of finite simple groups. Does any one person even know the proof? Couldn't they have missed some group? Counter argument: the list is on Wikipedia so it has to be correct.
4. The rationals and naturals are the same size. I know someone who knows the proof and is happy to say they are the same cardinality but refuses to say they are the same size. (I think they are wrong and this is important- using the term size DOES matter.)
5. A well known theorist told me that he used to believe both P ≠ BPP and there were problems in DTIME(2^O(n)) that require circuits of size 2^&Omega(n);. Oh well.
6. Lance Fortnow tells me he has a hard time believing the Recursion Theorem. Perhaps because the proof is completely uninformative. (Ted Slaman, a well known recursion theorists, agrees that the proof is uninformative. Bob Soare thinks the proof is quite intuitive- a failed diag argument.)
7. Probability has a few of these: The Central Limit Theorem says that stuff is all normal. That can't be true! I've done the calculations for Birthday Paradox but it still seems suspect to me. And don't get me started on The Monty Hall Paradox.
8. Local Lovasz Lemma has gone from being something I didn't believe to something I now understand and believe. The original proof just looked like symbols being pushed around, but Moser's and later Moser-Tardos's constructive versions makes sense to me.
9. We all know that Godel's theorem surprised people- but were there people who did not believe it? This theorem does not surprise Generation Xers who are not at all surprised to find out certain problems cannot be solved. Their response: Whatever.
10. The existence of Geometries that are as valid as Euclidean but not Euclidean. Again, this surprised people, but were there those who did not believe it? In this age of moral relativism people have no problem with different geometries that are all valid.

How about you? Are there any theorems that you simply don't believe?

Turing Award and Waterman Award and the variety of our field

As Lance tweeted:

1. The Turing Award for 2009 was given recently to Chuck Thacker LINK. See here. He developed the first modern PC.
2. The Alan T. Waterman award was given to Subhash Khot. See here. He formulated the Unique Game Conjecture and has proven many consequences of it.

These two award recipients demonstrate the vast variety there is within computer science. I suspect that these two people, one very practical, one very theoretical, have very different mindsets. The most striking is that in theory we have PROOF as our... proof that something is true (I can't even escape using the word!). In practical things the proof is in the pudding.

There is much less variety within Mathematics. All (well... most) mathematicians have proof as their criteria of truth. They may not understand each others problems and interests but they understand the type of problems each other works on.
Physics has two campus- theorists and experimentalists. But I get the impression they talk to each other and understand each other. While this is true in some parts of computer science (crypto and bio-comp come to mind) it is also often not true. (If I am wrong about Physicists let me know.)

Consider the following statements, both probably exaggerated.

1. In a math department any professor can teach any undergraduate class.
2. In a computer science department it is NOT the case that every professor could PASS every undergraduate class.

HW policies: PROS and CONS

The last blog entry had lots of good comments about different HW policies. I enumerate them and say PROS and CONS

1. Hard Deadline. PRO- uniform, no favoritism, can post HW Solutions or go over HW in class as soon as it is handed in. CON- there could be legitimate reasons for lateness that are short of a doctors note. CON- you want the student to DO the HW even if it will be late. CON- you need to be TOUGH to say NO.
2. Moral Deadline (what I do, see last post). Same as Hard Deadline, but its a bit easier to say NO.
3. Penalty for lateness. PRO- the students will still do the HW. CON- delay in posting solution. CON- slackers are still slackers. ODDITY- the penalty is supposed to discourage lateness. But it may encourage it (gee, 10% off if I hand it in one day late. OKAY, its a deal)
4. Look at late HW only if they affect the final grade. PRO- less to look at likely, CON- Don't really want to keep track of these things. CON- student may not be discouraged from handing things in late.
5. Only count (say) 10 of the 12 HWs, and have HARD DEADLINES. PRO- same as HARD DEADLINE. CON- students will blow off 2 HW's, possibly the last two which may be important for the final. CAVEAT- raises the much bigger question of whether to treat students like adults or like ...students.
6. Students get x number of late days (this one was new to me). PRO- well defined rule, flexible but no favoritism. CON- delay in posting solutions. CON- keeping track of it.
7. If you miss a HW then the others will count more (up to some limit). PRO- uniform. CON- students may still miss some HW they should do.
8. HW are OPTIONAL. PRO- they sink or swim on their own. CON- they sink or swim on their own.

Diff topic- how much to COUNT HW? I often count it low (like 10-20 percent) so that I don't' have to worry too much about cheating. Actually I think its GOOD if students help each other but BAD if students copy each other, but it can be hard to tell.

Which of these work best? Depends alot on the school and the course and even the profs willingness to say NO.

A HW policy- MORAL due date.

This semester I am using the following HW policy.

HW is due on Tuesday. However, your dog died! Hence you get an extension to Thursday. That is, for all people in the class I assume you have a quasi-legit reason to ask for an extension to Thursday. Hence you can hand it in Thursday for full credit. However, if you want an extension past that you will not get it since I already gave you an extension to Thursday. (There may be some severe exceptions which will have to be documented.)

1. This will save alot of time in terms of students asking permission to hand it in late since I will say I already have you an extension and you are asking for another one?
2. Some students will get into the habit of handing it in Thursday. This is okay so long as they do not ask for an extension past that.
3. Clyde tells me that this is really a cheat- the HW really is due Thursday. I may have a higher moral ground when telling them they can't hand it in later than Thursday, but they will still feel that they deserve an extension if their dog dies on Wednesday. My response: they do not.
4. I do make sure that they have enough knowledge to do the HW by Tuesday.
5. I am teaching one Junior-Senior class and one honors-class so these are already pretty good students. They (I hope) know what I mean when I say that they cannot ask for an extension past Thursday. Also they will likely not need them. I have not tried this in a Freshman class. I would like to but they are usually co-taught and large so it would be harder to manage.

Special Issue of TOC in honor of Rajeev Motwani

(Guest post by Samir Khuller, Sudipto Guha, Laci Babai)

Special Issue of the journal Theory of Computing in honor of Rajeev Motwani (1962 - 2009)

Submit contributions by July 30, 2010.

Submissions in all areas of theoretical computer science will be considered, with preference for topics related to Rajeev's work. All papers undergo strict peer review and must meet the standards of Theory of Computing.

See details at http://www.cs.umd.edu/~samir/ToCMotwani.htm.

Can The Hill Cipher ever be used?

Alice and Bob want to sent a message so that even if Eve intercepts it, she cannot tell what it is. We will allow Alice and Bob a short private meeting to exchange information (or perhaps they will use RSA or Diffie-Helman for that). But the key can't be that long and has to be reusable (so one-time pad does not qualify). I describe below a well known cipher called the Hill Cipher. I think that there are circumstances where it could do well; however, I am curious what you think.

Let n be a parameter we pick later. Alice generates a random n x n matrix of elements from {0,...,25} and checks that the Det mod 26 is nonzero. (CORRECTION ADDED LATER: the Det has to have an inverse mod 26, so has to be rel prime to 26.) Alice gives this to Bob. Alice and Bob both compute its inverse. Alice and Bob can exchange messages by encoding every block of n by this matrix. So the first n letters of the text get multiplied by the matrix to get a diff n letters. Then the next n letters after that, etc.

1. n has to be small enough so that Alice and Bob don't mind exchanging n² elements of {0,...,25}
2. n has to be large enough so that going through all possible n x n matrices is not practical for Eve.
3. n has to be large enough so that tables of how often particular n-sized blocks occur are useless.
4. Can combine with other techniques. Perhaps Alice and Bob first encode using the Vigenere Cipher and then apply the Matrix. They would then have to also share the Key for the Vigenere Cipher.
5. QUESTION: If ALL Eve gets is the text then is this a good cipher? Clearly if Eve also somehow gets her hands on a message and what it was coded to she will easily crack the code. But if not then does this work well? This code is not used because Eve might get her hands on such, but I wonder if these are circumstances where it would be reasonable.
6. Is there a value of n that is both big enough and small enough (a Goldilocks n).
7. What else is known about this?

Knuth Prize for 2009: David Johnson

Dave Johnson Won the KNUTH PRIZE for 2009: click here

I can't add much to the article linked to except to say that it is well deserved.

The Wikipedia entry on the Knuth Prize does not list him yet (March 2, 2010, 4:15PM East Coast Time in America). I wonder how fast it will get updated?

CCC 2010 papers posted (I know- Old News)

As Lance tweeted, the papers for CCC 2010 are posted here.

1. The Guest Speakers look AWESOME!: Khot, Raz, Regev. Also Banquet speaker Hartmanis AWESOME!
2. Based on titles alone (not so reliable) it looks like there are no quantum papers. Someone tell me- is that really true? Even if there are some, I am sure there are not many. Has the field run its course? Doubtful. In fact, it may be the other way around--- the field has grown and their are other places for that work to appear.
3. ADVICE: Try to download some of the papers that (1) interest you AND (2) you have the prereq knowledge OR always wanted to get that knowledge. Either read them or use them to find refs to read.
4. Is there a centralized place to download them? There should be!!!!!! Other conferences manage this (SODA for one).
5. I will be at STOC and CCC. Hope to see you there!