Re: [theory students] Theory lunch tomorrow

[YIFENG TENG <yifengt@xxxxxxxxxxx>]

Hi all,

We will have theory lunch at noon today in 4310. I'm going to give an informal talk on some recent work at Google. Pizza will be served during the talk. If you would like to come, please sign up on the spreadsheet or reply to this email to let us get the rough amount of pizza to order.

The spreadsheet for this semester is as below:

https://docs.google.com/spreadsheets/d/12LdZiO-QU7kW7s1bS4zSzeVw_1N-2Fkuh260gdcwM-U/edit?usp=sharing

Students are encouraged to sign up to give an (informal) talk. Also, professors are certainly welcome to add a note if free food will be provided.

Below is the information for tomorrow's talk.

Title: Why Do Competitive Markets Converge to First-Price Auctions?

Abstract: We consider a setting in which bidders participate in multiple auctions run by different sellers, and optimize their bids for the aggregate auction. We analyze this setting by formulating a game between sellers, where a seller's strategy is to pick an auction to run. Our analysis aims to shed light on the recent change in the Display Ads market landscape: here, adexchanges (sellers) were mostly running second price auctions earlier and over time they switched to variants of the first price auction, culminating in Google's Ad Exchange moving to a first price auction in 2019. Our model and results offer an explanation for why the first price auction occurs as a natural equilibrium in such competitive markets. This is joint work with Renato Paes Leme and Balasubramanian Sivan.

Thanks,

Yifeng

---

From: YIFENG TENG
Sent: Wednesday, October 2, 2019 3:06 AM
To: Shuai Shao <sh@xxxxxxxxxxx>; theory-faculty@xxxxxxxxxxx <theory-faculty@xxxxxxxxxxx>; theory-students@xxxxxxxxxxx <theory-students@xxxxxxxxxxx>; theory-postdocs@xxxxxxxxxxx <theory-postdocs@xxxxxxxxxxx>
Subject: Re: Theory lunch tomorrow

 

Hi all,

We will watch TCS+ talk at noon today in 4310. Feel free to bring your lunch and join us. The spreadsheet for this semester is as below:

https://docs.google.com/spreadsheets/d/12LdZiO-QU7kW7s1bS4zSzeVw_1N-2Fkuh260gdcwM-U/edit?usp=sharing

Students are encouraged to sign up to give an (informal) talk. Also, professors are certainly welcome to add a note if free food will be provided.

Below is the information for today's TCS+ talk.

 

Title: Towards the sunflower conjecture

Speaker: Shachar Lovett (UCSD)

Best,

Yifeng

---

From: Theory-students <theory-students-bounces@xxxxxxxxxxx> on behalf of Shuai Shao <sh@xxxxxxxxxxx>
Sent: Tuesday, September 24, 2019 11:14:00 PM
To: theory-faculty@xxxxxxxxxxx <theory-faculty@xxxxxxxxxxx>; theory-students@xxxxxxxxxxx <theory-students@xxxxxxxxxxx>; theory-postdocs@xxxxxxxxxxx <theory-postdocs@xxxxxxxxxxx>
Subject: [theory students] Theory lunch tomorrow

 

Hi, Dear all

 

We will watch TCS+ talk tomorrow noon in 4310. Feel free to bring your lunch and join us. I created a spreadsheet for this semester.

https://docs.google.com/spreadsheets/d/12LdZiO-QU7kW7s1bS4zSzeVw_1N-2Fkuh260gdcwM-U/edit?usp=sharing

Students are encouraged to sign up to give an (informal) talk. Also, professors are certainly welcome to add a note if free food will be provided. Thanks.

 

Below is the information for tomorrow TCS+ talk.

 

Title: Chasing Convex Bodies

Speaker: Mark Sellke(Stanford)

 

Abstract: I will explain our recent understanding of the chasing convex bodies problem posed by Friedman and Linial in 1991. In this problem, an online player receives a request sequence K_1,...,K_T of convex sets in d dimensional space and moves his position online into each requested set. The player's movement cost is the length of the resulting path. Chasing convex bodies asks if there an online algorithm with cost competitive against the offline optimal path. This is both an challenging metrical task system and (equivalent to) a competitive analysis view on online convex optimization. This problem was open for d>2 until last year but has recently been solved twice. The first solution gives a 2^{O(d)} competitive algorithm while the second gives a nearly optimal min(d,sqrt(d*log(T))) competitive algorithm for T requests. The latter result is based on the Steiner point, which is the exact optimal solution to a related geometric problem called Lipschitz selection and dates from 1840. In the talk, I will briefly outline the first solution and fully explain the second.

 

Partially based on joint works with Sébastien Bubeck, Bo'az Klartag, Yin Tat Lee, and Yuanzhi Li.