Select a calendar:
Filter April Events by Event Type:
Events for April 24, 2025
-
NL Seminar
Thu, Apr 24, 2025 @ 11:00 AM - 12:00 PM
Information Sciences Institute
Conferences, Lectures, & Seminars
Speaker: Skyler Hallinan, USC
Talk Title: TBA
Series: NL Seminar
Abstract: Meeting hosts only admit on-line guests that they know to the Zoom meeting. Hence, you’re highly encouraged to use your USC account to sign into Zoom. If you’re an outside visitor, please inform us at (nlg-seminar-host(at)isi.edu) to make us aware of your attendance so we can admit you. Specify if you will attend remotely or in person at least one business day prior to the event. Provide your: full name, job title and professional affiliation and arrive at least 10 minutes before the seminar begins. If you do not have access to the 6th Floor for in-person attendance, please check in at the 10th floor main reception desk to register as a visitor and someone will escort you to the conference room location
Host: Jonathan May and Katy Felkner
Webcast: https://www.isi.edu/research-groups-nlg/nlg-seminars/Location: Information Science Institute (ISI) - Conf Rm#689
WebCast Link: https://www.isi.edu/research-groups-nlg/nlg-seminars/
Audiences: Everyone Is Invited
Contact: Pete Zamar
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. -
PhD Thesis Proposal - Neel Patel
Thu, Apr 24, 2025 @ 12:30 PM - 01:30 PM
Thomas Lord Department of Computer Science
University Calendar
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.
