Posted by Dr Serena Coetzee on 3 Feb 2010, 13:18 (last modified on 18 Feb 2010, 08:18)

Eric Allender from the computer science department of Rutgers University (New Jersey, USA) is currently visiting South Africa on the basis of a Fulbright Fellowship. He already visited the University of Cape Town, as well as UNSIA, and he will also visit our CS department here at the University of Pretoria very soon. His main research area is computational complexity theory. In this context, Eric Allender is going to give a guest lecture on the 23th of February (15:00-16:00h), to which visitors are welcome. The topic of his lecture will be: "Chipping away at P versus NP - How Far Are We from Proving Circuit Size Lower Bounds?"

Abstract: There is widespread consensus that one of the most challenging and important problems in computer science is to show that certain problems cannot be computed by small circuits. Eric Allender's lecture will review why proving circuit size lower bounds is so important (and will also review the relationship between this problem and the P versus NP problem), and will also discuss some of the reasons why there is such widespread pessimism about the likelihood of proving superpolynomial circuit size lower bounds any time in the near future. Eric Allender will also present some recent developments that suggest that there might be reason to be more hopeful about the prospects for proving lower bounds.