Naming Complexity Classes

How do complexity classes get named? A proposal gets submitted to the Complexity Class Naming Commission (CCNC) which makes sure the class was not already named and the name has not been used before. The CCNC then puts out a Request for Comments to the community. Once the community responds, sometimes giving other suggestions for the name, the CCNC makes a formal recommendation to the Complexity Governing Council. The Council takes a final vote on the name.

If only we were so organized. Complexity classes get their name usually from the authors who invent them or occasionally by a later paper if the first paper didn't name the class or gave it an unmemorable name. Too often researchers will give a temporary name so they can work with a class and then keep that name out of laziness. Maybe I've been guilty of this a few times myself.

I could write several posts on badly named complexity classes. For now let me mention two important ones.

• NP for Nondeterministic Polynomial Time. But "nondeterministic" is not very descriptive. Logically ∃P would be better or PV for Polynomially Verifiable.
• PP for Probabilistic Polynomial Time. Since the error is not bounded away from one-half, the class is not a useful characterization of probabilistic computation. A better name would be Majority-P or just MP. BPP would then get the proper name PP and BQP would be just QP.

Someone asked me how to get their class into the Complexity Zoo. You can submit a proposal to the CCNC or just realize the Zoo is now a wiki and edit it yourself.

Definitions of Advice

When Karp and Lipton showed that if NP had polynomial-size circuits the polynomial-time hierarchy collapses, they also give a general definition of nonuniform complexity.

Let C be a class of languages and F be a set of functions. The class C/F is the set of all languages L such that there exists an A in C and an arbitrary f that maps n to strings with |f(n)| in F such that x is in L ⇔ (x,f(|x|)) is in A

Seems natural but this definition has given complexity theorists headaches for many years. The definition works fine for the applications in the Karp-Lipton paper, but it loses the semantic meaning of complexity classes in general.

In particular consider (NP∩co-NP)/poly. We need an A in NP∩co-NP for the definition above, but note that means we need two NP machines that accept complementary languages even for all possible advice strings, not just the correct one. In our toolkit paper we give a relativized world where NP/1∩co-NP/1 is not contained in (NP∩co-NP)/poly. We don't even know if (NP/poly)∩co-NP is contained in (NP∩co-NP)/poly.

