[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.
5 comments
Comments feed for this article
September 16, 2010 at 7:48 pm
Anonymous
I guess Hastad had not heard of the Linial-Nisan conjecture. That was not so hard (in retrospect).
September 23, 2010 at 9:33 am
Anonymous
Was this a recent talk – if so, where and when? I’m curious to know what the classical questions are that Johan considers interesting…
October 1, 2010 at 6:13 pm
a b
put ur thru thous…
–
October 14, 2010 at 4:04 am
not quite chinese
Funny but problematic answer. There are always such problems, and I’m sure Hastad knows of a few, though maybe not off the tip of his tongue.
October 16, 2010 at 8:20 pm
not quite american
hi not quite chinese. Wat does it mean to be chinese ? are you chinese ? why are u saying this ? why did you never convert to chinese ? where are you these days ? do you have an up to date website ? hello ?