[Colloquium] Beygelzimer talk today 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 thedeterminant. We show a similar hardness result for the rank function. 
Joint workwith Mitsu Ogihara.
 
If you have questions, or would like to meet the speaker, please contact 
Meridelat 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


Toyota Technological Institute at Chicago