[Colloq] Talk by Emanuele Viola at BU, Friday, Oct. 24

[Rachel Kalweit]

                                The Inaugural
                       Boston University - Northeastern
                        Theory of Computation Seminar
                                Emanuele Viola


This Friday, Oct 24, at 4:00 Emanuele Viola (Northeastern) 
will speak on
"Polynomials over {0,1}".

The talk will take place in room 138 of 111 Cummington Street at BU.
Refreshments at 3:45.

Abstract:
Polynomials are fundamental objects in computer
science that arise in a variety of contexts, such as error-correcting
codes and circuit lower bounds. Despite intense research, many basic computational
aspects of polynomials remain poorly understood. For example, although it
is known that most functions cannot be approximated by low-degree multivariate
polynomials, an explicit construction of such a function is still unknown.

In this talk we discuss some of the progress we have made towards understanding
computational aspects of polynomials. In particular, we present our recent
result that the sum of d pseudorandom generators for degree-1 polynomials is
a pseudorandom generator for polynomials of degree d.


See http://www.ccs.neu.edu/theory/seminar.html for
future meeting of this
joint BU/NEU Seminar.