
Abstracts 
Thursday, April 20, 2006 
9:00 am 
Continental Breakfast 
9:30 am 
Tom Leighton,
Akamai
Lower Bounds for Some Problems on Grids
During the talk, we will breifly describe a collection of problems
involving grids for which some lower bounds have recently been
established. In most cases, optimal bounds are not known. Included are
problems involving multicommodity flow, TSP, and wire routing with
limited numbers of bends.

10:00 am 
Herbert Edelsbrunner,
Arts and Sciences Professor of
Computer Science and Mathematics, Duke University
Global Methods for HighDimensional Datasets
Considering the problem of learning about the structure
of large and possible highdimensional data sets, we take a
global approach aiming at determining their gross topology.
Specifically, we introduce a parametrized family of witness
complexes modeling the data and methods to extract the stable,
or persistent topology from the family.

10:30 am 
Break 
11:00 am 
Bruce Maggs,
Carnegie Mellon University
Variations on Nested Dissection
This talk is about my collaboration with Gary. We look at modifying elimination
orders for solving linear systems via direct methods either to make them more
parallel without creating too much more fill or less parallel to reduce the
fill.

11:30 am 
Silvio Micali,
MIT
Rational Secure Computation and Ideal Mechanism Design
We prove a general result bridging the fields of
Secure Protocols and Game Theory.
In gametheoretic terms, we show that ANY mediated
game with incomplete information can be perfectly
simulated by the players alone, by means of an
extensiveform game in which the trusted mediator
is replaced by a ballot boxthe venerable device
used throughout the world to privately and
correctly compute the tally of secret votes.
In cryptographic terms, we show that, in ANY joint
computation, security can be achieved based solely
on the players’ RATIONALITY, rather than on the
HONESTY of some of them.
Our result has broad implications for Mechanism
Design; in particular, it enables One to design
mechanisms in a MODULAR and COMPETITIVE fashion.
This is joint work with Sergei
Izmalkov and Matt Lepinski.

12:00 pm 
Lunch 
2:00 pm 
John Gilbert,
University of California, Santa Barbara
Interactive Combinatorial Supercomputing
Highperformance computing is being used to
understand large data sets that are combinatorial
rather than numerical in nature, in applications
as diverse as sparse matrices, knowledge
discovery, machine learning, search and
information retrieval, and computational biology.
Compared to numerical supercomputing, the field of
highperformance combinatorial computing is in its
infancy. How can combinatorial methods be used by
people who are not experts in discrete
mathematics? How can supercomputers be used by
people who need to explore huge discrete data sets
interactively?
We are building a flexible, scalable interactive
environment for highperformance computation on
discrete structures that will be used both as a
rapidprototyping tool for exploring and
experimenting with different approaches to
analysis, and as a scalable system for performing
analysis on real, dynamic, discrete data.

2:30 pm 
Dan Spielman,
Yale University
Gary's Algorithms for Graph Isomorphism
I will survey Gary Miller's contributions to the
development of algorithms for testing graph
isomorphism, and present in detail a beautiful but
unpublished algorithm of Leighton and Miller for
testing isomorphism of graphs with distinct
eigenvalues.

3:00 pm 
Break 
3:30 pm 
Satish Rao,
University of California, Berkeley
Recent Uses of Spectral Techniques for Graph Partitioning
We will describe some uses of spectral methods
in recent approaches to graph partitioning.

4:00 pm  4:30 pm 
Leslie Valiant,
Division of Engineering and Applied Sciences, Harvard University
Accidental Algorithms
We provide evidence for the proposition that the computational complexity of
certain computational problems may hinge on the existence of certain related
solvable polynomial systems that are otherwise arbitrary, and unlikely to be
encountered other than through enumerative searches for them. For example, we
consider a minimalist version of Cook's 3CNF problem, namely that of monotone
planar 3CNF formulae where each variable occurs twice. We show that counting the
number of solutions of these is NPhard modulo 2, and polynomial time computable
modulo 7 (sic). We use holographic methods for both the algorithms and the
completeness results. The latter yields the first general technique for showing
for problems for which solutions are easy to find, such as 2SAT, that parity is
NPhard.



Back to MillerFest 2006 main page
