Evan Brody

Global Challenge: Algorithms for Stochastic Function Evaluation

Abstract:

Many situations require performing pre-defined actions sequentially in order to answer a question of interest. For example, a doctor may have a range of medical tests available, each with potential informative value towards some diagnosis; a rescue operation may have a set of possible locations to search to determine the number of survivors that can be saved; antivirus software analyzing a potentially malicious program may have numerous sections of code it could test to determine the program’s safety.

 In these types of situations, the question naturally arises: what ordering minimizes the expected number of necessary actions? Mathematically abstracted from a range of distinct but related applications, these situations are classified as stochastic sequence ordering (SSO) problems. Our research focuses on the design of algorithms for SSO problems. We have two criteria for an SSO algorithm, which must be provably met under any possible input: it must run efficiently with respect to the problem’s size, and it must produce a strategy which is either exactly or approximately optimal. If an algorithm’s ordering is guaranteed to require at most, in expectation, k times the number of actions as the optimal ordering, the algorithm is a k-approximation algorithm. We present an O(log Q)-approximation algorithm for nonadaptively evaluating any discrete function of independent stochastic inputs, where Q is a measure of the complexity of the function in question known as its goal value.

We apply this result to the problem of evaluating the Coupon Counting Function, obtaining an O(log d)-approximation algorithm, where d is the number of coupons. We generalize this to a closely related but more difficult function, the Coupon Collection Function, to obtain a max{O(log d), n/(n - d)}-approximation algorithm. We also present a 1-additive approximation algorithm for evaluating the related d-ary Unanimous Vote Function.

Bio:

Evan Brody received BS degrees in mathematics and computer science from NYU Tandon in the spring of 2026, and will pursue a PhD in theoretical computer science at Brown University from fall 2026 onward. He originally hails from Tunkhannock, a small town in the Pennsylvanian stretch of the Appalachian mountains.

Evan spent the summer of 2023 participating in the NSF REU in Cloud Computing Security & Privacy at Boise State University. In the summer of 2024, he participated in the NSF REU in Industrial Mathematics and Statistics at Worcester Polytechnic Institute.

From the spring of 2025 through 2026, Evan worked closely with Prof. Lisa Hellerstein of the Theoretical Computer Science Group at NYU on the design and analysis of algorithms for stochastic combinatorial optimization; specifically, their work focused on algorithms for optimally, or near-optimally, sequencing queries or probes. This included full-time participation in the NYU Tandon Undergraduate Summer Research Program in the summer of 2025.

Over the summer of 2026, before beginning his PhD, Evan interned in the Multiphysics Modeling and Flows Group at Oak Ridge National Laboratory.

Evan is also interested in mentorship and teaching. From his junior year onward at Tandon, he worked as a recruiter for GLASS and as a teaching assistant for Object-Oriented Programming (CS-UY 2124). In the fall of 2025, he was also a teaching assistant for Artificial Intelligence (CS-UY 4613).