Holographic Algorithms
Leslie Valiant
Harvard University
Thursday, November 30, 2006
9:00 a.m. in 2310 CS
(refreshments at 8:30)
Abstract:
Using the notion of polynomial time reduction computer scientists have
discovered an astonishingly rich web of interrelationships among the myriad
computational problems that arise in diverse applications. These
relationships can be used both to give evidence of intractability, such as
that of NP-completeness, as well as to give efficient algorithms.
In this talk we discuss a notion of reduction, which we call a holographic
reduction that is more general than the traditional one in the following
sense. Instead of locally mapping solutions one-to-one it maps them
many-to-many but preserves some measure such as the sum of the solutions.
One application is to finding new polynomial time algorithms where none
was known before. Another is to give evidence of intractability. There are
pairs of related problems that can be contrasted in this manner. For example,
for a skeletal version of Cook's 3CNF problem (restricted to be planar
and where every variable occurs twice positively) the problem of counting
the solutions modulo 2 is NP-hard, but counting them modulo 7 is polynomial
time computable.
Also, one can revisit the currently accepted conjectures of computer science,
such as that P does not equal NP, and ask whether this new kind of reduction
offers any insights either way regarding the truth of these conjectures.
Speaker's Bio:
Leslie Valiant was educated at King's College, Cambridge; Imperial College,
London; and at Warwick University where he received his Ph.D. in computer
science in 1974. He is currently T. Jefferson Coolidge Professor of Computer
Science and Applied Mathematics in the Division of Engineering and Applied
Sciences at Harvard, where he has taught since 1982. Before coming to Harvard
he had taught at Carnegie-Mellon University, Leeds University, and the
University of Edinburgh.
His work has ranged over several areas of theoretical computer science,
particularly complexity theory, computational learning, and parallel
computation. He also has interests in computational neuroscience, evolution
and artificial intelligence.
He received the Nevanlinna Prize at the International Congress of
Mathematicians in 1986 and the Knuth Award in 1997. He is a Fellow of the
Royal Society (London) and a member of the National Academy of Sciences (USA).
|