Georgia Institute of Technology College of Sciences

Designing mechanisms to maximize revenue is a fundamental problem in mathematical economics and has various applications like online ad auctions and spectrum auctions. Unfortunately, optimal auctions for selling multiple items can be unreasonably complex and computationally intractable. In this talk, we consider a revenue-maximizing seller with n items facing a single unit-demand buyer. Our work shows that simple mechanisms can achieve almost optimal revenue. We approached the tradeoffs of simplicity formally through the lens of computation and menu size. Our main result provides a mechanism that gets a (1 − ε)-approximation to the optimal revenue in time quasi-polynomial in n and has quasi polynomial (symmetric) menu complexity. 

Joint work with Pravesh Kothari, Ariel Schvartzman, Sahil Singla, and Matt Weinberg.

Meeting link: https://bluejeans.com/912860268/9947

The Navier-Stokes and Euler equations are the fundamental models for describing viscous and inviscid fluids, respectively. Based on ideas which date back to Kolmogorov and Onsager, solutions to these equations are expected to dissipate energy, which in turn suggests that such solutions are somewhat rough and thus only weak solutions. At these low regularity levels, however, one may construct wild weak solutions using convex integration methods. In this talk, I will discuss the motivation and methodology behind joint work with Tristan Buckmaster, Nader Masmoudi, and Vlad Vicol in which we construct wild solutions to the Euler equations which deviate from the predictions of Kolmogorov's classical K41 phenomenological theory of turbulence.

Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its "expectation-threshold," which is a natural (and often easy to calculate) lower bound on the threshold. In this talk, I will first introduce the Kahn-Kalai Conjecture with some motivating examples and then talk about the recent resolution of a fractional version of the Kahn-Kalai Conjecture due to Frankston, Kahn, Narayanan, and myself. Some follow-up work, along with open questions, will also be discussed.

Szemerédi's regularity lemma is a game-changer in extremal combinatorics and provides a global perspective to study large combinatorial objects. It has connections to number theory, discrete geometry, and theoretical computer science. One of its classical applications, the removal lemma, is the essence for many property testing problems, an active field in theoretical computer science. Unfortunately, the bound on the sample size from the regularity method typically is either not explicit or enormous. For testing natural permutation properties, we show one can avoid the regularity proof and yield a tester with polynomial sample size. For graphs, we prove a stronger, "L_\infty'' version of the graph removal lemma, where we conjecture that the essence of this new removal lemma for cliques is indeed the regularity-type proof. The analytic interpretation of the regularity lemma also plays an important role in graph limits, a recently developed powerful theory in studying graphs from a continuous perspective. Based on graph limits, we developed a method combining with both analytic and spectral methods, to answer and make advances towards some famous conjectures on a common theme in extremal combinatorics: when does randomness give nearly optimal bounds? 

These works are based on joint works with Jacob Fox, Dan Kral',  Jonathan Noel, Sergey Norin, and Jan Volec.