Month: April 2016

Two Northwestern papers in FOCS 2015 (with video)

Talk videos are online from the 2015 Symposium on Foundations of Computer Science (FOCS).  The CS Theory group had two papers at the conference.

meNorthwestern CS Theory and Economics Ph.D. student Manolis Pountourakis did a really fantastic job of presenting his paper Optimal Auctions vs. Anonymous Pricing (joint with with coauthors Saeed Alaei, Rad Niazadeh, Yang Yuan, and me). The paper proves that eBay’s Auctions and Buy-It-Now (posted pricings) are within at least an e = 2.718 factor of the revenue optimal auction (which may be asymmetric and very complicated). This is a worst-case bound that is quite difficult to prove; in practice the eBay’s sales mechanisms likely do much better.  Watch the video!

dsc-mTCS Prof. Anindya De presented his paper Beyond the central limit theorem: Asymptotic expansions and pseudorandomness for combinatorial sums. This paper extends the central limit theorem to achieve faster convergence rates by using information about a large number of moments of the sum (as opposed to just the mean and variance). This result also has applications in space bounded derandomization, a central question in complexity theory.  Watch the video!

Northwestern CS initiates the Quarterly Theory Workshop

The Northwestern CS Theory Group hosted its First Quarterly Theory Workshop last month on the theme of Algorithmic Game Theory and Data Science. Fantastic talks were given by workshop speakers Tim Roughgarden (Stanford), Avrim Blum (CMU), and Eva Tardos (Cornell). Videos of the talks are available on the workshop webpage.

The goal of this new quarterly theory workshop format is to facilitate a deep discussion of the workshop theme and enable broad participation from theoretical computer science faculty and students in the greater Chicago area. For this first workshop, we were especially delighted to have attendees coming from the Toyota Technology Institute, University of Illinois at Chicago, the University of Chicago, and the University of Wisconsin at Madison. A colleague wrote afterward: “Thank you so much for inviting my students to attend the workshop yesterday! They were all blown away by the experience.”

The Second Quarterly Theory Workshop will be held on the morning of May 17 (Tuesday) on the theme of semidefinite programming hierarchies and sum-of-squares. The speakers are Boaz Barak (Harvard), David Steurer (Cornell), and Prasad Raghavendra (UC-Berkeley). The workshop will be preceded, on the morning of May 16 (Monday), by a tutorial on sum-of-squares by Madhur Tulsiani (TTI-Chicago). Individual meetings with the speakers are available on Monday and Tuesday afternoon.

Thanks to everyone who came and made the first workshop a success, we hope to see you all again for the second!