Thursday, September 04, 2003
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 (2n-1) of the strings of length n.
Think about it. I'll post the proof next week.
Tuesday, September 02, 2003
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
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
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.