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!

Is Math too hard?

Are humans good at Math?

In the movie Oh God Book II God (played by George Burns) says that Math was a mistake, I made it too hard!. While I am reluctant to contradict God, George Burns, or God as portrayed by George Burns, scientists have found evidence that people are pretty good at math. At least people have known about numbers for a far longer time than previously thought. See this article. What does this mean for us? The next time one of your students says I can't do this! I'm just not that good at math! you can tell them that this is just not true.

An Aside: Before posting this I wanted to verify that that quote really was in that movie. I would have thought it would be a quote that math people, or people who think math is hard, or math people who know math is hard, would remember. When I googled it all I could find was a comment on this blog entry of Scott's by Bill Gasarch. Not what I would call a confirmation. It may be that my quote is not quite exact. If anyone knows for sure (e.g., has the DVD and checks it) let me know.

Doing it OLD SCHOOL!

If you browse the Univ of MD Schedule Web pages for the last few years I would:

1. Ask you why you were doing that. Seems like an odd use of your time.
2. Point out to you that Automata Theory which usually gets around 8 people got 23 (it competes with crypto as noted a few blog entries ago).

Why the uptick? Did we use email? blogs? a websites? twitter? FACEBOOK? eBay? None of the above. We had tried some of those in the past to NO effect. We did it Old School! I went around to the classes that feed into Automata Theory and TALKED about them for 5 minutes each around registration time. And the talks were off-the-cuff. No PowerPoint, no fireworks, no technicolor show with an intermission. Also we told advisers to be on the lookout for people who might want to take it and tell them while advising.

