Computer Science for Mathematicians

The CMSA will host a weekly seminar running through 2020-21, where researchers from all areas of computer science present modern frontiers in computer science to the general mathematical audience. Talks shall be accessible to anyone with a good mathematical background; no domain-specific background is required. The seminar will run weekly on Tuesday 11:30 am ET.

In order to attend this seminar, please fill out this form.

For more information, contact the seminar organizer, Omri Ben-Eliezer (

Yannai A. Gonczarowski (Microsoft Research)

Title: The Menu-Size of Approximately Optimal Auctions

Abstract: We consider a monopolist who wishes to sell n goods to a single additive buyer, where the buyer’s valuations for the goods are drawn according to independent distributions. It is well known that—unlike in the single item case—the revenue-optimal auction (a pricing scheme) may be complex, sometimes requiring a continuum of menu entries, that is, offering the buyer a choice between a continuum of lottery tickets. It is also known that simple auctions with a finite bounded number of menu entries (lotteries for the buyer to choose from) can extract a constant fraction of the optimal revenue, as well as that for the case of bounded distributions it is possible to extract an arbitrarily high fraction of the optimal revenue via a finite bounded menu size. Nonetheless, the question of the possibility of extracting an arbitrarily high fraction of the optimal revenue via a finite menu size, when the valuation distributions possibly have unbounded support (or via a finite bounded menu size when the support of the distributions is bounded by an unknown bound), remained open since the seminal paper of Hart and Nisan (2013), and so has the question of any lower-bound on the menu-size that suffices for extracting an arbitrarily high fraction of the optimal revenue when selling a fixed number of goods, even for two goods and even for i.i.d. bounded distributions.
In this talk, we resolve both of these questions. We first show that for every n and for every ε>0, there exists a menu-size bound C=C(n,ε) such that auctions of menu size at most C suffice for extracting a (1-ε) fraction of the optimal revenue from any valuation distributions, and give an upper bound on C(n,ε), even when the valuation distributions are unbounded and nonidentical. We then proceed to giving two lower bounds, which hold even for bounded i.i.d. distributions: one on the dependence on n when ε=1/n and n grows large, and the other on the dependence on ε when n is fixed and ε grows small. Finally, we apply these upper and lower bounds to derive results regarding the deterministic communication complexity required to run an auction that achieves such an approximation.
9/22/2020Daniel Goldberg (NextSilicon)Title: Cybersecurity research in the wild

Abstract: Cybersecurity research exhibits classic yet complex challenges, melding together cryptography, programming language design, and computational complexity, along with psychology and industrial design.
One example of these challenges is crafting an expressive yet safe programming language. SQL — the most popular database querying language — is, however, far from being safe; its expressiveness and lack of care in design result in countless SQL injection attacks to this day. The approaches to mitigating this design flaw vary between academia and industry and involve a mixture of graph analysis, system engineering and new designs of programming interfaces.
During this talk I will review the different participants in frontier research: industry, academia, nationstates and hobbyists. The first part of the talk will focus on these participants and their incentives, while the second part will contrast how academia is approaching them compared to industry and nationstates.
9/29/2020Rajesh Jayaram (CMU)

The schedule below will be updated as talks are confirmed.

Related Posts