Lessons from the IM Experiment

Last week I started an experiment using instant messaging. I thank the many of you who sent me IMs, a great way for me to meet you, the readers of this weblog. I plan to keep trying IM for a while but I have had learned a few lessons which seem obvious in retrospect.

Instant messaging can be a time sink. I love communicating with people, which is the main reason I keep this weblog going. However, as most academics, I have much going on and can't afford to have many lengthy discussions. I've also learned there is no clean way to end an IM conversation. So please feel free to IM me but don't take it personally if I rudely keep the conversation short.

Just because the nice icon on the home page says I'm online it doesn't mean that I am at my computer and available to chat at the moment. Often I am and I will but if not I will eventually see your message and respond. If there is really is something important that you want to discuss with me via IM we can setup a scheduled time via email. I often do this with phone calls so why not IM too?

I've also discovered IM conversations can be recorded, posted on the web and could be used in a court of law. I need to be careful about what I say.

I have already had some interesting research conversations and ideas for weblog posts via IM. The last post came in part because of some IM questions about the Feigenbaum-Fortnow paper. Email became a powerful research tool when email use hit a critical mass among computer scientists sometime in the mid-late 80's. I believe IM will also follow that curve and I hope to keep ahead of it and perhaps nudge it a little bit.

Changing Strings but not Distributions

Let f be a function that maps Σⁿ to Σⁿ. Let U represent the uniform distribution on Σⁿ and D be the distribution that one gets by applying f to a string drawn from U.

We wish to find f that change x but keep the underlying distribution close to the same, in particular we want the following properties,
(1) Prob(f(x)≠x)≥2/3 when x is drawn from U.
(2) U and D should be statistically close, informally no algorithm making a polynomial number of samples will be able to distinguish, with high confidence, whether those samples came from D or U.

Achieving such an f is easy, consider f that just flips the first bit of x. (1) holds all the time and U=D.

Suppose we add a restriction to f:
(3) In the bits where x and f(x) differ those bits are 1 in x and 0 in f(x). For example, f(011)=010 is allowed, but f(011)=f(111) is not.

An f fulfilling (1), (2) and (3) is impossible. (1) and (3) means that f will reduce the number of ones on most of the strings and taking say n³ samples we will notice a statistical difference in the number of bits which are 1 depending on whether the samples were drawn from U or D.

