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.

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.

--
Posted by Lance to Computational Complexity at 6/02/2006 07:30:00 AM

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.

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.

--
Posted by Lance to Computational Complexity at 6/04/2006 07:12:00 PM

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.

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.

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

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

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?

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.

--
Posted by Lance to Computational Complexity at 6/08/2006 03:49:00 PM

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.

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.

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.

--
Posted by Lance to Computational Complexity at 6/14/2006 10:04:00 AM

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.

--
Posted by Lance to Computational Complexity at 6/15/2006 06:53:00 AM

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.

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.

--
Posted by Lance to Computational Complexity at 6/16/2006 07:58:00 AM

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.

--
Posted by Lance to Computational Complexity at 6/19/2006 06:03:00 AM

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.

--
Posted by Lance to Computational Complexity at 6/21/2006 08:16:00 AM

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.

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.

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.

--
Posted by Lance to Computational Complexity at 6/22/2006 11:31:00 AM

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)

--
Posted by Lance to Computational Complexity at 6/24/2006 05:06:00 PM

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.

--
Posted by Lance to Computational Complexity at 6/26/2006 09:39:00 PM

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.

--
Posted by Lance to Computational Complexity at 6/28/2006 05:13:00 AM

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.

--
Posted by Lance to Computational Complexity at 6/29/2006 02:49:00 PM

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.

--
Posted by Lance to Computational Complexity at 7/03/2006 12:23:00 PM

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.

--
Posted by Lance to Computational Complexity at 7/03/2006 12:23:00 PM

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.

--
Posted by Lance to Computational Complexity at 7/06/2006 03:52:00 AM

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.

--
Posted by Lance to Computational Complexity at 7/07/2006 12:02:00 PM

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.

--
Posted by Lance to Computational Complexity at 7/07/2006 12:02:00 PM

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

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.

--
Posted by Lance to Computational Complexity at 7/10/2006 09:18:00 AM

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.

In Amsterdam I always go for the Uitsmijter (literally "Bouncer", like at a club), basically an open-faced sandwich with fried eggs on top. I usually go for the Rostbief Uitsmijter and the Ham-Kaas version (Ham and Cheese and the Eggs) can really clog those arteries.

But the Uitsmijter is downright healthy compared to the Porto delicacy Francesinha ("Little French Girl"). One starts with a thick slice of bread then add layers of ham, steak and sausage. Cover with another slice of bread and pour melted cheese on top. Then add the fried egg and smother the whole thing in gravy. Right now Porto is having their Festa da Francesinha by the river where restaurants from all over the city come to offer their versions of the Francesinha.

Luis Antunes says "A little bad food is good for stomach every now and then." After eating a Francesinha at lunch today I'm not sure my stomach agrees.

--
Posted by Lance to Computational Complexity at 7/13/2006 12:43:00 PM

Theoretical computer science (TCS) asserted in the 1960s that Turing machines (TMs)—introduced by Turing to help show the limitations of mathematical problem solving—provide a complete model of computer problem solving by negating Turing's claim that TMs could solve only functional, algorithmic problems. The TCS view ignored Turing's assertion that TMs have limited power and that choice machines, which extend TMs to interactive computation, represent a distinct form of computing not modeled by TMs.

In the 1960s theorists (such as Martin Davis of New York University) adopted the inaccurate assumptions that "TMs completely express computer problem solving" as a theoretical (mathematical) foundation of the computing discipline. The TCS model is inaccurate because TMs express only closed-box functional transformation of input to output. Computation is not entirely mathematical, since broader models of thinking and research are needed to express all possible scientific and engineering questions. Computational problem solving requires open testing of assertions about engineering problems beyond closed-box mathematical function evaluation.

But more importantly Wegner and Goldin misinterpret the Church-Turing thesis. It doesn't try to explain how computation can happen, just that when computation happens it must happen in a way computable by a Turing machine.

I admit the original single-tape Turing machine does not model interaction as Wegner and Goldin state. Nor does the Turing machine model random-access memory, machines that alter their own programs, multiple processors, nondeterministic, probabilistic or quantum computation. But what that single-tape Turing machine can do is simulate the computational processes of all of the above. Everything computable by these and other seemingly more powerful models can also be computed by the lowly one-tape Turing machine. That is the beauty of the Church-Turing thesis.

The ongoing support for rationalist over empiricist modes of thought (despite repeated questioning by some philosophers) suggests that human thinking is inherently more concerned with the rationality of human desires than with the empirical truth of human reasoning. Our empirical analysis of interactive problem solving continues to be criticized by incorrect rationalist arguments about the strong problem-solving power of TMs, which are accepted as the proper form of valid reasoning, even though they were contradicted in 1936 by Turing himself.

We hope you accept that empirical (open) reasoning is often more correct than rationalist (closed) arguments, and that modes of thought about truth and problem solving should promote empiricist over rationalist reasoning, as well as definitive truth over questionable a priori value judgments.

Blogging will likely be light this week as the conference keeps me busy and I once again have limited Internet access.

One of the students in Chicago had planned to go yesterday to Israel to work for a month with Eldar Fischer at the Technion in Haifa. He postponed his trip, no so much because of the danger, but because getting to Haifa has become very difficult and the University has temporarily closed. The Technion, aka The Israel Institute of Technology, has by far the largest collection of theoretical computer scientists at any single university. Haifa University also has a nice theory group. We sincerely hope the situation resolves itself quickly and they can return to a sense of normalcy, as normal as one gets in that region.

--
Posted by Lance to Computational Complexity at 7/17/2006 02:30:00 AM