A Super Addiction

New superhero movies like Superman Returns and X-Men: The Last Stand remind me of my one time comic book addiction. As a child, I liked to read superhero comics but they had simple stories of saving the world. As I grew up the stories became less interesting and I stopped reading them. In my senior year of college I had a friend who collected comic books and convinced me to start reading them again as the stories have added some sophistication to them. During my last summer before I went to grad school I read through much of his collection. In my first few years of graduate schools I continued to reach comics voraciously and at one point I used a mail-order service to get 25-30 comic books a month.

At some point I realized that I read the books not so much for enjoyment but to finish before the next month's batch arrived. So I went cold turkey, I stopped reading comics and never went back.

However I had gotten my apartment mate hooked and he decided to take over my subscription. Several years later, this would be the mid-90's, the two of us were walking around and entered a comic book store for old times sake. I saw a rack of new releases and we had a conversation that went something like this.

Me: There's Batman, I thought he was paralyzed.
AM: He got better.
Me: I heard Superman was dead.
AM: He got better too.
Me: And the Flash? I remember when he died.
AM: That's Kid Flash all grown up.
Me: At least Wonder Woman hasn't changed.
AM: Actually that's her mother.

The Chicago Tribune just ran an editorial on Spiderman revealing his identity to the world. No worries, in due time the world will forget.

FOCS Accepts and a Movie

The list of accepted papers for FOCS 2006 has been posted. Since I was on the program committee I won't comment on the papers or the process.

So instead I offer to you this short movie (16 MB, 3:14) using soccer to explain Euclid's theorem that there are infinitely many prime numbers. Part of a new British project science.tv.

Finding a Mate

A female professor once told a story of a student who asked her out on a date. After she politely declined, the student asked her if she could be his advisor. Apparently it is harder to find a spouse than to get a Ph.D.

Which brings me to a question asked by a commenter on my Two Body post: How is a CS grad student to find love?

I get asked this question surprisingly often, even though I have been out of "the game" for nearly two decades. My best advice: Find some activity you like and join a club on or off campus that matches that activity. For example, concert band, contra dancing, running, skiing, sailing, etc. You'll meet other lonely people who share at least one interest with you.

I was never good at bars, clubs and blind dates. People like us don't always make a good first impression; that's why it's best to have an opportunity to make friends over time before asking someone out.

I missed the whole on-line dating scene. I have known some people who have had great success with them and others who haven't. Sunday the Chicago Tribune highlighted a new dating site Geek2Geek. Only for the desperate.

Does it matter whether you date an academic or not? Not really, just find the right person for you. Making a two-body problem is often harder than solving it.

FREE REPRINTS

Bill Gasarch is giving away free copies of one of our papers. Get them while they last.

I recently got in the postal mail REPRINTS of a recently published article of mine. This used to be standard—when an article was published you got 50 free copies. Less and less journals do this now.

Are reprints needed anymore?

NO: With everything online nowadays anyone who wants to find or read your article can.

YES: When someone visits you in your office its nice to be able to give them a copy without having to print it out. Also, when I went up for Tenure and Full Prof, I was asked for 14 copies of every article I ever wrote, so it was good to have the preprints around. (some went to my letter writers, which makes sense, some went to the committee deciding my case, which makes less sense, some went to the dean, provost, and for all I know the governor of Maryland, which makes no sense. Well maybe its okay–the governor has a Ph.D. in Mathematics–it was on Recursive Algebraic Topology. I am, of course, kidding–there is no such field.)

Even before the electronic age I never used reprints much (except when I went up for promotion). And the last few times I've written a letter for promotion I was NOT given the set of papers (NOTE: It would have been an appreciated courtesy if they had).

The article A Tight Lower Bound for Restricted PIR Protocols by Beigel, Fortnow and Gasarch (Computational Complexity, Vol 15, No 1, 2006, 82-91) can be YOURS if you send a Self-Addressed Stamped Envelope to

