Georgia Institute of Technology College of Sciences

The problem of quantifying the amount of information loss due to a random transformation (or a noisy channel) arises in a variety of contexts, such as machine learning, stochastic simulation, error-correcting codes, or computation in circuits with noisy gates, to name just a few. This talk will focus on discrete channels, where both the input and output sets are finite. The noisiness of a discrete channel can be measured by comparing suitable functionals of the input and output distributions. For instance, if we fix a reference input distribution, then the worst-case ratio of output relative entropy (Kullback-Leibler divergence) to input relative entropy for any other input distribution is bounded by one, by the data processing theorem. However, for a fixed reference input distribution, this quantity may be strictly smaller than one, giving so-called strong data processing inequalities (SDPIs). I will show that the problem of determining both the best constant in an SDPI and any input distributions that achieve it can be addressed using logarithmic Sobolev inequalities, which relate input relative entropy to certain measures of input-output correlation. I will also show that SDPIs for Kullback-Leibler divergence arises as a limiting case of a family of SDPIs for Renyi divergence, and discuss the relationship to hypercontraction of Markov operators.

The rank of a bimatrix game (A, B) is defined as the rank of (A+B). For zero-sum games, i.e., rank 0, Nash equilibrium computation reduces to solving a linear program. We solve the open question of Kannan and Theobald (2005) of designing an efficient algorithm for rank-1 games. The main difficulty is that the set of equilibria can be disconnected. We circumvent this by moving to a space of rank-1 games which contains our game (A, B), and defining a quadratic program whose optimal solutions are Nash equilibria of all games in this space. We then isolate the Nash equilibrium of (A, B) as the fixed point of a single variable function which can be found in polynomial time via an easy binary search. Based on a joint work with Bharat Adsul, Jugal Garg and Milind Sohoni.

(algebraic statistics reading seminar)

Pricing and allocating goods to buyers with complex preferences in order to maximize some desired objective (e.g., social welfare or profit) is a central problem in Algorithmic Mechanism Design. In this talk I will discuss some particularly simple algorithms that are able to achieve surprisingly strong guarantees for a range of problems of this type. As one example, for the problem of pricing resources, modeled as goods having an increasing marginal extraction cost to the seller, a simple approach of pricing the i-th unit of each good at a value equal to the anticipated extraction cost of the 2i-th unit gives a constant-factor approximation to social welfare for a wide range of cost curves and for arbitrary buyer valuation functions. I will also discuss simple algorithms with good approximation guarantees for revenue, as well as settings having an opposite character to resources, namely having economies of scale or decreasing marginal costs to the seller.