[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.

About these ads