- You are here:
- GT Home
- Home
- News & Events

Series: Other Talks

Hosted by School of Computer Science.

Equilibrium computation is among the most significant
additions to the theory of algorithms and computational complexity in
the last decade - it has its own character, quite distinct from the
computability of optimization problems.
Our contribution to this evolving theory can be summarized in the
following sentence: Natural equilibrium computation problems tend to
exhibit striking dichotomies. The dichotomy for Nash equilibrium,
showing a qualitative difference between 2-Nash and k- Nash for k > 2,
has been known for some time. We establish a dichotomy for market
equilibrium.
For this purpose. we need to define the notion of Leontief-free
functions which help capture the joint utility of a bundle of goods that
are substitutes, e.g., bread and bagels. We note that when goods are
complements, e.g., bread and butter, the classical Leontief function
does a splendid job. Surprisingly enough, for the former case, utility
functions had been defined only for special cases in economics, e.g.,
CES utility function.
We were led to our notion from the high vantage point provided by an
algorithmic approach to market equilibria.
Note: Joint work with Jugal Garg and Ruta Mehta.

Series: Other Talks

(algebraic statistics reading seminar)

Series: Other Talks

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.

Series: Other Talks

Emory University, the Georgia Institute of Technology and Georgia State
University, with support from the National Security Agency and the
National Science Foundation, are hosting a series of mini-conferences.
The ninth in the series will be held at Georgia Tech on
April 27-28, 2013. This mini-conference's featured speaker is
Dr. Fan Chung Graham, who will give two one-hour lectures. There will be
five one-hour talks and a number of half-hour talks given by other
invited speakers.
To register, please submit the
registration form.
Registration is free but is required.

Series: Other Talks

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.

Series: Other Talks

(algebraic statistics reading seminar)

Series: Other Talks

(algebraic statistics reading seminar)

Series: Other Talks

Algorithms and Randomness Center (ARC) Theory Day is an annual event that features hour-long lectures focusing on recent innovative results in theoretical computer science, spanning a wide array of topics several of which are inspired by practical problems.
See the complete list of titles and times of talks.

Series: Other Talks

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.

Series: Other Talks