Computer Science Thesis Proposal

  • Remote Access - Zoom
  • Virtual Presentation - ET
  • ROIE LEVIN
  • Ph.D. Student
  • Computer Science Department
  • Carnegie Mellon University
Thesis Proposals

Submodular Optimization Under Uncertainty

Submodular functions, which are a natural discrete analog of convex/concave functions, strike a sweet spot between generality and structure: they model an immense variety of applications in computer science and beyond, but, at the same time, are sufficiently well behaved that they can be optimized very effectively in theory and in practice.  Optimization tasks involving submodular functions have classically been studied in settings of complete information, i.e. where the entire input is known upfront. However, such perfect, full-information access to the input is unrealistic in many applications, and indeed designing algorithms under uncertainty has become an important trend in modern computer science.

In this thesis, we study how to design algorithms for submodular optimization in scenarios of incomplete information. We study three different kinds of uncertain environments: (a) Online settings where problem constraints are revealed piecemeal, and the algorithm must commit to irrevocable decisions as it maintains feasibility. The challenge is to make decisions that are robust to the final realization of the problem, even with limited information. (b) Dynamic settings where constraints can not only be added, but also removed over time. The goal is to design algorithms that maintain feasible, near optimal solutions at every stage that are stable, in the sense that they change as little as possible between time steps. (c) Streaming settings where the input is too large to hold in memory all at once. The algorithm must adequately solve problems with only limited memory after one (or few) sequential passes over the data.

Prior to our work, no algorithms were known for several important instances of submodular optimization in uncertain environments; we improve known algorithms for others. In doing so, we develop techniques that we hope find uses elsewhere. We propose avenues for future work, including expanding the scope of these algorithms to new incomplete information settings, as well as applying insights from these submodular optimization algorithms to problems that are not on their surface related to submodularity.

Thesis Committee:
Anupam Gupta (Chair)
R. Ravi
David Woodruff
Joseph (Seffi) Naor (Technion)
Chandra Chekuri (University of Illinois, Urbana-Champaign)

Zoom Participation. See announcement.

For More Information, Please Contact: 
Keywords: