Opening Day

Fresh back from my Israel trip, still slightly jet lagged, and several hundred emails await me. Hold on, I will get to yours soon.

A new quarter starts today at Northwestern and with it a new course, teaching C++ to young undergraduates. Poor kids.

As of today, I now officially have a teenage daughter and will continue to have at least one teenage daughter for the next 10 years, 2 months and 3 days. Not that I'm counting.

But most importantly, just fifteen minutes after my class today, the White Sox take the field in Cleveland for their first official game of the 2008 season. Baseball is back and all is good in the world.

Univ of MD Grad Student Visit Day

Today was UNIV OF MD GRAD VISIT DAY for computer science grad students. We invited the students who got into UNIV OF MD Grad School in Computer Science for a free lunch and some talks about he program and such, in the hopes that they will come.

1. This is a relatively new concept for most schools. When I was applying to grad schools I do not think any school did it. Now many of them do. And now we all have to do it because everyone else does it.
2. Does it work? Depends on what `works' means. Students do get more information and hence can make a better choice. Whether this is good or bad for UNIV OF MD or any particular school is hard to say.
3. I am happy with the lack of propogandizing we do. We present Maryland honestly. Also, the prospective students get to talk to the students already here to get a true picture.
4. Many of the students who come to the Visit Day have already decided to come to UNIV OF MD so they are just here for the free lunch. I even met one today who already decided NOT to come and was here for the free lunch. Its a good lunch, but not that good.
5. On a related note--- many more students now have done research as a ugrad then when I went to school (I got my ugrad degree from SUNY Stonybrook in spring 1980.) The good thing about this is that if a student says, for example, I want to work in AI they have a better idea of what that means then they used to.

~ ~ ~

Complexity Conf 2008 - CCC08- You can now REGISTER!

You can now register for Conference on Computational Complexity, 2008 which will be in College Park Maryland. Go here to register and also find out more about the conference.

Lance and I will both be there.

If you have never met me and want to say high, I read your blog and I think it is XXX where XXX is any adjective you want, then you can recognize me by either this old picture of me or this more recent picture of me. However, since I am one of the local organizers you may just see a blur as I run this way and that getting things organized.

If you have never met Lance and want to say high, I read your blog and I think it is XXX then you can recongize him by either this, this, or this . I think the last picture captures the true Lance Fortnow.

An odd way to find good employees- it might work

I recently got the following email. It is not spam in that it is a legitimate company asking a fair question and it has only gone to a select group of people. However, a very similar email may have gone to other select groups of people, perhaps millions of select groups of people. Italics are mine.

I found your name while researching scholars who have served as teaching fellows under Professor Harry Lewis at Harvard. The D. E. Shaw group is currently looking to hire a small number of truly gifted individuals with outstanding backgrounds in math, physics, computer science, and other technical fields. As an organization, the D. E. Shaw group goes to extraordinary lengths to identify such candidates and introduce them to the firm. Based on your work as a teaching fellow in one of the most challenging CS courses at Harvard, you seem to be especially well-placed to help us find people with strong academic backgrounds whose areas of specialization might be particularly relevant to the work we do. Do you have any students or colleagues who stand out in your mind as possessing unusual raw ability even among a relatively gifted population of peers? If so, we would be enormously grateful if you'd bring them to our attention. If you yourself might be inclined to explore opportunities with us, I encourage you to send us a copy of your resume.

So, this person researches scholars who have served as teaching fellows under Professor Harry Lewis. How many people do research on that? Do they have their own Journal?

The sender did get one thing right and one thing weird. RIGHT: I was Harry Lewis's TA for Automata Theory in Fall 1981 and Fall 1984. WEIRD: The course was challenging for the students, but I doubt it was one of the most challenging CS courses at Harvard. Actually, I doubt that phrase even makes sense- for me Automata Theory was easy and programming courses were hard, and others felt the opposite.
Harry Lewis has on his website a list of all the people who ever TAed for him, which is where the sender got my name (other TAs of Harry Lewis, some further back than myself, have gotten the same email).
So, why did D.E. Shaw choose this group of people to send the email to? Harry Lewis has no connection to the company, so thats not it.

1. They believe, rightly or wrongly, that ugrads at Harvard who get to TA courses must be pretty good, and grad students who go to Harvard must be pretty good. But see next item.
2. They did not say that they want me to apply. They think I might know people that should apply. At the end of the letter they have an after-thought-type-statement saying essentially, `oh, and you too, I guess'
3. The list of Harry Lewis TA's is available! I also TAed for Michael Rabin, Gerald Sacks, and Leslie Valiant, but they don't have lists of their TAs on their websites. Hence people who do research on (say) scholars who have served as teaching fellows under Michael Rabin or the others have a much harder time.

Deadline Extension for NSF Theoretical Foundations Grant Proposals

(Guest post from Richard Beigel, NSF Theory Director, paraphrased. Any bad spelling or grammar you can attribute to me.)

Because of questions about the deadline in the Theoretical Foundations (TF) 2008 solication, the Theory of Computing program will accept revised Project Descriptions via Fastlane until 11:59pm EDT March 31, 2008. I cannot speak for other program directors. If your proposal is for a different program in TF, please contact your program director directly with any questions.

The link about this grant is here

Nine Billion Names

Arthur C. Clarke passed away yesterday. Of course 2001 dominates peoples memory of Clarke, but it was one of his short stories, The Nine Billion Names of God, that gave me the willies as a kid. It's about a group of monks that hire a computer company to print out all the possible names of God. Read it here before reading the rest of the post.

The story is quite dated as one could now bring a laptop and a couple of batteries to Tibet to complete the task. Nine billion is hardly a large number any more; one could enumerate those names in a few seconds these days. I'm teaching intro programming next quarter. Maybe I'll make it into an class assignment. If the world were to mysteriously end when the students finish the project, at least no one will be around to blame me.

The Life of David Gale

Guest post by Nicole Immorlica

We say goodbye this month to a profoundly inspiring mathematician and economist, David Gale. His influential paper with Lloyd Shapley entitled College Admissions and the Stability of Marriage in 1962 introduced the much-loved stable marriage problem to the literature. The problem asks how a matchmaker in a village can arrange marriages such that no couple wants to divorce their assigned partner and run off together. Such a set of marriages is called "stable", and the set of stable marriages turns out to have a beautiful and endlessly amusing mathematical structure, uncovering such universal truths as "the proposing side of the market ends up with the best partner." (I.e., be proactive in your personal life?) Beyond giving professors and students endless hours of fun and amazing lectures, the stable marriage problem has also had significant impact in many practical settings by providing policy-makers a powerful tool with which to design centralized markets like public school choice and the National Residency Matching Program (NRMP). While the stable marriage work is perhaps Gale's most well-known contribution, he has also contributed significantly to many other fields of math and economics, about which I am much less qualified to comment. He also developed a sort of online museum of mathematical concepts MathSite, which includes some really neat interactive exhibits and is accessible to people of all ages and skill levels.
David Gale was 85, and is survived by his partner, Sandra Gilbert, three daughters, and two grandsons.

Should a grad student use one offer for leverage at another school?

One of my readers emailed me the question below. I gave some answers but then I thought Lets draw on the wisdom of my readers

(EMAIL FROM A READER) I have gotten into two math grad schools which I will call A and B. I want to go to A, but B offered me substantially more money. Can I use the offer from B as leverage to get a better offer from A?

My answer was NO because

1. I doubt it will work--- money has to come from somewhere, I doubt School A can just find money for you.
2. I doubt it will work-- School A has other students who want to go there, I doubt you're that big a deal to them.
3. If you make a threat like this you need to be able to carry it out. That would put you at school B which you don't really want.

Speculation: This just isn't the kind of thing that grad students do. This is NOT a reason to NOT do it, and perhaps grad students should do it. Do you want to be the rebel who changes the system? Can you be?

