Dissertations, Theses, and Capstone Projects

Date of Degree


Document Type


Degree Name



Computer Science


Devorah Kletenik

Committee Members

Arash Asadpour

Mayank Goswami

Lisa Hellerstein

Rohit Parikh

Subject Categories

Discrete Mathematics and Combinatorics | Theory and Algorithms


Algorithms, Decision under Uncertainty, Approximation Algorithms, Adaptivity Gap, Query Complexity


In our daily life, we often face situations where we need to make precise judgments based on initially unknown information, while gathering all the evidence to make informed conclusions can be very costly. In this dissertation, we explore the problem of optimizing the decision-making process under uncertainty, and we focus on problems that can be found in both theoretical computer science and discrete mathematics. The primary goal is to develop approximation algorithms with guaranteed worst-case performance. These algorithms aim to minimize the expected cost of acquiring information necessary for evaluating fundamental functions, such as Boolean and symmetric functions. Furthermore, we examine the adaptivity gaps for evaluating some typical Boolean functions, highlighting the critical need for incorporating adaptivity into the decision-making process for these problems. Our research contributes to a deeper understanding of the underlying concepts, and hopefully also paves the way for the development of more effective and efficient decision-making strategies in the face of uncertainty.

This work is embargoed and will be available for download on Tuesday, September 30, 2025

Graduate Center users:
To read this work, log in to your GC ILL account and place a thesis request.

Non-GC Users:
See the GC’s lending policies to learn more.