Charla: Computing Efficiently Succinct
SPEAKER: Mihalis Yannakakis
TIME: 3:00 pm
DATE: Friday, August 25
CIW/DCC Centro de Investigacion de la Web &
Depto. de Cs. de la Computacion
CMM/DIM Seminario de Matematicas Discretas
When evaluating different solutions from a design space,
it is often the case
that more than one criteria come into play. The trade-off
between the different
criteria is captured by the so-called Pareto curve.
The Pareto curve has typically an exponential number of
points. However, it
turns out that, under general conditions, there is a polynomially
that approximates the Pareto curve within any desired accuracy.
In the first part of the talk we address the question of
when such an
approximate Pareto curve can be computed in polynomial time.
We discuss general
conditions under which this is the case, and relate the
approximation to the single objective case. In the second
part of the talk, we
address the problem of computing efficiently a good approximation
trade-off curve using as few solutions (points) as possible.
If we are to select
only a certain number of solutions, how shall we pick them
so that they
represent as accurately as possible the spectrum of possibilities?
(The talk is based on joint works with Christos Papadimitriou,
Vassilvitskii and Ilias Diakonikolas.)
Mihalis Yannakakis is the Percy K. and Vida L. W. Hudson
Computer Science at Columbia University. Prior to joining
he was Director of the Computing Principles Research Department
at Bell Labs and at Avaya Labs,
and Professor of Computer Science at Stanford University.
Dr. Yannakakis received his PhD from Princeton University.
His research interests include algorithms, complexity, optimization,
databases, testing and verification.
He has served on the editorial boards of several journals,
including as the past editor-in-chief of the SIAM Journal
and has chaired various conferences, including the IEEE
Foundations of Computer Science, the ACM Symposium on Theory
and the ACM Symposium on Principles of Database Systems.
Dr. Yannakakis is a Fellow of the ACM, a Bell Labs Fellow,
a recipient of the Knuth Prize.