PhD Thesis Proposal - Neel Patel

Title: Combinatorial Optimization under Uncertainty, Incentives and Correlations.  
 
Date and Time: 04/24, 12:30-1:30 pm  
 
Location: GCS 502C  
 
Committee Members: Shaddin Dughmi, David Kempe, Vatsal Sharan, Evi Micha and Greta Panova    
 
Abstract:  
 
This proposal considers algorithms for combinatorial problems, primarily those concerned with combinatorial selection under uncertainty and incentives, also known as stochastic selection problems. The core focus is on the two pivotal stochastic selection problems that include contention resolution schemes (CRS) and generalized prophet inequalities. Our contributions are twofold:    
 
Our first contribution deepens the understanding of the stochastic selection problems beyond independent priors on the input and its implications on the famous matroid secretary conjecture.  Our results completely characterize the CRS and prophet inequalities on matroids for pairwise independent priors. En route to proving our results, we develop techniques to sample exact pairwise independent vectors over a finite field from approximate pairwise independent vectors which later becomes a key ingredient for characterizing the difficult instance for binary matroid secretary conjecture.  
 
The rest of the proposal aims to push the applications of the powerful algorithmic toolkit --- stochastic selection with a broader goal of identifying the algorithmic and economic questions that appear to be complex and algorithmically challenging, for which the techniques developed by online stochastic selection provide an alternative outlook, leading to more efficient and powerful algorithmic results. In this context, we prove the following key results:
 
1.) We obtain the first combinatorial generalized stationary prophet inequalities where our main result shows that the (offline) CRS plays a central role in the (online) stationary prophet inequality problem. This intriguing connection allows us to obtain several new algorithmic results as well as improves the existing results significantly.
 
2.) We systematically generalize the sparsification of stochastic matching problems to the general combinatorial structure. Here, we show that any combinatorial structure that exhibits `good’ CRS also exhibits strong stochastic sparsifiers. 
 
3.) We obtain constant approximate delegation mechanisms for the principal-agent delegation problem with probing cost for a large class of combinatorial constraints.  We obtain these mechanisms by reducing the delegation problem to the online version of CRS for combinatorial constraints. 

Location: Ginsburg Hall (GCS) - 502C

Audiences: Everyone Is Invited

Contact: Neel Patel

This event is open to all eligible individuals. USC Viterbi operates all of its activities consistent with the University's Notice of Non-Discrimination. Eligibility is not determined based on race, sex, ethnicity, sexual orientation, or any other prohibited factor.

Add to Google Calendar