Readers- what do you thing? Do grad students ever do this? (I don't think so). Should they? Should she? ~

The Broken Remote Problem

This year I wrote one of the problems on the Univ of MD High School Programming Contest. The following conversation did not take place but could have.

BEGIN

BILL: Here is my problem. Imagine that you have a remote control for a TV set but that only a few of the numbers work. Also the UP-ONE and DOWN-ONE buttons work. Write a program that, given which numbers are available, and given x and y, return the sequence of botton pushes that get you from x to y in the least number of pushes. (NOTE- this description is incomplete- see problem 7 for a formal description.)

PROGRAM COORDINATOR: Is this some sort of Ramsey Thing in disguise?

BILL: No.

PROGRAM COORDINATOR: Then how did you think of it?

BILL: The remote at my in-laws only had 4 and 5 and UP and DOWN working.

END

The Broken Remote problem is not hard in that it does not need cleverness. But there alot of details to get right. Only 2 schools got the problem; however, the reason might be because problem 3 was harder than anticipated, hence some did not get to problem 7.

The point of all this?- similar to this post- everyday situations can inspire a math or comps sci problem.

Is the problem original? Hard to define what ``original'' means; however, I would not be surprised if it a similar problem appeared in some other contest.

Networking

Our weblog has joined the Scientific American Partner Network. You won't see any changes in the blog (besides the logo). You will continue to get the same wit and wisdom from Bill and I right here

We are joining the network to help promote the blog and to enter in a joint advertising agreement. We'll never get rich off this weblog, but money is good.

The Big Red Dance

Every year about this time, Americans come together and argue and wage large amounts of money on the outcome of a simple binary tree known as officially as the NCAA Division I Men's Basketball Championship. 65 teams play 6 rounds (two teams play 7 rounds) over three weeks in a single elimination to move up the tree.

The participants and the tree itself get unveiled Sunday but the fate of two teams that matter to me have already been decided. For the first time since I was a graduate student my undergraduate Alma Mater, Cornell University, will be in the tournament after going undefeated in the Ivy league. Meanwhile my new school, Northwestern, will be staying home after having won just one game in the Big Ten and having their last slim chance extinguished last night losing to Minnesota in the Big Ten tournament.

In 1988, the last time Cornell went to the tourney, their game against Arizona was televised on tape delay at about 3 AM. I taped the game on my VCR and watched it next morning before I found out what happened. Rooting for a team on a game whose outcome has already been determined feels a bit weird, sort of like waiting to open the box to see if Schrödinger's cat is alive or dead. Still I got emotional at the highs and lows of the game, although there were not too many highs as Arizona beat Cornell 90-50.

Flash forward two decades and now all the games will be streamed live over the Internet for free. But I'll be in Israel, the game will likely be on some ridiculous hour over there and I probably won't have computer access anyway even if they allow streaming internationally. So go Big Red, win your first four games without my live or even taped of a tape delay support, so I can watch you on final four weekend. But I wouldn't bet on it.

Abuse of Tagging System on amazon

Amazon has a feature where a reader can associate a word (called a tag) to a book, really user-defined keywords. However, this can be abused. Consider the following book:
Theoretical Aspects of Local Search

1. fraud (131)
2. lies (119)
3. fantasy (103)
4. mythology (94)
5. morons (69)
6. illogical (68)
7. unintelligent (68)
8. irony (65)

My my! Is the book really that bad? I recently had it reviewed for my SIGACT NEWS column and it seems like a fine book. Someone is abusing the tag system. But it gets worse. Look at the following book on a similar topic.
Local Search in Combinatorial Optimization

1. fraud (131)
2. lies (119)
3. breathtaking inanity (111)
4. fantasy (103)
5. junk science (71)
6. problem solving techniques (1)

What are the odds that exactly 131 people think that both of these books are frauds? that 119 people think both books are full of lies? that 103 people think that both are fantasy? I have it on good authority that these books are not bad. They may be too theoretical for someone's tastes, but thats no reason to trash them 131 times. So what is going on here? My guess: someone or some group does not like the area and has a program that tags things automatically.

This also happens in the humanities, which is perhaps less surprising since its more subjective.
The Columbia Anthology of British Poetry

1. anthologies (1)
2. avoid at all costs (1)
3. crazy (1)
4. cult (1)
5. evil (1)
6. fraud (1)
7. insane (1)
8. junk science (1)
9. poetry collection (1)
10. snake oil (1)
11. vocational (1)
12. discenment (1)

One big difference- people in the humanities have not learned how to write programs that will tag something multiple times.

The Long Slog

Mid-March is the time of year we begin to hear concern from students and postdocs on the job market. The CS job market is a lengthy affair running from January to June and beyond. But still if one has had few or no interviews scheduled yet, one cannot help but worry whether the situation will improve.

Some Advice:

• Don't Panic. Universities start with their very top candidates, often the very same people for each school. It is only after these candidates start deciding that schools will start bringing in other applicants. Also many CS departments first try to hire in applied areas and failing that will only then start to consider theory candidates. So sit tight, there is still a long way to go in this market.
• Expand your opportunities. Consider some schools you may not have thought of before. There are many possibilities overseas as well, especially for postdocs. The Internet is the great equalizer, allowing one to do strong research from just about anywhere.
• Consider another postdoc. It is becoming more common in our field to take a second or third postdoc and is no longer frowned upon when you reapply for permanent jobs.
• Keep busy. Keep your mind off the job hunt. Do some more research. Work hard on your thesis or journal versions of your papers. Take a vacation. Don't just sit at your computer checking your email every 15 seconds.
• Make some money. The hard truth is that there are not enough good academic jobs for all of the qualified applicants. But CS PhD's don't drive cabs. So join an Internet company or a hedge fund and go have a happy well-funded life.

Why is PARITY not in AC_0 important?

When discussing what should we teach in a basic complexity course (taken mostly by non-theorists) we often say results such-and-such is important. The question then arises- why is it important? Can the reasons be conveyed to a non-theory audience? Lets look at PARITY CANNOT BE COMPUTED BY POLYTIME, AND-OR-NOT, UNBOUNDED FANIN, CONSTANT DEPTH CIRCUITS (henceforth PARITY ¬in AC₀).

Why is PARITY ¬in AC₀ interesting? important? (For a good source on this result and other lower bounds on simple models see boppana_sipser.pdf boppana_sipser.ps, a survey from 1989 which is, sadly, not that dated.) I do find the result interesting, but none of the reasons below seem that satisfying to a non-theorist.

1. PARITY ¬in AC₀ is the way to obtain an oracle that separates PSPACE from PH. (An oracle to make them collapse is easy.) Hence no proof that relativizes can be used to seperate PSPACE from PH (this is not a rigorous concept, but people in the area have a sense of what it means). To motivate this you need to do some proofs that relativize. How many? Perhaps I am biased here- I had a course in computability theory covering 2/3's of Soare's book (I understood 1/2 of it at the time) before studying complexity theory, so I really knew what relativizing technique meant when I looked at oracles. That level of understanding is not needed, but some is. Even so, seems hard to get across to non-theorists in a course.
2. PARITY ¬in AC₀ is a natural problem on a natural model with a natural proof, and hence is interesting. This raises the question: do some people in the real real world really want to construct polysize constant depth unbounded fanin AND-OR-NOT circuits for PARITY, and does this result tell them why they cannot? Are there other lower bounds that are corollaries of PARITY ¬in AC₀ that give lower bounds on problems people really want to solve? I ask this non-rhetorically.
3. One approach to P vs NP is to start with simple models of computation that one can prove lower bounds in, and then scale up. There was more optimism for this approach back in 1989 then there is now.
4. The techniques used to prove the result are interesting (YES- there are several proofs, all interesting) and useful for other theorems of interest (circular reasoning?).

A more general issue: when are results interesting in their own right, and when are they meant to be part of a larger research program? We may not know until many years later.

And of course, for course content, the question is important? compared to what?

The Video King

I recently watched a surprisingly good documentary The King of Kong: A Fistful of Quarters where Steve Wiebe tries to break the Donkey Kong record held for many years by the popular Billy Mitchell. These battles take place at video arcades across America as well as Wiebe's garage in Redmond, Washington. A neat back and forth battle fraught with controversy for a record that only a handful of people actually care about. Similar in spirit to many academic battles.

More than just a good movie, it brought back memories from my high school days when video arcades were at their prime. I spent too many nights at the Willowbrook Mall arcade in New Jersey playing Donkey Kong, Pac Mac, Centipede and the like with their simple graphics and repetitive play. These arcade got quite crowded with a few local celebrities that could break a machines record with quite a crowd looking on. Much bigger crowds than Wiebe draws in his world record attempts in the documentary.

I was never a great video game player, I actually prefer pinball, but we took good notes and writing microcomputer simulations of some popular games became a hobby of mine (see Ribbit). I had just enough success to bring me heavily into computers and thus computer science. A little more success and I probably would not have gone into an academic career. Life moves in mysterious ways.

I would reminisce much more about those old video arcades but it's my turn on Guitar Hero. Rock on.

AI overhyped!!!!!!!!!!!!!!!!!!!!!!!!!!!

(A commenter left an off-topic comment on my last entry. INSERT GENDER-NEUTRAL PRONOUN HERE SINCE I DO NOT KNOW GENDER OF COMMENTER raisesd a question of interest. I have made a blog entry out of it. (NOTE- if you want a topic discussed on this blog, better to email Lance or I directly rather than make an off-topic comment.))

Kurzweil and others in AI think that computers will surpassing human intelligence in about 30 years. For example, see this overly optimistic entry on wikipedia. The media also seems to over-hype things. For example, when Deep Blue beat Kasporov there were headlines about how computers are smarter than people. These types of article seem to overlook the computational complexity of some of these problems. (Though one can say that we work on worst case and asy results while they work on ``real world problems''.)

My impression of Computer Chess is that they originally wanted a domain where computers could learn and adapt, but winning became too important and computers became too fast, so that (very clever) brute force searches took over. They may have more luck with the game of Go which is likely not able to be won with (even very clever) brute force. However, the whole story seems to be to show the computers are nowhere near human intelligence. (I grant that these terms are hard to define.)

Endorsements and Game Theory

If you are a big shot in the political world then endorsing a political candidate has a game theory flavor to it. I'm sure someone could make a formal game theory problem out of it. There are two possibly competing options:

1. Endorse someone who you think will get the nomination.
2. Endorse someone who you agree with politically.

And there are four scenarios.

1. You endorse someone who you think will get the nomination but who you disagree with.
   1. They win: you may get power (e.g., a cabinet post) but you may not be able to use that power to do what you want. In short, you have power but have lost your integrity (If you have been in politics long enough thats probably already gone.)
   2. They lose: you have lost your power and your integrity. (Pat Robertson's endorsement of Guilliani may be like that.)
2. You endorse someone who you agree with but probably won't get the nomination.
   1. If they win then you are in great shape. You get power and integrity.
   2. If the lose this isn't so bad since you still have your integrity. And if they did better-than-expected (e.g, Mike Huckabee) then you may have some power.
3. You endorse someone who you agree with and who you think will get the nomination.
   1. If you endorse after its obvious they will get the nomination then you don't get much. (Six Republican Govenors recently endorsed McCain. Too late to get any brownie points for that. Or the Vice Presidency.) If you endorse before its obvious then you could get power and keep your integrity.
   2. If they lose then hope that it is not thought that your endorsement caused the loss.
4. You endorse someone who you disagree with and who you think won't get the nomination. You may be in the wrong business.

Visions in Theory Workshop

I got this email and was NOT asked to blog about it, but should have been:
Visions for Theoretical Computer Science

Theoretical Computer Science (TCS) aims to understand the intrinsic capabilities and limitations of efficient computation. This subfield of computer science has a record of producing unexpected discoveries of high impact, such as public-key cryptography and quantum computation; and of raising deep scientific questions, such as the P vs. NP question.

On May 17, 2008, the TCS community will engage in a CCC-sponsored "visioning" workshop at the University of Washington in Seattle. The goals of the visioning workshop will be to:

1. Identify broad research themes within theoretical computer science (TCS) that have potential for a major impact in the future,
2. Distill these research directions into compelling "nuggets" that can quickly convey their importance to a layperson.

The nuggets produced in the workshop will serve to highlight the importance of sustained support for long-term, fundamental computing research, and to inspire the TCS community in its future efforts.

All researchers interested in theoretical computer science are encouraged to provide input for the visioning process. Since space is limited, those interested in attending should apply as soon as possible. (Ideas are welcome even from those who cannot attend.) More information is available at the workshop's website http://theorymatters.org/pmwiki/pmwiki.php?n=Visioning

Organizing Committee: Bernard Chazelle (Princeton), Anna Karlin (U. Washington), Richard Ladner (U. Washington), Dick Lipton (Georgia Tech), Salil Vadhan (Harvard).

About the Computing Community Consortium

The National Science Foundation created the Computing Community Consortium with the goal of stimulating the computing research community to imagine, articulate, and pursue more audacious research visions-visions that will capture the imagination and change the world. The CCC is funded through an NSF award to the Computing Research Association (www.cra.org); the CCC's Council operates as a committee of CRA.

Skipping Class

Someone on the job market was wondering how many classes they could skip teaching in a typical term. As this is generally not a good question to ask during an interview, I was asked instead. Surprisingly the person wants to remain anonymous. I can't remain anonymous answering here, but then again I have tenure.

First a little math exercise that I have done since I was an undergrad. Let's take a student who take five courses per quarter. There are about 28 hours/quarter and 3 quarters. Northwestern University tuition is $35,064, coming to $83.49/hour. If you have 30 students that amounts to a bit over $25K of tuition spent on each hour you teach.

This is false math, but students are often paying the big bucks for college, including the opportunity to be taught by leading researchers in the field. You shouldn't deprive them on a regular basis.

Nevertheless sometimes you have a workshop or a conference that you don't want to miss. As a general rule you shouldn't skip enough classes that students feel cheated. There are many factors that should be taken into consideration.

• Why are you missing the class? Do you have a family emergency? Are you a speaker at some conference? Are you visiting another university? Doing consulting work? Taking a vacation?
• What level of class? Skipping an undergraduate class is different than skipping a graduate seminar.
• Is there an easy make-up time that works well for the students? Can you find a replacement instructor?
• What is the standard at your university? Could be different between schools and departments as well. My business school friends cannot miss classes. MBAs get upset easily.
• What is your current status? Missing classes is a sign of irresponsibility. It can hurt your tenure case if you do it too much.

In the end follow your conscience. You owe it to your students to teach a good course and showing up matters.

Playing to Win

Consider the following game: A player starts with 0 points. For 100 rounds, a player picks one of the following three actions in each round.

1. Gets 7 points with probability 1/2, 3 points with probability 1/2.
2. Gets 4 points with probability 1.
3. Gets 10 points with probability 2/5, 0 points with probability 3/5.

The player wins by having at least 500 points at the end of the game. An alternative is to have two or more players with the winner as the one who has the highest score at the end.

What is the right strategy? Initially play action 1 and towards the end possibly switch to action 2 if you are ahead and action 3 if you are behind.

Many sports have these kinds of actions to keep the game exciting even if one player has a lead. Action 2 corresponds to using a closing pitcher, or a prevent defense. Action 3 is using a pinch hitter, pulling the goalie or the "Hail Mary" pass.

Quidditch doesn't have these options rather having a final move that usually dominates the rest of the scoring. The scoring rules of Quidditch is J.K. Rowling's biggest blunder in the Harry Potter universe.

Sometimes you do see action 2 moves earlier in a game. For example in football, after a touchdown a team can either kick for an extra point or run a short play to try for two. Kicks are are rarely missed and the plays are successful slightly more than half the time. Yet most coaches just kick unless there is a significant advantage to go for two.

The choices above apply to many more arenas than just sports. Obama and Clinton have been following actions 2 and 3 respectively over the last few weeks. Which approach will work? We'll find out tomorrow.