[Colloquium] Beygelzimer talk this Friday 12:45 at TTI

[Meridel Trimble]

TOYOTA TECHNOLOGICAL INSTITUTE TALK 

Speaker Alina Beygelzimer
TJ Watson Research Center, IBM

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

Time: 12:45pm
Date: Friday, February 13th, 2004
Place: TTI-Chicago (1427 East 60th Street, Second Floor - Press Building)
LUNCH PROVIDED

Title: Pruning the Search Space for the Determinant and the Rank is Hard

Abstract: 
We show that it is as hard to substantially prune the search space for the
determinant and the rank functions as to compute them exactly. For example, if
there exists a logspace machine that, given an integer matrix, reduces the
number of possibilities for the determinant of this matrix to polynomially many,
then another logspace machine can determine which of the remaining values is the
determinant. We show a similar hardness result for the rank function. Joint work
with Mitsu Ogihara.
 
If you have questions, or would like to meet the speaker, please contact Meridel
at 4-9873 /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