Colloquium Details
Max-Throughput for Sequential Testing
Speaker: Lisa Hellerstein, Polytechnic Institute of NYU
Location: Warren Weaver Hall 1302
Date: February 4, 2011, 11:30 a.m.
Host: Mehryar Mohri
Synopsis:
In sequential testing, there are n tests that can be performed on an item, and we need to determine whether the item passes all the tests. Tests are performed sequentially. Once the item fails a test, no more tests are performed. Sequential testing problems arise in a number of fields, including databases (parallel filter ordering), artificial intelligence (satisficing search), and VLSI testing.
We consider the problem of maximizing throughput of sequential testing, in a setting where each of the n tests is performed by a separate processor, in a parallel setting. The processor performing test i can only perform r_i tests per unit time, and the (independent) probability that an item passes test i is p_i. Tests can be performed in different orders on different items, so as to best use the capacity of the processors. The problem is to determine the best assignment of orderings to items, so as to maximize the throughput of items tested.
We begin by presenting a simple O(n2) algorithm for this maximum throughput problem, which finds a sparse, optimal solution. We then present results on the maximum throughput problem with precedence constraints, and discuss the strong relationship that exists between maximum throughput problems, and their associated (and more classical) min-cost problems.
This is joint work with Amol Deshpande.
Speaker Bio:
Lisa Hellerstein has been on the faculty of the Polytechnic Institute of NYU (formerly Polytechnic University) since 1997. She did her undergraduate work at Harvard and received her PhD in Computer Science from the Univ. of California at Berkeley. Prior to joining the faculty at NYU-Poly, she did a postdoc at MIT and was on the faculty at Northwestern University. Her research areas include computational learning theory, algorithms, and complexity, with a focus on problems of learning, representing, and evaluating Boolean functions.
Notes:
In-person attendance only available to those with active NYU ID cards.