At least we can use the terminology NP/poly∩co-NP/poly to nicely capture the class we want. For other classes like BPP/log we have no such clean notation. Once could make some new notation (someone suggested C//F) but instead we usually just state early on that we are not using the official Karp-Lipton terminology and only require the BPP behavior for correct advice.

Karp and Lipton did nothing wrong. They use a very natural definition that works for their purposes. Unfortunately the natural definition does not match the natural interpretation for all classes and will continue to confuse inexperienced complexity theorists for years to come.

On to Portugal

At noon today, as I was checking into my flight to Porto, Heathrow Airport went quiet, part of a nationwide two-minute memorial for the London bombing victims of a year ago. Machines were turned off and everyone stopped talking and just contemplated. The silence was deafening.

So starts the second leg of my journey, a visit to colleague Luis Antunes. As a commenter mentioned I am in Europe but not going to ICALP next week in Venice despite having a paper there. I greatly enjoy going to conferences and workshops but find them quite exhausting and going to three meetings in a row is more, especially with the large and broad ICALP in the middle is more than I can handle. For those in Venice, enjoy the conference and good luck to Italy in the WC final. Afterwards, come on up to Prague for Complexity.

At the workshop in Bristol, the projector was a bit dim and we had some problems reading some colors, green on the white background and red on a black background. This led to a heated discussion on what backgrounds to use. Harry Buhrman argues for white, as one can see the text best. Any background color can work, as long as you don't use too many different colors for text and carefully choose contrasting colors. Though I find any plain color, especially white, a bit boring. I typically use one of the Powerpoint defaults, which Microsoft has designed to both look pleasant and have good readability.

Complexity and Randomness

The Complexity and Randomness workshop in Bristol has an unusual mix of researchers in random graphs and mixing (the British) and complexity (the rest of us). For example Colin McDiarmid talked about the maximum degree of a random planar graph (Θ(log n)) and Mark Jerrum on Monte Carlo mixing methods, in addition to Irit Dinur on her PCP proof, Oded Goldreich on pseudorandomness and coming up Luca Trevisan on Gowers uniformity and Vijay Vazirani on markets.

I don't go to England much because they don't have many researchers in computational complexity, so I get a rare chance to talk to many of the researchers in this area. These workshops give us a chance for us to tell them about the latest in complexity and I can learn about areas I don't keep up with as much as I should.

Leslie Ann Goldberg gave a neat talk on the hardness of estimating the Tutte polynomial of graphs on a variety of points. I never really learned about the Tutte polynomial; it has some cool properties that for various parameters can count properties of graphs such as number of connected components. Goldberg and Mark Jerrum showed some of the approximations are #P-hard, that is hard for counting solutions of NP problems. We rarely see #P-hardness for approximating as all #P problems can be approximated probabilistically with an NP oracle. The Tutte polynomial is harder to approximate on some negative values because of the cancellations given by negative terms.

England on the 4th of July

I have just started a three week European trip. This week at the Randomness and Complexity workshop in Bristol, next week in Porto, Portugal and ending up at the Computational Complexity conference in Prague.

I will celebrate American Independence Day in the country we declared independence from, and not for the first time. You see many European conferences and workshops around this time. You don't notice Independence Day at all in England, the English being more upset at their lost in Portugal in the World Cup then their loss in an 18th century war.

I'm rooting for Portugal to win against France in the semifinals, since I'll be in Portugal for the final game and also because they are playing the French.

Blogging will be light this week as Internet access is not that easy; the Marriott here charges 15 Pounds/day for wireless access, shame on them.

If you don't normally read comments, the recent post on FOCS accepts has generated a record number of comments for this weblog. Check it out and join in the discussion. Nothing gets the emotions up more than discussing the importance of various conferences.

England on the 4th of July

I have just started a three week European trip. This week at the Randomness and Complexity workshop in Bristol, next week in Porto, Portugal and ending up at the Computational Complexity conference in Prague.

I will celebrate American Independence Day in the country we declared independence from, and not for the first time. You see many European conferences and workshops around this time. You don't notice Independence Day at all in England, the English being more upset at their lost in Portugal in the World Cup then their loss in an 18th century war.

I'm rooting for Portugal to win against France in the semifinals, since I'll be in Portugal for the final game and also because they are playing the French.

Blogging will be light this week as Internet access is not that easy; the Marriott here charges 15 Pounds/day for wireless access, shame on them.

If you don't normally read comments, the recent post on FOCS accepts has generated a record number of comments for this weblog. Check it out and join in the discussion. Nothing gets the emotions up more than discussing the importance of various conferences.

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.

Dispersing Ramsey Graphs

Perhaps the very first example one sees of the probabilistic method: Show there exists a graph on n vertices with no clique or independent set of size k = 2log n. Simply pick the graph at random. For any set S of k vertices the probability that the graph restricted to S will be a clique or independent set is at most p=2^{-(k choose 2)}/2. The probability that any subset S is a clique or independent is at most p times (n choose k) which is less than one for k = 2log n. So there must be some graph with no clique or independent set of size k.

Actually constructing such a Ramsey graph is another story. You can create the graph in quasipolynomial (2^{poly log n}) time using standard derandomization techniques. In 1981, Frankl and Wilson had a polynomial-time construction of a graph that had no clique or independent sets of size 2^{(log n log log n)1/2}. That bound stood until the recent STOC paper by Barak, Rao, Shaltiel and Wigderson creating a graph with no clique or independent set of size 2^{(log n)o(1)}.

Barak et. al. were not trying to create Ramsey graphs, rather to create randomness dispersers for two independent weakly random sources. As a bonus they improved the Frankl-Wilson bound giving yet another example where proving one kind of theorem in complexity gives an exciting result in an apparently unrelated area.

The South Has Risen

Who would have thought the next theoretical computer science powerhouse would have come from Atlanta? Georgia Tech this year has hired Santosh Vempala and Adam and Yael Tauman Kalai into an already amazing theory group. In the past few years Georgia Tech has gone from a good theory program to one of the largest and strongest in the country. How did they accomplish that feat? Seeing potential where others haven't, solving two-body problems both inside and outside the department and most importantly having the resources to go after opportunities when they occur. Alas two of their recent hires came at the expense of Chicago/TTI but hey, all's fair in love, war and recruiting.

It's not like other departments have stopped hiring in theory. In the past two hiring years alone several schools have hired junior theorists including Carnegie-Mellon, Cornell, Michigan, MIT Math, Penn State, Rochester, Stanford, Washington and Wisconsin. Many universities realize that in order to have a strong CS department one needs a strong theory group and in order to improve or even maintain strength in theory one needs strong young talent.

Talking to Publishers

A few publishers showed their wares at STOC. This is a good opportunity to talk them about book ideas or about publisher's policies and how they operate. You can also get some good books at a discounted price; I picked up J. Michael Steele's The Cauchy-Schwarz Master Class from Cambridge University Press based on a recommendation.

I had a lengthy conversation with Sweitze Roffel, who took over Chris Leonard's position as publishing editor of the Elsevier theory journals. Sweitze is quite aware of the negative perception of Elsevier in the theory community and wants to talk to the community about their concerns. So talk to him at conferences or send him email and tell him your concerns about Elsevier's policies. A couple of nuggets.

• Sweitze will move the offices for his journals from Amsterdam to New York to emphasize the global nature of Elsevier and be closer to editors.
• Elsevier has an arrangement with Microsoft's Academic Search but negotiations with Google Scholar are going slowly because of Google's "secretive" policies.
• Elsevier plans to give contributors (editors, referees, authors) access to their Scopus system. Elsevier also has their own free academic search site Scirus.
• The free access experiment of Information and Computation continues.
• Elsevier is exploring starting their own version of Springer's Lecture Notes in Computer Science series and also a Review journal.

I also talked to Lauren Cowles, an editor for Cambridge University Press who wrote a good comment on a publisher's view of putting books on the web. She pointed out Victor Shoup's A Computational Introduction to Number Theory and Algebra is available for purchase and also freely available online.

Flying American

A commenter asked about the Fly America Act that requires, with few exceptions, that when traveling abroad on US money, such as an NSF grant, one must use a US-based carrier. This silly protectionist law just supports American airlines with tax-payer dollars and in the end wastes both money and time. Not only should I be able to fly a foreign carrier to other countries I should even be able to fly a foreign carrier between US cities.

As a practical matter the Act is more a nuisance than a serious problem. US carriers have an extensive collection of foreign routes, you can fly most foreign flights via a US-airline codeshare, and in a jam one could launder some grant money to a non-grant account and then use non-grant money to fly the foreign carrier. Not that I ever have, ever would or ever condone taking the last action.

Thoughts from STOC

I don't go to many talks at STOC, I prefer hanging out in the hallways and talking with other attendees. But the best talk I saw so far was the first, Atri Rudra gave an easy to follow overview of a his paper Explicit Capacity-Achieving List-Decodable Codes with Guruswami. Both student paper award winners also gave nice overviews of their technical results. Much better than trying to wow us with complicated formulas.

What were the folks in the hallways talking about? Worry about funding in the short term but cautious optimism a few years down the line. Some optimism on employment; many good places hired in theory this year and most students found postdoc, faculty or industrial positions. I didn't see many students scrambling for jobs. Last time STOC was in Seattle (1989) I was one of those scramblers.

Prabhakar Raghavan, a theorist who now heads Yahoo! Research, gave the first invited talk about some mathematical questions related to Yahoo. Prabhakar spent a considerable part of his talk on sponsored search, the bidding and ranking mechanisms for those who pay to be listed right of the search results. Yahoo currently uses a variant of second-price auctions that is non-truth telling and has some other flaws but is simple enough for people to understand how much they will pay. Google on the other hand use more complicated schemes with nicer properties but most if not all of its users don't really understand the bidding mechanism.

Russell Impagliazzo gave the other invited talk on pseudorandomness, his title slide containing a joke only my generation would get.

Let's secretly replace Al's coffee cup of random bits with pseudorandom bits and see if he notices.

Russell's take-home message: Randomness does not help in algorithms but we can't prove it doesn't help until the circuit complexity people (like Russell) get on the ball and prove some good lower bounds.

On a personal note, today I have lived as long as my father. Puts a real perspective on life.

STOC Business Meeting

Howdy from Seattle. Here's some highlights from the STOC business meeting.

78 papers accepted out of a record 288 submissions.

There were 275 registrants including 109 students. Rooms at the conference hotel ran out slightly before deadline and the organizers scrambled to find rooms at a nearby hotel. Be sure and reserve your hotel early in the future.

As of January 2, Bill Steiger has become the new program director for theoretical computer science at the NSF. He expects to fund 15-20+ awards from an estimated 100 theoretical computer science submissions to the Theoretical Foundations solicitation due this Thursday.

Richard Karp gave a long talk about the activities of the SIGACT Funding Committee. More on this in a future post.

Tom Leighton won the SIGACT Distinguished Service Award. The best student paper award winner was split between Anup Rao for Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources and Jakob Nordström for Narrow Proofs May Be Spacious: Separating Space and Width in Resolution. The best paper award went to Irit Dinur for The PCP Theorem by Gap Amplification.

FOCS 2006 October 22-24 in Berkeley. STOC 2007 June 11-13 in San Diego as part of FCRC. STOC 2008 in Victoria, British Columbia May 18-20.

Favorite Theorems: Primality Algorithms

April Edition

For many years the standard example of a probabilistic algorithm checked whether a number was prime.

Riemann's Hypothesis and Tests for Primality, Gary Miller, STOC 1975, JCSS 1976.

A Fast Monte-Carlo Test for Primality, Robert Solovay and Volker Strassen, SICOMP 1977.

Probabilistic Algorithm for Testing Primality, Michael Rabin, Journal of Number Theory, 1980.

Let n be an odd number and n≠r^q for r,q>1. Fermat's little theorem shows that for any a, 1<a<n, if aⁿ≠a (mod n) then n is composite. But for a special set of composites called the Carmichael Numbers, this test will fail for all a. Miller adds the condition that a^(n-1)/2k-1 and n are relatively prime for all 2^k dividing n-1 and shows that assuming the Extended Riemann Hypothesis, for any composite n there is an a < O(log² n) passing the test. This gives a polynomial-time (in the number of bits to express n) algorithm for primality assuming ERH. Rabin showed that one could instead choose random a's giving a probabilistic algorithm with no assumption. The resulting test is now called the Miller-Rabin primality test. Solovay and Strassen give a different test based on the Jacobi Symbol.

Of course now we know that primality has a polynomial-time algorithm with no unproven assumptions. So why did I choose these obsolete algorithms for favorite theorems? They are not so obsolete as they are considerably more efficient then Agrawal-Kayal-Saxena. But more importantly they served as the motivation for the study of probabilistic computation, much like Shor's Quantum Factoring Algorithm motivates quantum computing today. Without studying probabilistic computation we would have had no modern cryptography, no derandomization results, no Toda's theorem, no interactive proofs and no probabilistically checkable proofs with their hardness of approximation consequences.

Taulbee Survey

Via CRA Bulletin the 2004-2005 Taulbee Survey has been posted. A wealth of statistics about computer science in the US and Canada. The charts fall into several major categories.

1. Ph.D. Production and Employment. Most CS Ph.D's ever (1189) last year. Nearly all of them found jobs.
2. Bachelor and Master's Students. Enrollment continues to decline.
3. Faculty Demographics. Faculty sizes continue to grow, though slowly, and are getting slightly more diverse.
4. Research and Graduate Student Support. A drop in research expenditures likely due to fewer grants.
5. Faculty Salaries. Truly useful when negotiating your pay. An interesting inversion where the schools ranked 13-24 in CS pay higher salaries than the schools ranked 1-12. And just who is being paid $400K?

The end of the report sums up the statistics nicely.

As predicted last year, our field is producing Ph.D.s at a record rate, and the short-term forecast is for continued record production. While there is no evidence in our employment statistics that the increased production is resulting in an inability of Ph.D. graduates to find work, an increasing fraction of new Ph.D.s appear to be taking positions outside of North America. In the wake of accelerating globalization of the marketplace, this is not surprising.

Three consecutive years of decreasing numbers of new Ph.D. students, and a sharply reduced pipeline at the Bachelor's level, will make it difficult to sustain this production rate in the longer term. Moreover, it is not yet clear when the decline in our undergraduate program enrollments will end. The double-digit percent decrease in bachelor's production observed this year is likely to continue for the next several years. Coupled with the declining representation of women in our undergraduate programs, our ability to produce a workforce that is sufficiently educated technically to meet the needs of the job market in computing is being severely challenged. The declining enrollments at the Bachelor's level also will increasingly challenge the ability of CS/CE departments to grow their faculty as they desire.

Graph Theory and the NSA

How could I not blog about Jonathan Farley's op-ed piece The NSA's Math Problem? Farley looks at the NSA's use of phone data as and argues that using graph theory to analyze the calls won't help find terrorists. But Farley doesn't do a particularly good job making his case.

First, the "central player" the person with the most spokes might not be as important as the hub metaphor suggests. For example, Jafar Adibi, an information scientist at the University of Southern California, analyzed e-mail traffic among Enron employees before the company collapsed. He found that if you naively analyzed the resulting graph, you could conclude that one of the "central" players was Ken Lay's…secretary.

Somehow if we find the "secretary" of a central US terrorist that should be considered a major success. But more importantly if we know just a little about some terrorist activities the graph can give us a great advantage in finding important sites. Google's PageRank primarily uses graph theory very successfully to rank order search results and there is no reason similar ideas won't work on phone data as well.

By no means should we accuse someone of being a terrorist solely because of their calling pattern. Will all terrorists be found on phone data alone? Of course not. But using graph information can give us important information as to where to look and narrow the search.

The main objection to the NSA's work is not that the phone data has little value but that it is too valuable. You can use the data to find out much more about Americans than who is a terrorist. We lose our freedom against government intrusion when the NSA has this data and that's what we need to argue against, not some fake argument that the NSA's algorithms won't work.

Steven Levy has a more reasonable discussion in Newsweek.

Computer Reliability

Suppose we could create a system where all automobile traffic in the US would be controlled by a central computer system. Traffic would flow more smoothly, fuel consumption could be better controlled, but with a catch that failures in the system could cause 10,000 deaths/year.

Keep in mind that we now have over 38,000 automobile fatalities per year. Even if we leave out alcohol-related deaths that number drops only to about 24,000. Still the public would find 10,000 deaths unacceptable and we would junk a system that would actually save lives as well as time and fuel.

I find when we frame the debate on the unreliability of computers, we usually measure it against perfection, rather than measuring it against the status quo. Whenever I read the Inside Risks column at the end of each CACM, I feel they fail to point out how little the risks are compared to the advantages of computing, instead of pointing out how bad the risks compared to unachievable perfection.

Consider electronic voting. I noticed that Diebold, the company in the middle of the electronic voting controversy, also makes the ATMs I use to withdraw money from my bank. ATMs are not foolproof, thieves have managed to fake ATM cards and discover passcodes to steal money from these machines. But banks know that the labor cost savings they get from ATMs greatly outweigh the losses.

Will electronic voting ever completely prevent any kind of fraud? Of course not. But will it beat out the systems we currently have in place? That's not that high a bar to pass.

I can vote proxies on my stocks and mutual funds over the Internet. There are some real money issues involved in the proxies. If Internet voting works well enough when serious money is involved, why can't we use it for general elections as well?

FCRC

This Monday May 15th is the early registration deadline for this year's Conference on Computational Complexity in Prague. The early registration date for the Electronic Commerce (EC) conference is Tuesday the 16th.

Next year both Complexity and EC will be part of the Federated Computing Research Conference (FCRC) in San Diego along with a plethora of other conferences including STOC, Computational Learning Theory (COLT), and Parallel Algorithms and Architecture (SPAA). June 13th is the day of death: STOC (2 tracks), EC, Complexity and COLT all have sessions that day. A theorist could find him or herself wanting to see five talks all given at the same time.

Game Science

Ehud Kalai proposes renaming the Game Theory Society to the Game Science Society and welcomes your comments. The goal of changing the name of the society is to change the name of the field to better describe what the field does and broaden its image.

An important example where the expanded name may get additional support is within a university. For example, it is hard to imagine the creation of a department devoted to the study of a theory. On the other hand a department devoted to study a science seems more plausible. To put things in perspective think of an analogy within another young field. Devoting major resources to a subject called "computing theory" less likely than devoting major resources to a subject called "computer science."

I've mentioned changing the name of Game Theory before but then again I never felt Computer Science is a great name. Following Kalai's reasoning, what if we renamed "Theory of Computing" to "The Science of Computing". Would that make our field sound more noble and generate more funding?

The Importance of Natural Proofs

Razborov and Rudich's paper Natural Proofs gives a combinatorial framework for proofs to show that circuits in a given class cannot achieve a given computational task. The paper explains the difficultly of extending these proofs to show, for example, that NP does not have polynomial-size circuits (and thus P≠NP). But do natural proofs really present a barrier to proving important circuit lower bounds?

One approach to showing NP does not have polynomial-size circuits: Find some property C of functions such that SAT is in C. We then show, using some sort of inductive argument, that no function computable by polynomial-size circuits can have property C. This would imply SAT, cannot have polynomial-size circuits.

Briefly a natural proof is such a proof where C has two properties.

1. Largeness: C contains many functions.
2. Constructivity: One can efficiently verify that a function f is in C.

Razborov and Rudich show that such a proof against polynomial-size circuits would break pseudorandom generators and in particular imply that the discrete logarithm is not hard. So under reasonable hardness assumptions, natural proofs cannot be used to prove lower bounds against polynomial-size circuits. See the paper for more details.

Sounds bad for proofs against circuits. But let's consider the two properties. The authors give a good argument why the largeness condition should hold, however

We do not have any similar formal evidence for constructivity, but from experience it is plausible to say that we do not yet understand the mathematics of C_n outside exponential time (as a function of n) well enough to use them effectively in a combinatorial style proof. We make this point in Section 3, where we argue that all known lower bound proofs against nonmonotone circuits are natural by our definition.

Indeed they do show all known proofs are natural, but in some cases go through considerable effort to "naturalize" these proofs (as opposed to relativization where the fact that a theorem relativizes follows immediately from the proof).

Consider what I call quasinatural proofs, where we only require the largeness condition. One might say that if discrete logarithm is hard then a quasinatural proof must prove the nonconstructivity of C. But really you get a conditional. If there are quasinatural proofs against polynomial-size circuits then

If C is constructive then Discrete logarithm is easy which is just a "pigs can fly" theorem that we see often in complexity.

Avi Wigderson points out that unconditionally you cannot have a natural proof showing that the discrete logarithm problem is hard. If we unravel this statement then we get that giving a quasinatural proof showing discrete logarithm is hard would require proving that discrete logarithm is hard, hardly a surprise.

I don't have an example of a quasinatural proof not known to be natural as we have very limited techniques for proving circuit lower bounds. Natural proofs do give us some insight into what kind of proof techniques we need for stronger lower bounds, but they do not, in and of themselves, present a major barrier to finding such proofs.

Forward-Looking Links

A computer science paper goes through many phases: manuscript, technical report, conference submission and proceedings and journal submission and published version. As a paper goes through these stages they usually improve, adding more background and intuition, better and more detailed proofs and so on. If someone wants to read your paper, you'd like them to look at the latest version. How do you make sure that they even know about the latest version?

You can't go into everyone's paper proceedings and add a yellow sticky to your paper saying to check out the new and improved journal version. But in this electronic age we can, in principle, add these notes.

First of all keep the papers on your webpage up to date. Many people just go to an author's page to download a paper and often they find some ancient version.

But after that then what? ECCC allows one to submit a revised version or add a comment which could point to a revised version. arXiv allows one to add journal information to an existing paper. Both of these require actions by authors that rarely happen. The digital libraries of proceedings publishers ACM and IEEE-CS don't have any mechanism to add pointers to later papers.

The field should have some standard mechanism for updating pointers to future papers. Until then we have to rely on the readers to find the latest papers on their own and perhaps hope that paper search tools like Citeseer, Google Scholar and Microsoft Academic Search will point to the latest and greatest version of a paper.

Rejection and Rejecting

Luca and Oded talk about rejection. Here are some thoughts.

Rejection hurts. Academics thrive on earning the respect of their peers and it's tough to think that someone doesn't want you. So go ahead and be depressed for a day or two and then move on.

Stanford is my ultimate rejecter, having turned me down for undergrad, grad, junior and senior faculty positions without the least bit of interest. But I got my revenge–I once got a parking ticket at Stanford and I never paid it. Ha!

A few people have complained to me about how rejections letters are written. A rejection letter contains exactly one bit of useful information. The rest is irrelevant and you should not let it get to you.

Suppose Alice sends email to her friend Bob asking if Bob's department would be interested in her. In academics, Bob usually won't give his real thoughts ("We are looking for strong candidates and you are not one of them"), instead he'll find some property P such that Alice has P but they won't hire in P, for example "Unfortunately we are not looking for any cryptographers this year." A couple of warnings for Bob:

1. Be sure P is not illegal, i.e., based on religion, race, gender, etc. Even if you don't discriminate, saying that you do is not a smart thing.
2. Bob's department might end up hiring a cryptographer. Then Alice will realize that Bob didn't want Alice because she was a cryptographer, rather he just didn't want Alice.

The Cost of Big Science

A panel at the National Academy of Sciences suggests that the US should support Fermilab's bid to land the International Linear Collider.

via Chicago Sun-Times

As a scientist I should support such a project, especially one located in the suburbs of Chicago. But at what cost? As a perspective, next year's proposed budget for the entire National Science Foundation is just over $6 billion.

This ILC reminds me of the Superconducting Super Collider, a project that spent $2 billion dollars digging a hole in Texas that was killed by Congress in 1993 once the projected costs topped $12 billion.

Putting large dollars into a single basket will take away the incentive to increase basic research funding in other scientific endeavors. The main argument for the ILC at Fermilab is not that the research won't get done, it just won't get done in the US. So let the Europeans or the Japanese have the flashy expensive collider and let the US do what it does best—basic research advancing science over a large range of disciplines.

Four Coloring the United States

For a talk I wanted to show a map of the United States using four colors with the usual constraint that every pair of states that share a common border have different colors. The four-color theorem says that such a coloring must exist.
So I tried Googling to find such a picture of a four-colored United States but I couldn't find one. NASA states it as a challenge but doesn't give the solution. Most maps I found like this one

use five or more colors, probably because they use a simple greedy algorithm.

Four coloring the US is not difficult. I found a Map Maker utility that lets you color the states anyway you want. Here is my four coloring.

My independent sets:

1. AK, AL, AR, CT, DE, HI, IL, ME, MI, MN, MT, NE, NM, NV, SC, VA, WA
2. AZ, DC, FL, KS, KY, MS, NC, ND, OR, PA, RI, TX, VT, WI, WY
3. CA, CO, GA, ID, IN, LA, MA, MO, NJ, SD, WV
4. IA, MD, NH, NY, OH, OK, TN, UT

The United States cannot be three colored, just consider Nevada and its neighbors. When writing this post I Googled on "four-color theorem" and the first link was this page which features a four-colored United States. Well at least I got a weblog post from all this work.

New Priorities for Computability Theory

Bob Soare, who wrote one of the great textbooks on recursion theory and then almost single-handedly changed the name of the field to computability theory, teaches an intense two-quarter class on the topic every other year in Chicago. To my surprise just now, halfway through the second quarter (15 weeks into computability theory) he is just proving the solution of "Post's Problem", the existence of incomplete degrees, that excited Gödel in his letter.

When I sat in on Soare's class in the early 90's, by this time he had covered much more complicated finite injury arguments and was starting the infinite injury constructions like the Sacks Density Theorem: Given r.e. sets A and B, such that A is reducible to B and B is not reducible to A, there is a set C that lies in between.

I asked Soare about this last week. He isn't dumbing down his class, rather he's acknowledging a change in direction in the field, more along the lines of looking at the complexity of reals (infinite sequences of bits), often by examining those defined by infinite branches of computable trees.

For example, many computability theorists today are studying notions of "random reals", infinite sequences that share some properties of randomly chosen numbers. They have shown neat connections to Kolmogorov complexity and connections to Chaitin's Ω. For any reasonable ordering, Chaitin's Ω is a computably enumerable random real and Kucera and Slaman show the surprising result that the converse is true as well.

One used to measure a recursion theorist by the difficulty of their constructions; now we see more a focus on the beauty of the theorems and their proofs.

Soare is working on a new version of his textbook that will differ in a couple of ways. He is changing terminology (recursive and r.e become computable and c.e.), but more importantly he changes the focus to more strongly develop the theory that drives computability today. A good lesson: Fields change over time and better to acknowledge and embrace those changes than to fight them.

The Home Stretch

If you have an academic job offer, what next? Don't forget to negotiate. I wrote a post on negotiating last fall and in particular you should read the Chronicle article. Worst mistake: Not negotiating.

If you don't have an offer yet, don't panic (at least not too much). We are just entering the home stretch of the CS academic job season. Many of the same few people get the initial interviews and once they get sorted out, more interview and offers are still to come. Don't be afraid to contact departments still in play and remind them of your continued interest.

My first time on the job market in 1989 I didn't get my first offer until June and still had an interview after that. The system has only become even more insane since.

Still you might start getting ready for Plan B. Consider lowering your sights, seeking temporary and/or overseas positions, or thinking about industrial jobs.

Searching for jobs is perhaps the most stressful time in one's academic career. Do your best to keep your spirits up and your options open.

Kurt Gödel (1906-1978)

Kurt Gödel came into our world one hundred years ago today. Gödel's incompleteness theorems changed the way we think about mathematics.
We reprint the translation of the now famous letter he wrote fifty years ago to von Neumann which was rediscovered in 1988. This letter describes something close to the P versus NP problem years before the field Computational Complexity even had its name. SIGACT and EATCS jointly sponsor a prize named after Gödel because of the letter.
Princeton, 20 March 1956
Dear Mr. von Neumann:
With the greatest sorrow I have learned of your illness. The news came to me as quite unexpected. Morgenstern already last summer told me of a bout of weakness you once had, but at that time he thought that this was not of any greater significance. As I hear, in the last months you have undergone a radical treatment and I am happy that this treatment was successful as desired, and that you are now doing better. I hope and wish for you that your condition will soon improve even more and that the newest medical discoveries, if possible, will lead to a complete recovery.
Since you now, as I hear, are feeling stronger, I would like to allow myself to write you about a mathematical problem, of which your opinion would very much interest me: One can obviously easily construct a Turing machine, which for every formula F in first order predicate logic and every natural number n, allows one to decide if there is a proof of F of length n (length = number of symbols). Let ψ(F,n) be the number of steps the machine requires for this and let φ(n) = max_F ψ(F,n). The question is how fast φ(n) grows for an optimal machine. One can show that φ(n) ≥ k ⋅ n. If there really were a machine with φ(n) ∼ k ⋅ n (or even ∼ k ⋅ n²), this would have consequences of the greatest importance. Namely, it would obviously mean that in spite of the undecidability of the Entscheidungsproblem, the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine. After all, one would simply have to choose the natural number n so large that when the machine does not deliver a result, it makes no sense to think more about the problem. Now it seems to me, however, to be completely within the realm of possibility that φ(n) grows that slowly. Since

1. it seems that φ(n) ≥ k ⋅ n is the only estimation which one can obtain by a generalization of the proof of the undecidability of the Entscheidungsproblem and
2. after all φ(n) ∼ k ⋅ n (or ∼ k ⋅ n²) only means that the number of steps as opposed to trial and error can be reduced from N to log N (or (log N)²).

However, such strong reductions appear in other finite problems, for example in the computation of the quadratic residue symbol using repeated application of the law of reciprocity. It would be interesting to know, for instance, the situation concerning the determination of primality of a number and how strongly in general the number of steps in finite combinatorial problems can be reduced with respect to simple exhaustive search.
I do not know if you have heard that "Post's problem", whether there are degrees of unsolvability among problems of the form (∃ y) φ(y,x), where φ is recursive, has been solved in the positive sense by a very young man by the name of Richard Friedberg. The solution is very elegant. Unfortunately, Friedberg does not intend to study mathematics, but rather medicine (apparently under the influence of his father). By the way, what do you think of the attempts to build the foundations of analysis on ramified type theory, which have recently gained momentum? You are probably aware that Paul Lorenzen has pushed ahead with this approach to the theory of Lebesgue measure. However, I believe that in important parts of analysis non-eliminable impredicative proof methods do appear.
I would be very happy to hear something from you personally. Please let me know if there is something that I can do for you. With my best greetings and wishes, as well to your wife,
Sincerely yours,
Kurt Gödel
P.S. I heartily congratulate you on the award that the American government has given to you.
[The text is taken from this page where you can also find the original German text and acknowledgments. John von Neumann, who received the Presidential Medal of Freedom in 1956, had cancer at the time of the letter and passed away in 1957.]

Richard Rado (1906-1989)

Tomorrow marks the hundredth anniversary of the birth of combinatorialist Richard Rado. Rado is the second most famous mathematician born on April 28, 1906 so we will celebrate him a day early.

In complexity Rado is best known for the Erdös-Rado Sunflower Lemma. A sunflower is a collection of sets S₁,…,S_k such that any two have the same pairwise intersection, i.e., for all 1 ≤ i < j ≤ k, S_i∩S_j=S₁∩S₂. A Venn diagram of these sets would look like a sunflower.

The sunflower lemma states that given any collection of m distinct sets of cardinality s with m>s!(k-1)^s, there is a subcollection of size k that forms a sunflower. The size of the universe plays no role in the statement of the lemma.

The proof is a nice induction once you figure out the right variable to induct on. Try it yourself or read it here.

The sunflower lemma has played a major role in many results in computational complexity, most notably in Razborov's proof that clique does not have small monotone circuits.

Overheard

"…which also gives better heuristics for the Traveling Salesman Problem."

"Don't you mean the Traveling Salesperson Problem?"

"No, the Traveling Salesman Problem. A traveling saleswoman would have asked for directions."

Theory and Systems

An anonymous graduate student asks

Why do theory students have to take systems courses?

Most American Ph.D. programs have distributions requirements where every student must take courses and/or exams in many different subfields of computer science. Why have these distribution requirements and in particular why should theory students need to know systems concepts they feel they will never use.

• If a student becomes an academic computer scientist they will have to evaluate systems candidates for hiring and tenure and better they can tell the difference between good systems and bad systems.
• Just like theoretical physicists should do some experimental physics to realize what they do should have some grounding in reality, all computer scientists should do some programming to get a better feeling about the concept of computation.
  The mission of computational complexity is to understand the power of efficient computation and how can one really understand efficient computation if they don't try to do it themselves.
• A good systems class will surprise many theory students by showing that much of systems have a strong theoretical underpinning and basic concepts like abstraction underlies both theory and systems. Some very good theoretical work has arisen from questions from the systems community and vice versa.

Many new Ph.D. students make the mistake of trying to fulfill all of their distribution requirements as soon as possible. But this makes the beginning of the Ph.D. program feel like an extension of undergraduate education. Better to take the courses over time and get involved in research as soon as possible.

I did receive my Ph.D. in Applied Mathematics and didn't have a systems requirement. But I did take systems classes as an undergrad and during my first year at Berkeley and I did extensive programming in high school and during my undergrad days. Programming has helped me tremendously in my research. Putting together old theorems to make new theorems is not unlike making different pieces of code work together.

One might also ask why theory students should take AI courses? I'll leave that to a future post.

One Miserable Year

Luca and his commentors get dreamy-eyed over Berkeley but not everyone has such fond memories of that place.

I arrived in Berkeley for graduate school in August 1985. When I went to the off-campus housing office, there was dead silence as hundreds of people looked over a small number of listings. A TV news crew arrived to interview some students who had been looking for months for a place. The ridiculous rent-control laws of the city led to an incredible housing shortage. I ended up moving into a dorm at Mills College, thirteen miles from campus.

The city had a horrendous homeless problem which meant you couldn't walk down the street without being constantly asked for money. Berkeley, home of the free speech movement, was in fact the most intolerant place I have ever been to. Many ads for housing, jobs and the school newspaper required applicants to be "politically correct". And my favorite: A man drops garbage on the front lawn of City Hall, calls it art, and there is an actual debate on whether the town has the right to remove it.

Initially I didn't fit in well socially with the other theory students, partly because I lived so far from campus and didn't have an office my first semester, and party because I didn't fit well into their culture. I broke my finger playing touch football with my dormmates. Some theory students thought I made the story up, how could I be so foolish to play such a game. Others said "serves you right".

I nearly dropped out of graduate school that year. When my advisor, Michael Sipser, decided to move back to MIT I happily followed him.

I did have some good experiences from that year in Berkeley. Many of my fellow graduate students at that time are now some of the leaders in their fields and I consider many of them good friends. MSRI had a special year that year on Computational Complexity with many visitors and seminars. Berkeley hosted STOC and the very first Conference on Computational Complexity (then called Structures), a conference that would become an important part of my life. And I can't deny Berkeley has great food.

The following fall at the MIT theory group picnic we played touch football. I found where I belonged.

Student Weblogs

A few days ago I put a look of horror into one of our graduate students when I went up to him and simply said "You should be careful about what you write in your weblog."

The number of weblogs continue to grow and more and more students are starting to put their thoughts online. Many of them write brutally honest opinions of some of their academic and non-academic experiences or just write very silly or nasty stuff about themselves or each other.

You might think that only the fellow students you have told about your weblog read your weblog, but chains of links are easily followed. Many of us also have automated searches; if you link to my weblog or use the phrase "Computational Complexity", I'll see what you have said. If you really want to limit your readership you can put in some password protection and I strongly suggest that you do so.

Luckily for the student above, I just laugh off such weblog entries, but they can come back to haunt you. When you apply for jobs, you will get Googled and your odd weblog entries can count against you. Deleting your entries off the internet does not necessarily make them disappear, they might have been downloaded or cached.

Just remember when you write your next post, the Internet never forgets.

Favorite Theorems: Small Sets

March Edition

In 1976, Juris Hartmanis and Leonard Berman defined the isomorphism conjecture: For all pairs of NP-complete sets there is a reduction from one set to the other that is 1-1, onto, polynomial-time computable and polynomial-time invertible. As a corollary to the conjecture all NP-complete sets must have many strings in them. They asked whether there could be any NP-complete sparse sets, where a set is sparse if the number of strings of length n is bounded by n^k for some k.

Steve Mahaney in 1982 settled this second question.

Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis by Steve Mahaney, JCSS 1982.

Mahaney's theorem states that if P≠NP then there are no sparse NP-complete sets.

Before Mahaney, Piotr Berman (no relation to Leonard) in 1978 showed that there can't be NP-complete Tally sets, where a tally set is a subset of 1^*. Steve Fortune extended this work to show that co-NP cannot have sparse complete sets. (These results assume P≠NP.)

To adapt Fortune's techniques for NP-complete sets, Mahaney had to find a way to know when strings were not in the sparse set. If one knew how many strings were in the set, and one found all those strings then you knew the rest were not in the set. Mahaney then just showed you could try all possible sizes of sparse sets. This neat idea of finding what's not there by finding everything that is there played a role in many future results in complexity, most notably in the proof that nondeterministic space is closed under complement.

In 1991, Mitsu Ogihara and Osamu Watanabe give a simpler proof using Left Sets, the set of pairs (φ,w) such that w is lexicographically smaller than some witness for φ. Ogihara and Watanabe's paper also extends Mahaney's theorem to show that a reduction from SAT to a sparse set that asks only a constant number of queries would imply P=NP. Whether a reduction using O(log n) queries implies P=NP remains open, even in relativized worlds.

Ham Radios, Coding Theory and the Internet

Venkat Guruswami talked at TTI last week giving an overview of recent work in list decoding. Someone asked him about practical applications of his work and he mentioned ham radio operators now able to error-correct signals bounced off the moon.

My memories of ham radio go back to summer camp. As one of the activities, we could go to a trailer with the Ham Radio Guy (who looked something like this) and we would try, not always successfully, to reach other ham radio operators around the world using Morse code and occasionally voice. Plastered around the trailer were postcards from other ham radio geeks he did talk to.

Ham radio was sort of a precursor to the Internet, which begs the question—Why hasn't the Internet made ham radio obsolete? You get much better bandwidth over TCP/IP than bouncing signals off the moon and you don't need a license to use the Internet.

The iCal Effect

The iCal standard allows sharing of events and calendars. The standard has been around for many years and has been popular with Apple users but the new Google Calendar will become the first popular cross-platform system to support the standard. While several sharable calendars already exist, we should see a dramatic growth in the use of this standard.

How would I like to see the iCal standard work in our community?

• Academic Departments can put their seminar calendar in the iCal format. No longer would I have to subscribe to email list to see events and then have to enter the events that I care about into my calendar manually.
• Any email that announces an event or meeting should have an attachment I can click that adds it to my calendar.
• Conferences could create calendars listing the important dates (submission, notification, proceedings version, registration) as well as the dates of the conference, perhaps even having the schedule of talks in iCal format with links to the papers. (I don't think iCal supports links but hopefully some later version will).
• One might also want a theory iCal calendar listing all conferences but this would likely have too much information to be useful.
• I have wasted much time trying to schedule meetings. Ideally I'd like a system that searches everyone's calendars and finds a common free time.
• As with many standards there are some great applications not initially anticipated but will develop over times.

Google with this Calendar and also their Talk program embrace standards where other related companies have not. Early standards like FTP, SMTP (email), HTTP, and HTML have allowed the Internet to grow to the force it is today. The RSS standard has allowed sharing of information in unprecedented ways. The iCal standard will help us save time scheduling time.

Microsoft Academic Search

Microsoft just announced their Academic Search, a direct competitor to Google Scholar. Scholar is incredibly useful at tracking down electronic versions of documents but using it to find bibliographic information can be frustrating. Here Academic Search shines, hold your mouse over an entry and the right pane gives the bibliographic information including abstract and you can also get a Bibtex or Endnote version. But actually downloading a paper requires more clicks than Google.

I tried some random searching and Academic Search is missing many papers. But it does index some Elsevier papers, where Google never got the rights. But there is a back door in Google via ACM. For example, do a Google Scholar search on Occam's Razor, click on the Blumer et. al. paper and it will bring up the ACM Digital Library page that indexes the Information Processing Letters article. Click on the DOI bookmark and it will take you to Elsevier's page.

In short Microsoft has the much nicer interface but not yet the breadth of articles. If your sole goal is to download the paper, better to use Google.

A little less related to academics, you might want to check out Google's just released Calendar. Looks impressive.

Gödel Prize

The EATCS has announced the winners of the Gödel Prize: Manindra Agrawal, Neeraj Kayal and Nitin Saxena for their paper Primes in P.

I started this weblog shortly after the announcement of the Primes in P result which was the topic of my third post. Now the result has won the award for best recent journal paper. Either that was a very quick process or I have been writing this weblog too long.

What Math to Take?

A good reader question.

I was curious if you had any discussions on what kind of math background new graduate students need to have? For instance, if the undergraduate institution did not have a good math program to support the CS curriculum, what specific topics should students self-study before going to graduate school?

Most importantly you should have some familiarity with mathematical proofs. Mathematical maturity is more important than specific knowledge in any single topic.

Theoretical computer science is mostly discrete mathematics and other areas of discrete math play an important role: Discrete probability, combinatorics, algebra especially group theory, logic and number theory.

Depending on your interests analysis, measure theory, topology and algebraic geometry might be important. Almost every branch of mathematics has played some role in theoretical computer science.

I don't mean to scare you. As I said best to take any real math course (one with proofs, not just Plug-and-Chug Engineering math) and you can later pick up more specific math knowledge when you need it.

Reviewer Ethics

When you are asked to referee a paper you need to follow a set of ethical guidelines that are rarely spelled out and often ignored. Here are the rules as I see them.

The same ethical rules apply to refereeing papers or reviewing manuscripts for conferences. By "editor" I mean whomever asked you to referee or review the paper.

You should not review a paper co-authored by yourself, a member of your institution, someone you are related to, or having relations with. It is fine to referee papers by recent co-authors or by your former advisor or students. The conflict rules are not transitive, you can referee a paper by someone else at your brother's institution. If for any reason you do not feel you can give an unbiased review of the paper, discuss your issues with the editor or just refuse to referee the paper.

You should only discuss the paper with the editor. The fact that you are a referee, or even that the paper was submitted is confidential information. You should not ask someone else to look at any part of the paper without the editor's permission. You must never ever contact the authors directly.

If the paper has not yet been publicly announced, you must follow Rule Number One

Other than reviewing the paper you must ignore the paper completely for any other purpose, including your own research, until the paper appears.

If you find a simple extension or simplification of the paper: Tell the authors through the editor, they will likely add it to their paper and give you credit through a nice acknowledgment to the "anonymous referee."

If you find a significant extension to the paper: Shame on you, you have already violated Rule Number One. Best thing at this point is to wait until the paper appears and then write your extension. If the authors or someone else beats you to it, or the papers never appears, that's what you get for violating Rule Number One.

You also have put yourself in a messy situation since you are now no longer unbiased in the outcome of the paper. If you think there is a significant extension, mention the possibility in your report or keep it to yourself but don't work on it. It only leads to trouble.

The Life of the Party

From Jay Leno's monologue on Monday's Tonight Show

Scientists have been working on a device that will tell when you are boring or irritating in social situations. Who really needs this device?…Scientists.

Normally I'd complain about such stereotypes, but social grace is just not one of our strengths.

How Many Students?

From an assistant professor comes a question

How many Ph.D. students should a professor advise?

There is no single answer. The usual constraints are time and money. It depends on one's teaching, administrative and other time constrains (such as advising Master's and Bachelor students) as well as the ability to fund such students. Also how do you count part-time students, students not in residence, students you officially or unofficially co-advise and students from other schools who are long-time visitors at your institution.

I ideally like to advise three full-time Ph.D. students at any one time. More and I find it difficult to find interesting research problems for the students and not enough time to properly help their research along.

Some professors can handle more students, some should never advise any students. Particularly in the more applied areas of computer science, professors need a considerable number of slaves graduate students to help them with their projects. It's much easier to tell someone what to code than what to prove.

The Terror of the Unabomber

Ten years ago today federal agents went to a remote cabin outside Lincoln, Montana to arrest one Theodore Kaczynski, also known as the Unabomber.

Just a couple of months before I started graduate school at Berkeley in 1985, one of the students in that department, John Hauser, picked up a package in the computer science lab that detonated and cost him some fingers and his vision. We all had heavy warnings about opening packages during orientation, what a way to start graduate school.

I didn't think much about the Unabomber again until 1993 when Yale University CS professor David Gelernter was injured when a package exploded in his hands. At this point the FBI sent major alerts to all of the CS departments including Chicago and started interviewing faculty about former students. The Unabomber became the main topic of discussion and many of us became very careful about opening any package until his capture in April 1996.

Many students today have never heard of Kaczynski or the Unabomber as he safely spends the rest of his life behind bars. But this mathematician turned bomber made us quite scared and paranoid back in the mid-90's.

Baseball is Back and All is Good in the World

The Chicago White Sox have raised their championship banner and started a new season with a rain-delayed win.

A team wins the World Series, their first in 88 years, and the main story in the following spring is whether they can win it all again. Similarly, you could prove a major theorem, answering an 88 year-old question, and a few months people will ask what you've done lately.