Theory Lunch Seminar - Amir Azarmehr

— 1:00pm

Location:
In Person - Gates Hillman 8102

Speaker:
AMIR AZARMEHR, Ph.D. Student in Computer Science, Khoury College of Computer Sciences, Northeastern University
https://amirazarmehr.com/

We prove that a polynomial degree (in inverse of realization probability) subgraph can obtain a (1-epsilon)-approximation for stochastic matching, improving over the previous quasi-polynomial degree bound of [Behnezhad, Derakhshan, Hajiaghayi STOC'20]. Beyond its quantitative improvement, a key conceptual contribution of our work is to connect local computation algorithms (LCAs) to the stochastic matching problem for the first time. While prior work on LCAs mainly focuses on their out-queries (the number of vertices probed to produce the output of a given vertex), our analysis also bounds the in-queries (the number of vertices that probe a given vertex). We prove that the outputs of LCAs with bounded in- and out-queries (in-n-out LCAs for short) have limited correlation, a property that our analysis crucially relies on and might find applications beyond stochastic matchings. 

This talk is based on a joint work with Soheil Behnezhad, Alma Ghafari, and Ronitt Rubinfeld, to appear in STOC'25, .

Event Website:
https://www.cs.cmu.edu/~theorylunch/abstractsHTML/20250226.html

Add event to Google
Add event to iCal