1. I had a prior post on why email is less effective then is used to be (I can't find the post- if you know where it is let me know.) To summarize from memory- people get too much email and some goes to SPAM filters or can be claimed to have.
2. (A colleague of mine suggested this.) If I just EMAIL about a class, I have not spend much effort and the students sense that. If I go out of my way to talk about the class then the students think that I care.
3. There are some other explanations for some of the uptick: Comp Sci enrollment is up (might account for 4 students) and by a fluke we have 2 grad students taking the course (which accounts for 2 students). But going from 12 in Spring 2009 to 24 in Spring 2010 is alot. (It was taught be people who are thought us as good teachers both times.)

The point is, if you want something to get attention locally do it old-school! Or at least do it old-school in conjunction with high-tech.

What is in MY automata theory course/What should be

In the last post I pondered what was more important: Automata Theory or Crypto. This raises the question of what should be in a course in automata theory. Rather than discuss that I will tell you what is in mine and see what you think. (ADDED LATER: YOUR COMMENTS HAVE MADE ME RETHING THINGS. I WILL ADD MINMIZING DFA'S TO THE COURSE THIS SEMESTER. I AM JUST FINISHING UP REG STUFF SO I CAN DO IT NOW.)

The standard topics are:

1. Regular Languages: DFA's, NFA's, Reg Expressions.
2. PDA's, CFL's.
3. Turing Machines, computable and c.e. sets.
4. NPC

The following make this course a bit different than others, though not much. All the thing listed below that I claim I WON"T do are definite- I WON"T do them. All the things that I claim I WILL do are less definite I can't do all of them. I'll see how it goes and which ones I will do.

1. Decidability of Weak Second Order with S and ≤. The language has quantifiers that range over finite sets, quantifiers that range over natural numbers, and symbols for Successor and ≤. The proof uses Reg Languages. We do it in the Reg Language section and then revisit it when we do decidability. At that point I will also tell them (but not prove) about some theories that are undecidable. We also do decidability of Presburger arithmetic (quantify over naturals, have + and ≤) which follows from decidability of WS1S easily. Will also talk about decidability of S1S and omega-automta, but not prove anything. This did not take up too much time because I presented alot of it as more examples of regular languages. This material is not in any textbook that I know of, however see pages 8-28 of this PhD thesis.
2. I am NOT going to do the algorithm for MINIMIZING a DFA.
3. I am NOT going to do Context-Sensitive Languages.
4. I am NOT going to have them prove things that are obvious, like that S-->aSb, S-->emptystring generates {aⁿbⁿ}. Generally I am against having students prove things that are obvious.
5. I am NOT going to have them ever program a Turing Machine. I will tell them they can do everything and rarely refer to them ever again. I DO need the definition so that I can prove Cook's theorem.
6. I am NOT going to to Primitive Recursive functions.
7. In the NPC section I WILL DO the protocol for, in our language, NGI (non-Graph-Isom) is in AM.
8. In the NPC section I WILL DO the protocol for, in our language, given bit-commit, 3-COL is in ZK. (I may to other ZK protocols as well.)
9. In the NPC section will do that Vertex Cover with FIXED k is in O(n²) (I know that better is known.) Why? Because this is a very good example of an obvious thing (can't do better than roughly O(n^k)) being WRONG. Shows the NEED to prove things.
10. Might do NSPACE(n) closed under Complementation. Might not- this may be conventionally difficult for this audience. And we really wont' be talking about space anyway.
11. Let SUBSEQ(L) be the set of a subsequence of L. I will, throughout the year, do the following: Show that if L is regular than SUBSEQ(L) is regular, Show that if L is context free than SUBSEQ(L) is context free, Show that if L is c.e. than SUBSEQ(L) is c.e. All of this leads to material I discussed in this old post. I WILL NOT prove that if L is ANY language then SUBSEQ(L) is regular, but I may talk about it.

What is more importantt: Automata Theory or Crypto?

The way the requirements are set up at Univ of MD at College Park, without getting into details, has set up a competition between Crypto and Automata Theory That is, a student might take one or the other, but taking both does not serve her well for the requirements. Hence the students get to decide which one is more important, Crypto or Automata Theory. We did not plan it this way, it just happened. Automata Theory is Reg Languages, CFG/PDA, Computability theory, NPC. (A later post will expand on this since I am teaching it this semester.)

1. The students overwhelmingly take crypto. One year 150 students took Crypto (one section of 50 in the fall, two sections of 50 each in the spring) and 8 students took automata theory. Both courses are always taught by people who are regarded as good teachers, so that is not the issues.
2. I tend to think that Automata Theory is more important, but I may be biased. I also think that Automata Theory can be understood pretty well, whereas to understand crypto you really need to understand some Number Theory and even some security. Hence it is a strange stand-alone course.
3. Some students think that the crypto course will get them a job. A course in security may get them a job, but just crypto I kind of doubt.
4. Since more students choose Crypto we offer it more often. Since we offer it more often more students take it. (I exaggerate the circularity.) Also, its cross listed with Math so some math majors take it. This may account for some of the difference but not even close to all of it.
5. So, how does your school do this? In particular, do you let the students tell you what course is more important, or do you tell them? Is it bad if they tell us? YES if we end up with courses on twitter, NO if the students are more aware of what is important then we old academics are.

A problem about Graph Partitions (guest post)

(Guest post from Richard Taylor who requests information on a problem.)

The following graph partition problem arises in connection with studies I am doing on a particular dynamical systems problem. I wonder if there are any complexity results on it. Given a 3-regular graph, can the vertex set be partitioned into 2 sets in such a way that the induced subgraphs formed each have vertices of degree at least 2? Could this be NP complete? There are a few results on vertex partitions I have found in the literature - but none quite like this.

First Request from Bill G: In the past I have posted on problems and have had comments tell me that its well known or falls out easily from some theory, but then not give me a reference or proof sketch. Please, if you are going to say its known, give a reference or proof sketch.

Kurt Mehlhorn to receive EATCS award

Kurt Mehlhorn will receive EATCS award! Read about it here.

He has had a LONG and PRODUCTIVE career with many EXCELLENT papers. While he is mostly known for data structures and algorithms and Comp Geom, he did do some complexity theory early on. Here is a list of his papers up to 2007. Note that the first few are in complexity theory.

People in TCS can change fields easier than math since there is less background to learn. At least that was true at one time. I think it is harder to switch fields in Comp Sci now then it was then since now we know more.

e to the pi vs pi to the e

(ANSWER to Trivia Questions from Last Post: The last president who became president NOT by being VP and having the prez die, but then did not run again, was Rutherford B. Hayes. Hayes and Obama are the only presidents who have law degrees from Harvard. For more on both of these questions see this excerpt from my Prez Trivia Quiz.)

When I was 12 my school got a very primitive computer. The teacher asked me what I wanted it to do for me. I said

I want to know whats bigger e^π or π^e.

I typed both of them in, but I forgot the order I typed them in so I didn't find out. I didn't try again because I realized that even if I found out the answer it would not tell me a reason for the answer.

I had forgotten all about it until last week when I got a review of the book When Least is Best (book by Paul Nahim, review by Yannis Haralambous) in my capacity of SIGACT NEWS book review editor. Here is a quote from the review:

Imagine you are stranded on a desert island (without logarithm tables or computers) and--- probably due to an emotional shock---your only concern is to find out which one among numbers π^e and e^π is bigger. The solution is: take h(x)=ln(x)/x, take the derivative twice to prove that x=e is a maximum, and that gives e^π is bigger.

I am sure this is well known; however, since I didn't know it until last week I hope this will enlighten some of my readers.

Prediction on Presidents Day

Its PRESIDENT"S DAY so I have two predictions: One about the election of 2012 and one about P vs NP.

ON P VS NP: I have one prediction about P vs NP. It is not about when it will be solved (though I think this will be a long time). Look at the separation NC¹ ≠ AC₀. This was NOT achieved by taking a problem complete for NC¹ (the word problem for S₅) and showing it is not in AC₀. Instead a different problem in NC¹, PARITY, was shown to not be in AC₀ (CHECK- is it known that PARITY is NOT complete for NC¹? I think so - PARITY can be done in width 2 , poly sized BP and NC is equivlaent to width 5 poly sized, is probably the main part of the proof.)

I predict that P ≠ NP will be proven by showing some problem that is in NP but NOT NPC is not in P. The NPC problems seem to be hard to prove things about. Hence a problem in NP but not NPC may be better. Factoring is a candidate for this. Graph Isom may also be a candidate--- its like PARITY in that its very delicate. But it may very well be in P.

ON THE ELECTION OF 2012. For the Prez election of 2008 I predicted, before the primaries, that the candidates would be Barak Obama and John McCain, and that Barak Obama would win. I never blogged about it so my readers may be skeptical that I made such a prediction. Hence I will, today, predict the nominess for 2012: Barack Obama and Mitt Romney.

Barack Obama is obvious- TRIVIA- The last president to decline to run for a second term was LBJ. Note that he originally got to be Prez because he was VP when JFK died. The one before that was Harry Truman. Note that he originally got to be Prez because he was VP when FDR died. Who was the last president who obtained office NOT be being VP when the Prez died, who did not run for a second term? MORE TRIVIA:Call this prez X. Give a non-trivial trivia question for which the answer is Barack Obama and X. (I will answer these at the beginning of my next post.)

Mitt Romney- The republicans tend to give the nomination to someone familiar to them. Like the guy who came in second last time. Palin is also familiar to them, and she may run in the primaries, but I do not think she will get the nomination.

I also predict that Obama will win.

FOCS 2010 CALL FOR PAPERS is out!

(Univ of MD at College Park had Monday, Tuesday, Wed, Thursday all off. I've spend most of that time shoveling snow, so I am tired. Hence I am glad to have a SHORT post today- easier on the hands and arms.)

ADDED LATER-- I won't post Friday - instead I will add to this post. Note that there is NO PAGE LIMIT for FOCS submission! Is this a new policy? Have other conferences done this? It makes sense with e-proceedings to have no page limit for FINAL versions, but for Submissions. Might be hard on the committee and the sub-referees. PRO- people can include complete proofs and may be expected to. This will lead to better quality submission and less chance of error. CON- if you are restricted to 10 pages you are forced to make your point and shut up. PRO- Your submission and your final version and your journal version can be similar so less hassle changing formats. What do you think?

FOCS 2010 call for papers is out. Where is the link? You just read it! I did? Third Base!

Most important byte of info: April 7 is submission deadline. If a student said that he was sick and had a doctors note, you would likely give him an extension for a deadline. For FOCS, if a potential submitter tells the program chair that he is sick, I doubt he'll get an extension.

IF you had your paper rejected from STOC then should you submit to FOCS? It would be nice (though hard to really do) if the reports from STOC said Even though the paper was turned down, it was one of those papers which could have gone either way, so it could get into FOCS or XXX. or Your paper is not worthy of STOC or FOCS or XXX.

I am writing THIS before I actually post (duh). Right now if you type FOCS 2010 into Google, Our FOCS conference is the SECOND entry. Here is hoping that this post will boost it to the top.

STOC and More

The Snows of Maryland are keeping Bill away from this blog again. Here in Chicago we deal with snow (and even earthquakes) in stride--my kids still have yet to have a snow day this year.

So I'm back for a day to bring you some news.

The STOC accepted papers list is up, Shiva Kintali is collecting PDF pointers and Noam Nisan pulls out the AGT papers. Lots of goodies this year. You can change base without losing space (love that rhyming title), save space with algebrization and adding quantum to interactive proofs keeps it in PSPACE. 

You just don't see a lot of BLANK is computable results in STOC these days so nice to see a paper with BLANK=HOM=Is a given homomorphism of a regular language expressed by a tree automata itself regular? Sound technical but it actually has connections to XML.

So come to the conference. As Bill mentioned earlier, there are travel awards available for needy students even if you don't have a paper. Apply for visas if needed as soon as possible (click here if you need a letter). The Complexity and EC conferences will both be held also in Cambridge immediately following STOC.

The other big news, according to the Center for Computational Intractability, theory's own Subhash Khot wins the 2010 NSF Waterman award. The NSF gives away only one of these awards each year to a young researcher across all of science.

We are entering CS award season so keep an eye out for the Knuth Prize (the Knuth Prize Lecture will be at STOC), the EATCS award and Gödel Prize (presented at ICALP), Turing and other ACM awards. The SIGACT Distinguished Service award nominations are still open until March 1st which will also be presented at STOC.