[Colloquium] Alina Beygelzimer talk - Mon. 11/24 2:30 at TTI

[Meridel Trimble]

TOYOTA TECHNOLOGICAL INSTITUTE TALK 

Speaker: Alina Beygelzimer 
IBM T.J. Watson Research Center

Speaker’s homepage: http://www.cs.rochester.edu/~beygel/ 

Time: 2:30pm 
Date: Monday, November. 24th, 2003 
Place: TTI-C (1427 East 60th Street, Second Floor - Press Building) 
*REFRESHMENTS PROVIDED* 

Title: Is Ruling Out a Possible Solution as Hard as Solving?

Abstract: We will show that for some natural problems, a slightly non-trivial 
advantage over guessing is as hard to obtain as the solution itself. In 
particular, if one could rule out even a single candidate for the value of a 
given arithmetic circuit on a given input in NC, then this would collapse P to 
NC, i.e., constitute a proof that there are no inherently sequential problems 
in P. The result also holds if one makes mistakes by ruling out the correct 
value, with small probability. 

This is joint work with Mitsu Ogihara.

If you have questions, or would like to meet the speaker, please contact 
Meridel at: 4-9873 or mtrimble at tti-c.org 

For information on future TTI-C talks or events, please go to the TTI-C Events 
page: http://www.tti-c.org/events.shtml