Theory Lunch This Week (4/24, 12:00, GCS 502c)
8 views
Skip to first unread message
Grayson York
Apr 21, 2025, 9:37:35 PMApr 21
to usc-theo...@googlegroups.com, usc-t...@googlegroups.com
Hi all,
Please join us this Thursday 4/24 at 12:00 in GCS 502c for Neel's thesis proposal. The title and abstract for the talk are as follows:
Title: Combinatorial Optimization under Uncertainty, Incentives and Correlations.
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:
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.
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.
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.
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:
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.
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.
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.
Reply all
Reply to author
Forward
0 new messages