Jieming Mao will present a pre-FPO talk on Tuesday, March 6, 2018 at 2:00 pm in CS 402. Members of his Committee are as follows: Mark Braverman (Adviser) - Princeton University Matt Weinberg (Reader) - Princeton University Bernard Chazelle (Reader) - Princeton University Ran Raz (Examiner) - Princeton University Elad Hazan (Examiner) - Princeton University All are welcome to attend. ================ Title: Algorithms in Strategic or Noisy Environments Abstract: Algorithms are often used in strategic or noisy environments. These factors can significantly affect the performance of algorithms. My research aims to design algorithms that are robust against such factors.In the first half of the talk, I will talk about no-regret learning algorithms in strategic environments. We study a specific setting in which a fully strategic seller repeatedly sells goods to a buyer who no-regret learns over time. We give a full characterization of whether the seller can extract additional revenue from the buyer. In the second half of the talk, I will talk about parallel algorithms for finding top-k items with noisy pairwise comparisons. The problem has applications in crowdsourcing, peer grading and recommender systems. We show tight trade-offs between sample complexity and round complexity.