Workshops, ALADDIN Center

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 High-Dimensional Datasets Considering the problem of learning about the structure of large and possible high-dimensional 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 game-theoretic terms, we show that ANY mediated game with incomplete information can be perfectly simulated by the players alone, by means of an extensive-form game in which the trusted mediator is replaced by a ballot box---the 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 High-performance 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 high-performance 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 high-performance computation on discrete structures that will be used both as a rapid-prototyping 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 NP-hard 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 NP-hard.

Back to MillerFest 2006 main page