[Colloquium] TTIC Colloquium: Vijay Vazirani, Georgia Tech

[Liv Leader]

*REMINDER:*

When:     *Wednesday, April 6 @ 1 p.m.*

Where:    *TTIC Conference Room #526*, 6045 S. Kenwood Ave, 5th Floor

Who:       *Vijay Vazirani*, Georgia Tech

Title:        *Rational Convex Programs*

Let us say that a nonlinear convex program is rational if it has a rational
solution, that can be written in polynomially many bits, whenever all its
parameters are set to rational numbers.

At present, two classes of RCPs are known: quadratic and logarithmic. Those
in the first class are obviously rational and have been studied for several
decades.On the other hand, almost all logarithmic RCPs were found only in
the last decade in the context of the fascinating question of understanding
the computability of equilibria for various market models. Rationality for
programs in this class is not automatic and has to be established piecemeal.

The algorithmic significance of rationality is that it opens up the
possibility of solving the underlying problem with an efficient
combinatorial algorithm. We will talk about the innate potential of this
approach and mention several other open questions, not the least of which
is to determine if there are other classes of RCPs.

Based on the following paper and references therein:
http://www.cc.gatech.edu/~vazirani/NBalg.pdf

Host: Alexander Razborov, razborov at cs.uchicago.edu

-- 
Liv Leader
Faculty Services

Toyota Technological Institute
6045 S Kenwood Ave, #504
Chicago, IL 60637
Phone- (773) 834-2567
Fax-     (773) 834-9881
Email-  lleader at ttic.edu <jam at ttic.edu>
Web-   www.ttic.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20110405/4e4be0fb/attachment.htm