Date of Degree
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.
Liu, Naifeng, "Evaluation of Symmetric Functions and Boolean Functions over Stochastic Input" (2023). CUNY Academic Works.
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.
See the GC’s lending policies to learn more.