Suppose we replaced (3) with a weaker restriction:
(3') In the first bit where x and f(x) differ, that bit is 1 in x an 0 in f(x). So f(110)=011 is allowed but f(001)=010 is not allowed.

Can an f fulfilling (1), (2) and (3') exist? Not so clear, but Peter Shor found a simple example: f(0ⁿ)=0ⁿ, and for the other x, f(x)=x-1 where x is viewed as a nonnegative integer written in binary. D is indistinguishable from U yet f changes nearly every string.

These questions are related to an old paper I had with Joan Feigenbaum which has gotten some recent attention because of a nice new FOCS paper by Bogdanov and Trevisan that builds on our paper. The proofs in these papers work partly because (1), (2) and (3) cannot all happen even for arbitrary distributions U. Both papers give a negative result for a nonadaptive case; the adaptive case corresponds to (1), (2) and (3') and Shor's example shows that the proof techniques will not directly lead to a solution in the adaptive case which remain open.

Quantum Leaping to Conclusions

A quantum computing graduate student sent me email over the weekend. He had thought he had proven some surprising results about the class PP and was wondering if he was making some mistake. After some discussion here was his reply:

Ok I get it. Somehow I jumped to the conclusion that P^PP was PP.
There is one more for your blog: A⊆ B implies B⊆ A^B but not A^B⊆ B (duh!)

He goes on to say he made his quantum leap to conclusions since for the quantum class BQP, P^BQP=BQP, he thought the same property must hold for all classes.

I present this because he suggested it for my weblog and as a public service for those who might make a similar mistake. Yes, in case you were wondering, for reasonable classes A (like A=P), B⊆A^B without needing to assume A⊆B.

When Good Theorems Have Bad Proofs

Here is one of my favorite examples of a bad proof for what turns out to be a correct theorem.

Theorem: If NP is in BPP then the whole polynomial-time hierarchy is in BPP.

Let's focus on simply showing Σ₂ is in BPP if NP is in BPP. The rest is straightforward induction. Here is our first proof:

Σ₂=NP^NP⊆ NP^BPP⊆BPP^BPP=BPP. Do you see the problem with this proof?

To get a correct proof (first due to Zachos) we need to use Arthur Merlin games. Consider a Σ₂ language L as an ∃∀ expression. Since NP is in BPP, we can replace the ∀ with a probabilistic test. This gives us what is known as MA or a Merlin-Arthur game where the powerful Merlin sends a message that Arthur can probabilistically verify. A now classic result shows that MA is contained in AM, where Arthur provides a random string to Merlin who must then provide a proof based on that string. Once again we apply the NP in BPP assumption to allow Arthur to simulate Merlin probabilistically and now we have a BPP algorithm for L.

The problem in the first proof is in the second "⊆". The assumption NP in BPP does not imply NP^A in BPP^A for all A.

Talk to Me

How has the internet most affected the study of science? In one word: communication: the ability for scientists to discuss and share their research with each other quickly and cheaply. So I strive to find new ways to use the internet to improve communication. Starting this weblog is one such example. I'd thought I would try another: Instant Messaging.

Now many of you are thinking I am crazy, but for different reasons. Some of you out there have been using instant messaging for years and wondering how I could consider it s "new" technology. But many of you out there have barely figured out how to read your email attachments and have hardly even heard of IM.

On a trial basis, for my weblog readers, I will welcome your instant messages. Talk to me about this weblog, about complexity and computer science in general or about whatever you want. Maybe I'll start a trend and all computer scientists will IM each other. Maybe not but it's worth trying out.

I'm using Yahoo Instant Messaging; my Yahoo id is the imaginative "fortnow" (note: I do not read email sent to fortnow@yahoo.com). I put a button on the left column of the weblog home page that tells you when I am online and you can click to connect. I look forward to hearing from you.

What's happening at the NSF?

There is a big reorganization in the CISE directorate of NSF. To understand what's happening, let's review the previous structure..

The National Science Foundation, like most government bureaucracies, has a tree-like structure. At top is the office of the director (Rita Colwell). Below that are several directorates including the Directorate for Computer and Information Science and Engineering (CISE) headed by Peter Freeman. By law every organization in NSF cannot be just "science" but "science and engineering" except for the Foundation itself.

Below CISE were several divisions, including Computer-Communications Research (C-CR) headed by Kamal Abdali. C-CR ha several programs including the Theory program headed by Ding-Zhu Du.

Peter Freeman, who recently became head of CISE, has decided to reorganize the whole directorate. Exactly what it will become should be announced next week but there are some hints in this presentation. Change is always scary but I'm hopeful theory will survive. I'll give more details when I know them.

To overcome the tree structure of NSF, there are a number of cross-disciplinary programs. One such program, Information and Technology Research (ITR), has produced several large, medium and small grants to a variety of projects, including many applications of theory. This is the last year of ITR solicitations and the calls have been well behind schedule, probably not unrelated to the CISE reorganization. This year's topic will be on "ITR for National Priorities" with more details promised by Thanksgiving. Unconfirmed rumors have the program will be more focused and only making medium sized grants.

TTI

There are two computer science departments on the University of Chicago campus. The one I belong to, a department in the physical sciences division of the University and the other, the Toyota Technological Institute at Chicago (TTI-C). What is TTI-C?

The Toyota Technological Institute, a university covering various engineering disciplines located in Nagoya City, Japan, was founded in 1981 from funds from the Toyota Motor Corporation as directed by the Toyoda family. They decided to start a computer science department and locate it in the states to have a broader access to computer science faculty and students. For various reasons they settled on Chicago and set up an agreement with the University of Chicago, using space in the University of Chicago Press building. TTI-C has just officially started up and have already signed up a few strong faculty members including theorist Adam Kalai and Fields medalist Stephen Smale. TTI-C plans to increase its faculty size and start up a graduate program in the near future.

Although there will be some sharing of courses and a few of our faculty (including myself) sit on a Local Academic Advisory Council for TTI-C, TTI-C will formally maintain itself as a separate institution from the University. Nevertheless close collaborations between our department and TTI-C has already established an exciting research environment for our combined faculty and students.

The Agony of Defeat

This is for my friends in Boston who suggested I do a sports post.

One of the great parts of my job is working with people from around the world. I was working with a graduate student, Luis Antunes, from Portugal when we found out that Portugal would play the US in the 2002 World Cup. We had various rounds of taunting back and forth with me fully knowing the US didn't stand a chance in that match. When the US did win, Luis tells me the whole country went into a deep depression. By contrast, for the most part people in the US didn't care.

I can now understand Portugal's pain as the city of Chicago has gone into a similar kind of quiet depression over the Cubs failure to advance to the world series. Impressive what sports can do to the psyche of a city or a country.

Memo to my friends in Boston: Hope things go well for the Sox so your city doesn't end up feeling tomorrow like Chicago does today.

Tutorials on Machine Learning and Mixing via Markov Chains

Just prior to the FOCS conference, Avrim Blum gave a tutorial on machine learning and Dana Randall gave a tutorial on mixing. As the talks were computerized, even if you, like me, missed the conference, you can view Blum's slides here and Randall's slides here. Randall also has a companion paper that appeared in the proceedings.

Eli Upfal also gave a tutorial on Performance Analysis of Dynamic Network Processes which I haven't found online yet.

Columbus Day

Today is Columbus Day, a minor holiday in the states. There is a great saying about Columbus: He is not famous for being the first person to discover America, rather he is famous for being the last person to discover America.

The same principle holds for proving theorems. Think about it.

Advice for Students Going to a Conference

With FOCS starting this weekend, here is some advice for students attending a conference.

What is the purpose of a conference? Disseminating information is the obvious answer, but there are better ways these days to announce new results. No, the major reason for conferences is to bring a large segment of our community together in one place. Keeping that in mind,

• Meet People: Don't just hang out with students from your own department. Talk to other students, they will be your future colleagues. Don't be intimidated by senior people whose names you have seen on famous papers. Deep down they are just like you.
• Don't go to too many talks: You will burn out and not remember much of anything. And too much time in talks detracts from the main purpose of the conference. Pick and choose your talks based on your research interests, the abstracts in the proceedings and those given by someone with a reputation for giving good talks.
• Go to the business meeting: It will give you a flavor of the inner workings of the theory community. With luck there will be a lively discussion of some arcane issue. And don't forget the free beer.

Remember, networking is as important in academics as it is in business. But perhaps the most important piece of advice I can give: Have fun.

FOCS

Next week is the 44th FOCS Conference in Boston. FOCS, the Symposium on the Foundations of Computer Science is, with STOC, one of the two major American general theory conferences. Okay, usually American. STOC was in Crete in 2001 and FOCS will be in Rome next year but the other 77 FOCS and STOC conferences were held in North America.

I won't be attending the FOCS conference this year, but will definitely be at the next STOC being held in Chicago. I'll likely ask a grad student to pick me up a FOCS proceedings. I'm not sure why; most of the papers are available on-line, the proceedings take up valuable bookshelf space and I've barely opened the proceedings of the last few conferences. But I have a complete set of STOC, FOCS and Complexity proceedings going back to 1986 and I'm a sucker for tradition.

A New Genius

While on the topic of awards, we have a new "genius" in the theoretical computer science community. Computational geometer Erik Demaine just received a MacArthur Fellowship. Congrats!

Waiting for Nobel

The Nobel science prizes will be awarded next week: Medicine on Monday, Physics on Tuesday and Chemistry and Economics on Wednesday. Nothing against the Turing Award and Fields Medal but it is the Nobel that is a household name. Given the increasing connections between computer science and the other sciences, you never know who you might know who might win.

On the Nobel home page one can find some interesting articles on life as a scientist by some Nobel Laureates. Paul Samuelson ends his story with "Always I have been overpaid to do what has been pure fun," which nails the point that the most important requirement to being a successful researcher is to have fun doing it.

Happy Fiscal New Year

I have tried to keep politics out of this weblog with the exception of issues related to science, in particular science funding and immigration. To celebrate America's fiscal new year, let's talk about immigration.

Congress has declined to renew the higher annual cap on H1-B visas, rolling them back to 65,000 for the fiscal year starting today from 195,000 in 2000. H1-B's allow "employers to hire foreign workers with special skills they can't find among American job applicants," typically for high-tech jobs. But H1-B's are also used for visiting researchers at industrial research labs and some university positions. When the limit is reached, the government will no longer issue more visas until the start of the next fiscal year.

At NEC, we had postdocs who had to delay their start date until October for this reason, including in some cases those who wanted to start at the beginning of summer. With the limit dramatically decreased, if the job market starts perking up, we could hit the limit much earlier. This could make a real dent in international cooperation in science.