Dissertations, Theses, and Capstone Projects
Date of Degree
9-2023
Document Type
Dissertation
Degree Name
Ph.D.
Program
Computer Science
Advisor
Devorah Kletenik
Committee Members
Arash Asadpour
Mayank Goswami
Lisa Hellerstein
Rohit Parikh
Subject Categories
Discrete Mathematics and Combinatorics | Theory and Algorithms
Keywords
Algorithms, Decision under Uncertainty, Approximation Algorithms, Adaptivity Gap, Query Complexity
Abstract
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.
Recommended Citation
Liu, Naifeng, "Evaluation of Symmetric Functions and Boolean Functions over Stochastic Input" (2023). CUNY Academic Works.
https://academicworks.cuny.edu/gc_etds/5537
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.