[Johan Hastad delivers a survey talk revisiting classical questions in circuit complexity that have been open for decades. Russell Impagliazzo asks a questions at the end]
R.I.: Johan, is there any problem in circuit complexity that you think is open not because it is so hard but because it has been overlooked, people haven’t thought so long about it, and maybe it is more tractable?
J.H.: if I knew of such a problem, I would solve it.
Most, but by no means all, things are cheap in Beijing. Some examples:
The number 8 is considered lucky in Chinese popular culture. The Beijing Olympics, for example, took place in August, which is not the best month to be here, so that the opening ceremony could start at 8:08pm on August 8, 2008.
United Airlines, which has a major hub in San Francisco, labeled its daily flight from Beijing to San Francisco the flight United 888. The flight from San Francisco to Beijing is United 889. Without looking (no cheating!) guess what is United flight 887?
It is now possible to register for FOCS 2010. The early registration rate is until the end of September.