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.

One-Way Functions

What is a one-way function, intuitively a function that is easy to compute and hard to invert? Taking this intuitive idea to a formal definition has yield two quite different meanings, sometimes causing confusion.

The first directly tries to translate the intuition. A function f is one-way if

1. f is 1-1 (so an inverse is unique),
2. f is length increasing (so the output of the inverse function is not too large),
3. f is computable in polynomial time, and
4. there is no polynomial-time computable g such that for all x, g(f(x))=x.

This is a nice clean definition that fulfills the intuition but is not that useful for cryptography, since f could be easily invertible on all but a small number of inputs, or with stronger adversaries. To handle these issues we have a different looking definition.

A function f is r(n)-secure one-way if

1. There is a function l(n)≥n such that f maps strings of length n to strings of length l(n),
2. f is computable in polynomial time, and
3. for all probabilistic polynomial-time algorithms A, the probability that f(A(f(x)))=f(x) is at most r(n) where the probability is taken over x chosen uniformly from the strings of length n and the random coins used by A.

There are many variations on both definitions and a considerable amount of theory devoted to each. Grollmann and Selman show that one-way functions of the first kind exist if and only if P ≠ UP. On the other hand Håstad, Impagliazzo, Levin and Luby show that from any one-way function of the second kind, one can create a pseudorandom generator.

At one point I tried using complexity-theoretic one-way functions and cryptographic one-way functions to distinguish the two, but this only caused confusion. So we have to live with the fact that we have these two definitions with the same name and we'll have to just use context to figure out which definition is appropriate. If you give a talk or write a paper about one-way functions, it never hurts to distinguish which version you are talking about.

A Speech and A Weblog

UCLA Professor Andrew Kahng gave this wonderful speech to the incoming computer science graduate students. While designed for UCLA, with minor changes it applies to every research institution. Every graduate student or anyone interested in graduate school should read it.

Michael Nielsen, coauthor of my favorite book on quantum computing, has his own weblog. Worth checking out.

Proof, The Movie

We just got email that Proof, a movie adapted from the play, will be filmed in and around the University of Chicago campus over the next few weeks. I saw the play a couple of years ago in New York, a powerful story about an aging mathematician and his daughter. Given the cast, director and source material I would expect great things from the film version as well, and it certainly should best out the last movie I remember them filming here.

Turing, The Novel

Christos Papadimitriou has been exercising his creative talents. He has a new book Turing (A Novel about Computation) building a love story around some of Turing's lectures. He is now working on Logicomix, computer science in comic book form. I can imagine it now, our hero NP-Man and his trusty sidekick P-Girl battle the evil Execution Time.

The Buzz

There has been some buzz about the paper Resource Bounded Unprovability of Computational Lower Bounds by Tatsuaki Okamoto and Ryo Kashima. They claim to show that no polynomial-time machine can produce a proof of a super-polynomial-time lower bound for NP and as a consequence there is no proof that P≠NP in any reasonable proof system such as Peano Arithmetic. The first part I don't really understand but the latter would be a major breakthrough.

But don't get too excited. I have heard from multiple sources that Razborov has found serious problems in their paper, in particular that Theorem 22 is just false. So as one complexity theorist put it, "This is probably not the most important paper on your stack."

Creative Commons

In a conversation I had last week, a professor planned to use slides from lecture notes he found on the web in his own slides. He planned to give attribution to the original producers of the slides but did he need to contact them beforehand for permission. Technically yes, material put on the web is copyrighted by default. But if he sent them email most responses would be of the form, "Please don't waste my time!"

To deal with this issue, Creative Commons has a nice service giving an easy way to release some rights for online material. So I've added a link on the left column of the web log that basically allows you to modify and distribute the material in this weblog for noncommercial use with attribution. No need to ask me, not that anyone has.

On another note, I'm on vacation next week and off the internet. Back after that.

Balanced NP Sets

Last week I posed the following question:

(1) Exhibit an NP-complete language L, such that for all lengths n≥1, L contains exactly half (2^n-1) of the strings of length n.

This question was posed by Ryan O'Donnell and solved by Boaz Barak. Here is a proof sketch.

By using standard padding and encoding tools, (1) is equivalent to

(2) There is an NP-complete language L and a polynomial-time computable function f such that for every n, there are exactly f(n) strings in L of length n.

First we show how to achieve (2) if we replace "strings" with "total witnesses." Consider pair of formulas φ and ¬φ. The total number of satisfying assignments between them total 2ⁿ if the have n variables. We just create an encoding that puts φ and ¬φ at the same length. The total number of witnesses at that length is equal to 2ⁿ times the number of formula pairs encoded at that length.

We now prove (2) by creating a language L that encodes the following at the same length for each φ

1. φ, where φ is satisfiable.
2. (φ,w) where w is a satisfying assignment for φ and there is another satisfying assignment u<w for φ.

You can check that the language is NP-complete and the total number of strings in L for each φ is just the number of satisfying assignments of φ.

Is P versus NP formally independent?

As promised back in March, the October 2003 BEATCS Complexity Column is on whether we can truly settle the P versus NP question. Scott Aaronson gives quite an interesting survey on this topic.

STOC 2004

I have received some requests for the call for papers for STOC 2004 which will be held in Chicago. Maybe it is because I gave the presentation for STOC 2004 at the 2003 business meeting, or because if you google 'STOC 2004' this weblog comes up in the list, or just because I'm in Chicago now, but I am not officially connected to STOC 2004.

Having said that, here is the tentative call for papers.

Institute of Advanced Study

The Institute will be quite a complexity powerhouse this year. In addition to IAS fixtures Wigderson and Razborov, visiting are Russell Impagliazzo, Manindra Agrawal (with his students Kayal and Saxena at Princeton) and postdocs Boaz Barak, Subhash Khot, Ryan O'Donnell and Nate Segerland. These are just the ones I met yesterday during a short visit several weeks before their semester officially begins. We'll expect great things from them.

Here is a question we thought about yesterday, posed by Ryan O'Donnell and ultimately settled by Boaz Barak:

Exhibit an NP-complete language L, such that for all lengths n≥1, L contains exactly half (2^n-1) of the strings of length n.

Think about it. I'll post the proof next week.

Scheduling Research

A colleague of mine, who shall remain nameless, likes to schedule time for research, a certain set block of time during the day where he puts off all his todo's and concentrates on science. Sounds good but often his chair will stop by for some discussion or an impromptu meeting. The colleague will say, "Sorry, but I reserved this time for research", but that argument didn't fly, the chair said he could do research anytime. One day he said instead, "Sorry I have a squash game" and the chair replied that they would talk at a future time. Welcome to the academic world, where research gets trumped by a meeting that itself can be trumped by a squash game.

Is scheduling time for research a good idea? It depends on your personality and your research style. If you find yourself with no time to think about an interesting problem because too much else is happening then yes, best to schedule a few hours where you promise yourself you will do nothing else but research during those times. This means more than not preparing for class but also ignoring your computer. Checking email and surfing the web are themselves great time sinks.

In my case, I find it difficult to just start thinking about research at a given time. So I use the rule that research trumps all and when inspiration hits me, or someone comes to my office with a research question, I drop everything I can to work on the problem. Okay, I can't skip a class for research but email, weblog posts, referee reports, etc., should never stand in the way of science.