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!