William Gasarch
Dept of Computer Science
University of Maryland
College Park, MD 20742
USA

(I would bet $5.00 I won't get any takers, except that someone may take the bet and request a copy, thus gaining $4.61)

Favorite Theorems: Probabilistic Complexity

May Edition

After we saw several randomized algorithms for primality we needed a way to classify and analyze the power of probabilistic computation. The power of computational complexity comes from not just studying old models of computation but taking new ones and finding ways to analyze their computational power as well.

Computational Complexity of Probabilistic Turing Machines, John Gill, STOC 1974, SICOMP 1977.  A Complexity Theoretic Approach to Randomness, Michael Sipser, STOC 1983.
Gill gave a formal definition of a probabilistic Turing machine and defined the basic classes, PP, BPP, RP (which Gill called VPP) and ZPP and showed the basic relationships between them.
Sipser's main result showed the BPP is contained in the fourth level of the polynomial-time hierarchy and the paper also includes Gács improvement putting BPP in Σ₂∩Π₂. More importantly Sipser introduced new techniques into the complexity theorists' toolbox including

• A new resource-bounded Kolmogorov distinguishing complexity, and
• Using Carter-Wegman hash functions to focus randomness. Perhaps the first extractor.

Sipser's tools go on to play an important role in the complexity of Arthur-Merlin games, graph isomorphism, statistical zero-knowledge and other areas of complexity. But perhaps most importantly Sipser showed you can apply the tools of complexity to really understand the power a new model of computation, the probabilistic machine. How about that newer model of a quantum computer? Bernstein and Vazirani's paper plays the Gill role, in formalizing efficient quantum computation and definining the basic classes like BQP. But while we have had some limited success in understanding the computational complexity of BQP, not only do we not know whether BQP is contained in the polynomial-hierarchy we have not yet developed great tools for understanding "quantumness" the way Sipser has shown we can do for randomness.

Campus Maps

As an academic I can't count how many different college campuses I have visited. Most US universities produce beautiful glossy maps to make it easy to navigate to and around the university but you can't get one of these maps unless someone mails you a copy. So I go to the university's website and can usually find a page of maps.

The University of Wisconsin map page has a beautiful flash version of their campus map. Someone put considerable time to design such a completely useless map. What am I supposed to do, walk around campus with my laptop open to figure my way around? Wisconsin also has a PDF version of their map but when printed the type is so small the map is also useless. Admittedly Chicago does not do maps much better.

The glossy maps are typically much larger than the usual printer page, but still universities can do better than just creating PDFs of shrunken versions of their usual map. Princeton, has their useless interactive map, but their printed map does a nicer job with a second page having a building directory very useful with a duplex printer.

Some day we will carry portable GPS devices which when we visit a campus will download building information and guide us to where we want to go. Until that day universities should take the effort they use to create fancy interactive maps and instead focus on producing a "print and go" map designed specifically for standard letter-size paper.

The Two-Body Problem

Many professional couples can have problems finding jobs in the same city, but for academics the problem magnifies. Even big cities will have only a small number of computer science faculty positions in major research universities and so try to imagine finding two such jobs. This quandary has a name that started as a joke, but no one laughs at trying to solve their Two-Body Problem.

Finding two open positions in the same department and often in the same area (like theory) can be particularly challenging as departments have a limited number of positions available each year. Still a department can often obtain one or two faculty members they might usually lose to a stronger school by going out of the way to solve a two-body problem.

Two-body problems become even more difficult when one member of the couple is considerably stronger than the other, or they are at different stages of their academic careers. In the latter case the older one might have a tenure-track position and then have to go on the job market again to solve their two-body problem. Even if they eventually do land tenure-track jobs at the same department, they will come up for tenure in different years adding more instability.

How about two academics in different fields? Some universities will go out of their way to accommodate such couples, with a dean or provost encouraging one department to hire in order to help strengthen the other department. Many other universities won't try as hard.

Finally are the couples with one academic and a non-academic professional that also has limited geographical jobs opportunities. Here a university can't help at all, one just needs to get lucky.

By US law, one cannot ask a candidate about the two-body problem when they interview, and if they don't mention it one cannot take it into consideration during the hiring process. Nevertheless you should tell the department about your situation. Universities often have ways of solving two-body problems and letting them know about it ahead of time will give them more time to make the right opportunities available.

In the end most two-body problems do get solved, though not always at the place as good as where they might have received a position on their own.

The H-Number

Thomas Schwentick sends me a link to an h-number calculator maintained by Michael Schwartzbach. Jorge Hirsch developed the h-number or h-index as a measure of the scientific output of a researcher.

A scientist has index h if h of his/her N_p papers have at least h citations each, and the other (N_p - h) papers have no more than h citations each.

The h-index discounts researchers who have one or two highly cited articles or books, or those researchers who just churn out mediocre papers.

There are loads of problems with the h-index. Google scholar and other citations counters are inaccurate because of trouble parsing and disambiguating papers. Citation counts do not accurately measure the quality of the paper—a paper that opens a field will get many more citations than a paper that closes it. The h-index rewards fads and cliques who always cite each others work. The h-index gives greater weights to more senior scientists and doesn't separate those who had good early careers from those still going strong.

Having said that we do love to compare ourselves with our colleagues in any way possible. An automated calculator does not work well for even mildly common names but it works great for "Fortnow" and while my h-index of 23 does not put me among the h-number elite, I'll take it.

EC

This week I'm attending EC '06, The 7th ACM Conference on Electronic Commerce in Ann Arbor. The name does not completely fit the conference which focuses mostly on computer science issues in economic models (e.g. computing Nash Equilibria) and economic question related to computer science (e.g. Internet-related auctions, economic mechanisms that solve algorithmic problems). The conference draws a mostly computer science crowd from both the theory and AI communities. Not many economists and most of those from business schools. Some industry folk come but mostly CS researchers from the big internet companies.

So what is a nice complexity theorist like myself doing at a conference like this? I study the power of efficient models of computation and what is an economic market but just another model of computation.

This year's conference had a big emphasis on sponsored search auctions, those keywords you see on the right side of search results. Yahoo, Google and recently Microsoft all run various auction scheme where companies bid on keywords like "mp3 players." Finding the right models, bidding mechanisms and equilibria for these auctions continue to challenge researchers. EC had four submitted talks, an invited talk, a workshop including a panel, and a competition all on sponsored search.

The conference had no overhead projector, white or blackboards. A laptop powered every talk at EC, the first time I've seen that at any conference. However they still had paper proceedings though did talk about possibly eliminating them at future conferences.

EC broke their attendance records with 172 participants who came to the conference and/or one of the workshops. Next year EC will be at FCRC along with STOC, Complexity and many other conferences.

Incomprehensible implies Boring?

Lawrence Downes writes a New York Times opinion Edison, Unplugged talking about the beauty of listening to music recorded in the 20's and 30's on a cylinder.

And there is another pleasure, too. It's the warmth of the technology. There are surely downloadable versions of "True Blue Lou." But unlike the MP3, whose magic is incomprehensible and thus boring, the wax cylinder is viscerally miraculous. It's staggering to think that lungs and plucked strings could vibrate the air, wiggle a stylus and capture a song for 100 years on a fragile thing that looks like a toilet paper roll. Compared with the iPod, it's a lot more human, a lot more accessible, a lot easier to love.

Downes has it backwards. The cylinder technology is very simple and provides a mediocre reproduction of the original music. Meanwhile the MP3 and other compression schemes use beautiful computer science ideas to make a strong digital copy, easily produced and portable, superior to cylinders in every way.

Luckily Downes is the outlier. He can enjoy scratchy music on his "toilet paper roll" while the rest of us enjoy music that sounds like the original on devices we can carry in our pocket, even if most people don't understand the details of technology involved.

EC, PCs and the WC

Fresh off a PC (Program Committee) meeting in NJ (no tellsies), I drove from IL to MI for EC where I was also on the PC. First I spent the day at TTI with lunch at the GSB to watch the USA at the WC. Thankfully by the time I get to CCC that game will long be forgotten.

Time-Travel Circuits

From Computing Like Gods by Jörn Grote

Time travel circuits had been in the first stages of development, but even then it was clear that we had cracked NP complexity. Before TTCs, solving computational problems from the NP-class in polynomial time was like finding the holy grail. And then we got TTCs. They utilized extremely small wormholes, were one opening had been accelerated near the speed of light.

Computers with time travel circuits could easily solve NP-complex problems in polynomial time, but the limit was actually PSPACE. Time travel was characterized by the computational complexity class of PSPACE, a class of problems that was either bigger or at least as big as the NP class.

When the news were out that they had TTCs, most people had no idea what it meant. I can still remember the headlines TIME TRAVEL IS REAL, WE CAN GO BACK, KILL YOUR GRANDFATHER. Naturally all these articles omitted the fact what we really could do with TTCs. It was cheap and easy to create the extremely small wormholes, but bigger ones grew unstable with rising size. The crater where once had been Calcutta tells you that they had found the limit and surpassed it.

Can Settling P vs. NP Get You Sued?

A reader Osias asks

About purported P vs NP solutions…I was wondering what if you, sooner or later, lets say, 10 years from now, solve yourself the P vs NP question. Can those authors sue you, claiming they have solved and you "stole" it from them?

I am most worried about myself too. Cause I am actually reading those papers from them and contributing to a wiki that analyze them. What if those guys decide to sue me? Can they?

I view this question as an extreme hypothetical. I don't expect either you or I will settle the P versus NP problem nor do I believe any of the papers posted on the wiki will play any significant role in the eventual solution.

We rarely see lawsuits in academics and then only when large sums of money are involved, for example patent rights based on research. The Clay Mathematics Institute Millenium Problems do provide a significant sum of prize money but even in the scenario you outline above, the suit would not be against you but instead the Institute for not recognizing the earlier work.

If I write a paper and later learn of some work that overlaps my paper, I will mention this other work even if I was unaware of it at the time of my research. I could imagine a scenario where I don't believe a paper has any connection to my research and the authors of that paper decided to sue me to acknowledge their perceived contributions. In such a scenario I would not be bullied and hold my ground, though not before consulting the university's lawyers.

On a related note, Luca reports on the status of the Poincaré conjecture, likely to be the first Millenium Problem prize awarded by the Clay Math Institute.

Funding Committee Report

At the STOC Business Meeting Richard Karp gave a report from the SIGACT Funding Committee.

Why does TCS [Theoretical Computer Science] have meager funding and little influence with funding agencies?

A possible answer: Unlike the physicists we have no tradition of leadership within the CS community, setting community goals, and advising, serving and lobbying the funding agencies and congress. For physicists this is a normal responsibility and it should be for us as well.

Ways to get involved include

• Write popular articles.
• Contribute short articles for the SIGACT website.
• Serve on NSF panels and as program directors.
• Provide research nuggets to NSF.
• Advise the committee.

The committee suggested two cross-cutting initiatives, Theory of Networked Computing and Computer Science as a Lens for Science.

Theory of Networked Computing will bring TCS into the NSF GENI Initiative. ToNC has already had some influence in the development of the Scientific Foundations for Internet's Next Generation (SING) area of the recent Theoretical Foundations solicitation.

Computer Science as a Lens for Science promotes algorithms as the language of science in many different disciplines including

• Quantum Computing
• Statistical Physics—Phase Transitions
• Algorithmic Economics and Game Theory
• Computational Biology

Most of all the committee wants community action to help in promoting and supporting TCS.

The Funniest Computer Science Joke Ever

My kids watched one of the Disney Channel sitcoms and I caught the following exchange:

Teacher: Do you want to hear the funniest computer science joke ever?
Student: Sure

Customer: My computer crashes every time I press enter.
Tech Guy: So don't press enter.

Teacher: Now wasn't that the funniest computer science joke ever?
Student: Yes it was.

Not so funny. But also nothing to do with computer science. No wonder my kids sometimes think I fix computers for a living.

The May 1 Deadline

In 1964 the Association of American Universities passed the following resolution setting a May 1 deadline for hiring away faculty from other institutions.

The sharp increase in the demand for teacher-scholars of high talent arising from our growing national needs in both instruction and research is now pressing against a limited supply of such talent in many disciplines. To assure the highest possible effect in each university in producing high talent to meet future national needs, sound and orderly planning will be required. When late and sudden, induced departures of personnel assigned to provide instruction to lead in research in one institution may well do more to impair the effectiveness of that institution than is justified by the gain to the institution extending the offer. This is particularly true at the level of tenure appointments where the institution has declared its willingness to undertake a continuing obligation and where there are most likely to be continuing obligations by the faculty member to graduate students and colleagues.

Therefore we consider it incumbent upon the administrations of both the prospective and current institutions of employment to call the attention of the individual faculty member to these obligations when employment changes, not accepted before May 1 for the immediately ensuing academic year, are under consideration. We believe that a responsible approach for both the institutions and the faculty members would be to consider offers made or pending on May 1, or thereafter, to be effective normally only after the intervention of an academic year.

In practice we are strongly discouraged from making such offers after May 1 but if say Harvard wants to hire away a professor from Yale after May 1 for the following academic year, the provost of Harvard makes a request to the provost of Yale and such requests are almost always granted.

Most fields finish up hiring early in the spring and the May 1 deadline reasonably blocks some last minute shuffles. But as the computer science hiring season often goes into June and junior and senior hires often compete for the same slot the May 1 deadline can create havoc in the CS recruiting process.

The high-demand low-supply of faculty in 1964 no longer holds true today. We need to reconsider whether a one-day-fits-all deadline really applies in today's diverse academic hiring environment.

Beauty and the Bee

Last night my daughters and I watched a New Jersey girl win the National Spelling Bee. The final three contestants were all females though my kids were rooting for the boy from Illinois.

Championship spelling requires considerable memorization as you'd expect but it has a mathematical aspect as well. One needs to know how to put together words using very specific rules that depend often on the word's origins, which the spellers can ask about.

A major network (ABC) broadcasted the spelling bee for the first time. ABC once televised the Miss America Pageant, which has since moved to a small cable station because of lack of viewer interest. Amazing to see Beauty lose to the Bee.

Research with Colleagues Visiting for a Short Time

Another guest post by Bill Gasarch

A colleague is going to visit for a short time and you want to get some research done. When does this work? When does this not work? How to you define `work' anyway? Some advice.

1. Have a well defined topic that at least one of you is knowledgeable about.
2. Have complimentary strengths. Or, more accurately, make sure that several strengths are covered (e.g., one knows Algebra, one knows Geometry, so you can do research in Algebraic Geometry. Well, maybe not...) (Better example: one is a knowledgeable about widgets, and one is clever with widgets.)
3. Don't chit-chat or socialize that much, OR at least have it be during a well defined time. For example AT SCHOOL mostly talk about research. AT HOME (if the visitor is staying at your house) socialize. For this reason, having the visitor at your house is a good idea so long as it makes sense logistically and is okay with the spouse.
4. Avoid long big lunches. You feel sluggish afterwards.
5. Right after you've proven something new you are excited about it. Write it up SOON, while you are still excited. For work with visiting colleagues, make sure that ONE of you is assigned to get out the first draft. (This is true of research in general.)
6. How long to stay? Too long can be bad since then there is the temptation to put things off. About a week is good. If someone is visiting for a semester than this is a whole different story, which someone else may blog on.
7. One goal of a collaboration working is that a paper is produced. Other goals could be that you both learn something you didn't know before.