ASK THE ALGORITHM!

How do non-theorists view algorithms? If ask.com has its way they will associate algorithms with ask.com. Or they will associate ask.com with algorithms. There latest ad campaign seems to define algorithms to be search algorithms, which is even narrower than mine!. The company ask.com is bragging that their search engine uses an algorithm! Uh- we knew that. We also know that google and yahoo use algorithms! But apparently they don't use the algorithm.

I saw a billboard a few weeks ago which said

The Algorithm killed Jeeves.

Since I am a fan of of P.G. Wodehouse's fiction revolving around Jeeves and Bertie my curiosity was aroused. It turns out that this is ask.com's way of saying that they are changing their name from ask-jeeves to ask-the-algorithm (I'm not sure this is really their new name.) This is rather odd- you are supposed to kill the compeition, not your former selves.

This is only ask.com's second stupidest ad. The stupidest one is called the unabomber hates the algorithm What does this even mean? Nowadays most people have forgotten who the Unabomber is. But even if they know who he is, is the reasoning ``if a bad guy didn't like this product, then I should.'' ?
(Thanks to Paul Beame who send me this idea for a blog.)

The Man who loved Algorithms

The May 2007 issue of IEEE SPECTRUM has on its cover the sentence

The man who loved algorithms

I was thinking that it would be an article about Donald Knuth (See also Wikipedia entry) It was not- it was about Thomas Kailath(See also Wikipedia entry.) who won the IEEE spectrum medal of Honor for

exceptional developments of powerful algorithms in the fields of communications, computing, control and signal processing

I will defer to the IEEE and assume that he has indeed done excellent work. I had never heard of this person. Some of you may have since he does have some COMP SCI publications; however, I suspect most of you have not. If not, then do we have a narrow view of algorithms? My view is narrower than most and is summed up by a quote Michael Sipser said at a Workshop on Circuit Complexity about 20 years ago:

Algorithms are sanity checks on lower bounds.

$25,000 prize for ... Univ TM

1. Mike Pilat brought this to the attention of Lance Fortnow.
2. Lance Fortnow brought it the attention of Bill Gasarch.
3. Bill Gasarch brings this to your attention.

Mike's letter to Lance:

If you haven't already heard, my employer, Stephen Wolfram (and Wolfram Research) this week announced a $25,000 prize to prove or disprove that a particular 2-state, 3-color Turing Machine is universal (i.e., Turing-complete). If proven, it would be the simplest possible UTM. The details of the prize and the Turing Machine in question are all here. I thought you and your students might find this challenge interesting.

Is this interesting? Does offering $25,000 make it interesting? INTERESTING/NOT INTERESTING THINGS ABOUT TURING MACHINES:

INTERESTING: Turing Machines and seemingly unrelated models of computation are equivalent. NOT INTERESTING: Details of those equivalences. (They were clever and interesting at the time, but not now.)

INTERESTING: There is a Universal Turing Machine. NOT INTERESTING: Finding the smallest one.

INTERESTING: Turing Machines seem to capture all things that are computable. While usually called Church's thesis or The Church-Turing Thesis, Bob Soare thinks is should be Turing's thesis. See Springer LNIM, No. 4497, Computability in Europe, or just get it here.

INTERESTING: HALT is undecidable.

INTERESTING: The Busy Beaver Function (see also this) grows faster than any computable function, and hence is not computable. NOT INTERESTING: The actual values of this function. Especially since they would be tied to a rather particular type of Turing Machine (e.g., 1-tape, 2-symbol). Is the size of the smallest UTM or the values of the Busy Beaver function interesting to know for their own sake? How does this compare to finding actual Ramsey Numbers (see Dynamic Survey on Small Ramsey Numbers) or actual VDW numbers What are the criteria of interest?

1. Are these numbers interesting in their own right. For UTM NO, mostly because it is tied to a particular machine model. For Ramsey/VDW the numbers might be useful to inform conjectures. The few known values of VDW indicate that the VDW numbers may be far lower than the bounds given by the proofs.
2. Has nice math come out of the attempt? For UTM no, For Ramsey very little- R(4) uses Field Theory.
3. Has nice computer science come out of the attempt? For UTM/R/VDW the answer is yes- clever tricks and such. But (I think) nothing that can be used outside of these problems. If I'm wrong the commenters will politely correct me.
4. Why do people climb Mount Everest? Because its there! Finding these numbers may have the same mentality; however, its much safer.

Godel Prize: Natural Proofs. My 2 cents

As several readers mentioned on my last post, the Godel Prize has been announced. The award goes to the authors of a PAPER and the paper can be a conference paper, but it must have appeared in the last 14 years. They should have made it 16 years. The 2007 winners:

Alexander Razborov and Steven Rudich

for the paper

Natural Proofs, Journal of Computing and Systems Sciences, Vol 55, No 1, 1997, pages 24-35. Goto either of their websites for the paper.

This is an excellent paper about limits on proof techniques in circuits. Its been blogged about and been described in a wikipedia entry. Very recently Sivakumar wrote a very nice short description of the concept. Has it changed how we do research? The closest analog is the Baker-Gill-Solovay results on Oracles. The contrast:

1. Baker-Gill-Solovay showed that techniques that relativize do not suffice to resolve P vs NP. All proofs in recursion theory relativize. Hence we will need more than recursion theory techniques. (Some people disagree with this intepretation. If you are one of them, leave an intelligent comment.) Impact: (1) people got papers for constructing oracles to show that recursion theoretic techniques would not suffice to resolve certain problems, even problems nobody cared about. (2) people began looking more at combinatorial techniques such as circuits since those techniques tend to not relativize. One can argue if this is really true both mathematically and historically. It is possible that the move away from recursion theory to combinatorics was going to happen anyway, or already began. History is messy and hard to put into boxes.
2. Razborov and Rudich showed that all lower bounds for circuits (except monotone circuits, for which the terms don't really make sense) ``naturalize'' and that such techniques won't suffice to solve several problems in circuits, including P vs NP, under some reasonable assumptions. There has not been a rush to show certain results naturalize. There has not been a mass movement away from circuits towards something else. But there may be at some later time, and in any case the paper is crucial for telling us what we've been doing and what its limitations are.
3. Both results seemed to hint at independence results. Neither one has lead to any such results. Rudich told me once that they were 6 months away from an independence result. 10 years later he told me they are still 6 months away UPDATE IN 2014: STEVE RUDICH TELLS ME THAT HE NEVER SAID THIS. I BELIEVE HIM.
4. ``relativize'' was a natural notion that people already knew about at the time of the BGS paper. ``naturalize'' is a less natural notion that Razborov-Rudich discovered or invented for their paper. However it was a very important notion since it captured what many proofs had in common.

Money

When I was an Undergraduate (1976-1980) the question

Would you take grant money from the dept of defense?

was in the air. There were stories of people who thought they were working on medicine who were actually working on germ warfare. There were also stories about the people who worked on the Atom Bomb (knowing what they were working on) later regretting it.

I heard this kind of discussion less in grad school (1980-1985). The last time I ever heard it brought up at all was in 1989 when a grad student asked me if I take money from dept of defense. Since I've never been offered such money it was a moot point (I've never applied for such money, but not out of any moral principle.) I recently met up with that grad student (now a professor) and he is working on a germ warfare grant.

The question of who you take money from is asked in some circles- crypto comes to mind. But how about the general question- who would you take grant money from? There are several factors that people tend to lump together, but they are different:

1. Do they let you publish and post and talk about your research (e.g., NSA, Microsoft, might not)
2. Do you have a moral objection to who the person asking you? (e.g., the military)
3. Do you have a moral objection to the type of work being asked of you? (e.g., helping an advertising company sell more cigarettes to minors. When you question this they reply `if teenagers don't smoke, what will they do after sex?')
4. Is the work of interest to you?
5. Do you have to have a product in the end?
6. @
7. Will working on this put you in actual danger? (e.g., Tony Soprano wants you do use your knowledge of resource allocation to settle a gang war.)

There are many different possibilities. Here are two extreme cases:

1. Al Queda wants to give you a grant to work on something you like, and you can publish it, and it has no possible practical value. (You can replace Al Queda by whatever you think is a great evil.)
2. Greenpeace wants to know how to best lie to the public to force them to take action on Global Warming. You can't publish, post, or talk about it. The work is boring, and you find lying morally bad. But the cause is just! (You can replace Greenpeace and Global Warming with some other organization and cause that you agree with and think is very important.)

FCRC- deadline for late registration FRIDAY

The DEADLINE for registering for FCRC without paying a late fee is FRIDAY! However,

1. If you want to help the organizers in terms of allowing them to PLAN better, then register BEFORE the deadline.
2. If you want to help the organizes in terms of how much MONEY the conference makes then register AFTER the deadline.
3. To help them out in BOTH ways register ASAP after the deadline.

~

Believing an open problem has been closed

Frederic Green posted the following comment a while back:

Have you heard any buzz from your mathematical collegues on the alleged disproof of the Riemann Hypothesis.

Later comments indicated that the mathematician was not that good. When should you believe a math announcement? Which of the following would you believe? Would you bother downloading the paper?

1. Karp claims to have shown P = NP. P \ne NP.
2. Shelah claims to have shown P=NP. P\ne NP.
3. Widgerson claims to have shown P=BPP. P\ne BPP.
4. Bill Gates claims his group has shown P=NP and the binaries are available but not the source code.
5. The Free Software Foundation claims to have shown P=NP and of course the source code is available.
6. An undergraduate math major who is really sharp claims to have solved the the Collatz Conjecture) (also called the 3x+1 conjecture).

Whether to believe a claim is based on several variables.

1. G: How good is the person who claims to have solved it. Hard to measure. (number of STOC/FOCS papers :-) ) For someone new this might be even harder to access.
2. B: How believable is the result? We'd believe P\ne NP more than P=NP. But we may believe that if a proof was found now it would be that P=NP. I've heard that Riemann Hypothesis will probably be solved in the next 50 years.
3. H: How hard is the problem?
4. W: How good is the writeup? Is there one?
5. If the problem is outside of your area then you may have to take other people's word for some of G,B,H, or W. How good are the people telling you about the problem? This may lead to a recursive formula.

Green's Conjecture: There is a constant C such that

If G*B*W/H > C then the result is worth looking into.

If you claimed to prove Green's Conjecture then I could use Green's Conjecture to to see if your proof is worth downloading.

Coda to idiot-post

Coda to idiot.

1. The posting idiot was a test case for the newly-fixed mechanism to email posts to people (some people had been getting this blog via email instead of going to the web.) It did not work. Nobody knows why.
2. I had written:

   computers have gotten VDW(4,2) more complicated.

   One of the comments was:

   For the "Ramsey-theory idiots" out there, the technical translation of VDW(4,2) is "I don't know exactly how much more complicated computers have gotten, but its a while hell of a lot!" :-)

   The commenter is correct in clarifying what I meant; however, both the commentator and I are incorrect in the details. Inspired by the commenter, I looked up what is known about the VDW numbers. VDW(4,2) is known and is only 35. VDW(5,2) is known, and is only 178. I should have written VDW(5,5) which is unknown but quite likely quite large.
3. VDW(k,c) is the least number W such that no matter how you c-color the elements {1,2,...,W} there will be k numbers equally spaced (e.g., 3,7,11,15 is 4 numbers equally spaced) that are the same color. W(k,c) exists by van der Waerden's Theorem. See van der Waerden's Theorem-Wikipedia or van der Waerden's theorem-my posting in Luca's blog
4. I believe the only VDW numbers that are known are as follows: (see this paper) by Landman, Robertson, Culver from 2005.
   1. VDW(3,2)=9, (easy)
   2. VDW(3,3)=27, (Chvátal, 1970, math review entry, article not online.
   3. VDW(3,4)=76, (Brown, Some new van der Warden numbers (prelim report), Notices of the AMS, Vol 21, (1974), A-432. Article, review not online!
   4. VDW(4,2)=35, Chvátal ref above
   5. VDW(5,2)=178, Stevens and Shantarum, 1978 full article!

Idiot

CSP stands for COMPUTER SAVY PERSON. 25 years ago the following happened:

BILL: I can't get my computer to work.
CSP: Just push this button you idiot.
BILL: Thanks! That works!

15 years ago the following happened:

BILL: My awk program did not compile and in trying to find the error I found an example from the awk manual which did not compile.
CSP: Just use gawk instead of awk you idiot.
BILL: Thanks! That works! I don't think its idiotic to not know to use gawk.

5 years ago the following happened often:

BILL: My FILL-IN-SOFTWARE is not working, whats the problem?
CSP: We can find a work-around, but, by Rice's theorem, we can't find out what the problem really is.
BILL: Thanks!

Recently the following happened.

BILL: When I play a song on You-Tube I'm not getting sound.
CSP: That will take a few hours to fix. We need to INSERT TECHNO BABBLE.

When they were done sound worked, but many other things did not. And there were some things which I would call odd except that computers doing odd things is not odd. I fired up FIREFOX and a short time later OPEN OFFICE opened mysterious. There was a debate on this.

CSP1: I think FIREFOX is somehow linked to OPEN OFFICE.
CSP2: I think some weird combination of keys caused it.
BILL: Did I do something idiotic like accidentally click on some icon (this turned out to not be the case).

In the good old days computers were simpler. The staff would tell me I was an idiot and fix the problem! The staff now is 10 times better then they were then, 100 times more polite, but computers have gotten VDW(4,2) more complicated.

I miss being an idiot.

Meta Comment on FOCS/STOC comments

The comments on both Vijay's guest post and Lance's post brought out many comments about FOCS/STOC. People seem to have strong feelings and stronger opinions. Here is a list of questions this discussion has raised.

1. Is the community really driven by these conferences? An Underlying assumption of these discussions has been that someone judges us based on the number of STOC/FOCSs we have. Who is this mysterious someone? Is it our departments? Our Colleges? Ourselves? Granting agencies?
2. Is it bad that we are so judged?? PRO: Its good to have a central place where you know the good papers are. CON: The rest of the items on this list are about what problems there are in judging quality CON: Some of these papers are never put into proper journal form. CAVEAT: Is the Journal-Refereeing system all that good to decry that it is lacking here?
3. Other fields do not have high-prestige conferences- why do we and is it a good thing?. Our field moves fast so we want to get results out fast. It is not clear that FOCS/STOC really do this. Using the web and/or Blogs can get the word out. Important new results in theory get around without benefit of conferences. For results just below that threshold its harder to say.
4. Are the papers mostly good?
5. Is their a Name-School-bias? Is their a Name-person-bias? Some have suggested anonymous submissions to cure this problem.
6. Is their an area-bias? There are several questions here: (1) is the list-of-topics on the conference annoucement leaving off important parts of theory? (2) is the committee even obeying the list as is? (3) have some areas just stopped submitting?
7. Is their a Hot-area-bias?
8. Is their a mafia that controls which topics gets in?
9. Is their a bias towards people who can sell themselves better? To people that can write well?
10. Is their a bias towards making progress on old problems rather than starting work on new problems?
11. Is their a bias towards novel or hard techniques?
12. Is it just Random? Aside from the clearly good and clearly bad papers, is it random? Is even determining clearly good and clearly bad also random? One suggestion is to make it pseudo-random by using the NW-type generators. This solves the problem in that since it really is random it is less prestigous and most of the problems on this list go away. Would also save time and effort since you would not need a program committee.
13. Are there many very good papers that do not get in? It has been suggested that we go to double sessions so that more get in. If the quality of papers has been going up over time this might make sense and would not dilute quality.
14. Is 10 pages too short for submissions? This was part of Vijay's Video Suggestion. Are figures and diagrams counted for those 10 pages? If they are they shouldn't be.
15. Are many submissions written at the last minute and hence badly written?
16. Are many submissions written by the authors taking whatever they have by the deadline and shoving it into a paper?
17. Since the conference is about all of theory, can any committee do a good job?Vijay was partially addressing this problem by trying to find a way to make their job easier.
18. Do other conferences have these problems? That is, the more specialized conferences- do they have similar problems? Why or why not?
19. Do you actually get that much out of the talks? If not then it is still valuable to to go for the people you meet in the hallways?
20. For all the items above, even if true, are they bad? Some have suggested that bias towards big-names is okay.

Any proposed change in STOC/FOCS (or other conferences) should have the following:

1. State clearly what problem you are trying to solve. If it is a new problem there may be a bias against it.
2. Prove that it really is a problem. The proof has to use novel or difficult techniques.
3. State clearly what your solution is and proof that it works. The proof can be a sketch; however, if you are a big-name or from a big-name-school then people will pay more attention.
4. Comments to your suggestion must stay on topic. A referees report would never say: `The author showed that 3-colorability can be approximated well; however, the really important problem in this field is set cover, which can be shown to not be approximated by the following.'' But a comment on a blog often says things like: ``Vijay is addressing one problem with STOC/FOCS, but the real problem is ...''

Radical change to Conferences by Vijay Vazirani

(Guest Post by Vijay Vazirani!)

The processes of submitting FOCS/STOC abstracts and conducting PC meetings have undergone numerous changes since the good old days when you received your acceptance letter by US Mail and a couple of weeks later you received a huge rolled-up bunch of poster-sized papers on which you were supposed to glue your paper and mail back. There is little doubt that these changes have improved efficiency and fairness a great deal.

I would like to propose another, somewhat more radical, change that is now technologically feasible -- allowing people to submit, together with their 10 page abstract, a 10 (or 20?) minute video describing their result. The video will be optional, at least in the beginning.

They say a picture is worth a thousand words -- if so, a 10 minute video is worth millions! Imagine, as a PC member, how much easier it will be to read an abstract after you see a short video explaining the problem, the approach, and the main new ideas, and how much more "correct" your evaluation of the paper would be! In my opinion, this will greatly improve quality of the paper acceptance process. Many people complain that the latter is currently broken -- a large fraction of the decisions are nothing more than the flip of a coin or are left to such chance events as who reviews the paper or the constitution of the PC.

Many objections can be raised to this idea. Let me anticipate a couple and try to counter them. First, this change is feasible today -- if you need proof, just take a look at YouTube! Another objection is that this may give an advantage to some members of TCS community -- those who can give better talks. But then, they are precisely the people who are also better at writing clearly and already had a huge advantage. In fact, in my opinion, relatively speaking, the enhanced process will be a great equalizer -- giving a chance to people who don't have good writing skills to still be able to sell their wares.

Needless to say, this is a major change and it deserves an extensive discussion before it is implemented. I hope this blog will provide that opportunity.

Getting an 8-year old interested in math:Do's and Don'ts

I recently visited my nephew and his five kids and tried to get my 8-year-old great nephew Justin interested in some math. I told him that I am thinking of a number between 1 and 100, and he should ask YES/NO questions until he guessed it. Try to ask as few questions as possible. His first three questions were as follows.

• Is it bigger than 20? (YES)
• Is it even? (YES)
• Does it have a 7 in it? (NO)
• Is it 80? (NO)

It took him 20 more questions to get it. I bet him a quarter I could get his number with 10 questions. I succeeded and he had to beg his dad for a quarter. I've been told he has learned not to gamble with Uncle Bill. His father told me that the concept of `try to make every question cut the number of possibilities in half' was over his head since he has not learned fractions yet.

I then tried NIM-games. There are toothpicks on the table and you can remove 1 or 2. The players alternate. The player who removes the last toothpick WINS. He played his sister Jordan (who is nine) with different numbers of toothpicks on the table. They DID catch on that if the number of toothpicks is 3,6,9,12, ... like that, then Player II wins, otherwise Player I wins. They then did NIM with removing 1 or 2 or 3 and also 1 or 2 or 3 or 4, They learned the trick and the pattern. They liked it and learned some math.

I do not know if this is indicative, but it may well be that if a kid has not learned fractions yet, binary search may be over his head, while NIM games is fine and fun.

Warning: I once tried to teach my 6-year old nephew Michael that, when doing multiplication, the order does not matter.

BILL: Say you had two pans of brownies. One is 3 by 5 and the other is 5 by 3. Then---

MICHAEL: Do you! I love brownies!

We didn't get much math done ...

Knuth Prize goes to Nancy Lynch

The Knuth Prize for 2007 was announced: Nancy Lynch. The formal announcement is here. The Knuth Prize is awarded for a lifetime of work in the foundations of computer science. This is in contrast to awards that are for one work (e.g., best paper at STOC). A best paper award can look silly 10 years later; however, a lifetime-of-work award has much less chance of that. The Knuth Prize is $5000 plus $1000 travel expenses to go pick it up. Do they make you fill out forms and give them your receipts? This is a small amount of money as prize money goes. The Knuth Prize is given out every 1.5 years, so saying that Nancy Lynch is the `2007 winner' isn't quite right. Donald Knuth has never won the Knuth Prize, though he certainly should. Is he eligible? Previous winners are below. Impressive bunch!

1. 1996: Andrew Yao
2. 1997: Leslie Valiant
3. 1999: Laszlo Lovasz
4. 2000: Jeffrey Ullman
5. 2002: Christos Papadimitriou
6. 2003: Miklos Ajtai
7. 2005: Mihalis Yannakakis

Complexity 2007- BE THERE!

The website for Complexity 2007 is up now (its been up for while) CCC08. In 2007 it is part of FCRC, a set of conference including STOC. Should you go? YES if you can. Should you also go to STOC or part of STOC. YES if you can. Advice:

1. Register and book hotel early and try to stay in the conference hotel.
2. Air travel: There used to be some rules-of-thumb like `fly over a weekend for a better price' or `book early or `book late' or `fly airline XXX' or ... None of these seem to be consistent anymore. One rule-of0thumb- if you see a good price grab it since it may go away.
3. DO NOT CHECK BAGGAGE. Saves time on both ends and saves the time and hassle when they lose it.
4. Look at the program ahead of time and download and read some of the papers ahead of time. This way you can follow those talks pretty well. (Papers likely on authors websites or EEEC but not necc.)
5. Bring a notebook and a clipboard OR a labtop so that you can take notes on talks and things you hear in the hallways.
6. Its a cliche to say `you learn more from talking to people in the halls then at the talks' While you certainly learn alot this way, the talks are also valuable. Not so much because you will learn the latest results and their proofs, but so that you'll know whats out there.
7. How many talks to go to? Going to all of them is tiring and leaves less hall-time. Pick talks that you already have some very basic knowledge of OR want to get into. IF you are looking for things to work on, go to more talks. If your plate is already full, go to less talks.
8. The following is typical and should not be underated: You only understand the first 3 minutes of a talk BUT you get awareness of a new area and some references to look at.
9. When you get home follow up on the topics that peaked your interest.

What to make of the Ind of CH ?

Dave Barrington suggested I blog about Paul Cohen since he just died. Scotts Blog already reported on Paul Cohen's death, and there were many comments on C^* algebras and PAC learning (none of which Paul Cohen worked on). Paul Cohen's most important result was that CH is independent of ZFC. What does this mean and what do we make of it? CH is the statement there is no cardinality strictly between N and R ZFC is Zermelo-Frankl Set Theory (with the Axiom of Choice). Virtually all of Math can be derived from these axioms. (There are quibbles about this which might be a latter blog.) Kurt Godel showed that there is a model of ZFC where CH is TRUE. Paul Cohen showed that there is a model of ZFC where CH is FALSE. Together we have that CH is INDEPENDENT OF ZFC. What to make of this? Here are opinions I have heard over the years:

1. (Mathematical Realism or Platonist) There IS a model of the reals that is the RIGHT one.In that model CH is either true of false. ZFC just isn't up to the task of figuring it out.Paul Cohen thought that there were an INFINITE number of cardinalities between N and R.I've heard rumors that Kurt Godel thought there was exactly ONE cardinality between N and R.Hugh Woodin has some mathematical reasons to think there is exactly ONE:CHone CHtwo. Many people prefer the simplicity of having NONE---the infinity after N is R. Some people think that we need to add new axioms to ZFC such as Large Cardinals or the Axiom of Determinacy to settle the question. Are these really candidates for axioms?That may be a later post.
2. (Not sure what these people are called.) Since ZFC settles virtually everything else in mathbut not this question, CH has no answer. There is No `correct' copy of the reals.The weakness in this response may be the virtually. Are there questions in math that need it? Are there such questions outside of Set Theory? That may be a later post.

What do you think? ~

The Complexity Blog Lives!

Various people have urged Lance to keep the Blog going, perhaps under new management. Some have suggested Bill Gasarch (me) . Some have suggested anyone except Bill Gasarch. Lance flipped a coin and it came up with anyone but bill gasarch . However, not one to leave things to random chance, Lance offered me to take it over, and I accepted.

PROS: The blog will live!
CONS: It will have far more capital letters.
CONS: Fewer postings, probably twice a week. But that how Lance started.

I am honored to carry on the tradition, and will have my first real post next week. bill gasarch

The End

After 4 1/2 years and 958 posts I have decided to retire from blogging. No weblog can go on forever and I would rather end on my own terms than let the blog peter out.

Thanks for reading.

Turtles

Today a new Teenage Mutant Ninja Turtles movie opens. The turtles were quite popular back in the late 80's and early 90's, somehow making appearance in more than a couple STOC and FOCS talks. Seemed the rule to avoid popular culture in talks doesn't apply to children's shows.

Then the turtles started winning NSF Math Postdocs: Michelangelo (Grigni), Raphael (Ostrovsky) and Leonardo (Schulman). Poor Donatello never did get his postdoc.

Laws, Taxes and Computer Science

So if I get a number of P=NP and P≠NP "proofs" what do the law professors get? A long email argument that most income tax is illegal. I'll spare you the full email (but if you are really curious here is the website).

How do I know about the email to our law faculty? Because the message was cc'd to the CS faculty because of the following line:

I know that some people aren't comfortable using a computer. If you need help with a computer to search the tax code (US Code, and Code of Federal Regulations), perhaps one of the computer science faculty can assist you.

I don't hold much credence in his legal arguments but I know for sure he has no clue about computer science.

FCRC: Registration, Visas and Hockey

The Federated Computing Research Conference (FCRC) has opened registration and housing. FCRC, held June 8-16 in San Diego, is a mega-conference including STOC, Complexity, COLT, Electronic Commerce (EC), SPAA, and a few non-theory conferences as well.

Early registration deadline for the conference is May 11 and the hotel rooms are being held until May 9. It's recommended to make the hotel reservations as early as possible.

For registration, you pay a single fixed FCRC Fee and then a separate registration for every conference you attend. You are allowed to attend talks in any conference held during the same day you are registered for some conference. Tutorials and workshops are closed, though we are trying to open up the EC workshops.

If you need a visa, read this and apply now. The US visa process can take months.

Catherine McGeoch, the self-proclaimed ToC Hockey Commissioner, tells us the theory community has been challenged.

The computer architecture community (which attends ISCA) has challenged the theoretical computer science community to a "friendly inter-league" hockey game, to take place during FCRC. They will make local arrangements — we just have to get up a team.

If you are attending FCRC, and can pass as a theoretician (and/or as a hockey player), you are hereby invited to sign up for the now-forming ToC Hockey team. Tell all your friends to sign up, too.

I remember long ago in graduate school playing (badly) for the MIT theory group's intramural team, Execution Time. Now I can't even keep up with my eight-year old daughter.