ARC Colloquium: Viswanath Nagarajan (University of Michigan)

Algorithms & Randomness Center (ARC)

Viswanath Nagarajan (University of Michigan)

April 3, 2023

Klaus 1116 - 11:00 am

Title: Stochastic Score Classification and Halfspace Intersection

Abstract: In sequential testing, we have a complex system with several components, each of which is "working" or "failed" with some independent probability. We are interested in evaluating the system status, which is a function of the statuses of its components. The goal is to design a policy that minimizes the expected cost of testing. Prior work has mainly focused on simple functions like k-of-n and halfspaces. We consider more general "score classification" functions, and provide the first constant-factor approximation algorithm. Our result improves over a previous logarithmic approximation ratio. Moreover, our policy is non adaptive: it just involves performing tests in an a-priori fixed order. Finally, in computational experiments on random instances, we observe that the cost of our algorithm is typically within 50% of an information-theoretic lower bound.  



Speaker's Webpage 

Videos of recent talks are available at: and

Click here to subscribe to the seminar email list:

Event Details


  • Monday, April 3, 2023
    11:00 am - 12:00 pm
Location: Klaus 1116