^January February – 2011 ^March

e-Science involves the application of advanced computational methods to other areas of science and technology. It It has attracted a good deal of support over the past 10 years, and numerous groups have developed new techniques and software prototypes. Importantly, e-Science requires advanced in both computer science and the application area, making it an ideal driver for computer science research. In this talk, I will explore whether any of this work is actually making a difference. I will discuss our own projects work at the Monash e-Science and Grid Engineering (MeSsAGE) Lab, a computer science research laboratory devoted to new software development techniques that support e-Science applications. I will show how high throughput (aka parallel) scientific workflows have not only contributed to the state of the art in computer science, but are being adopted in research labs at Monash and internationally. In particular, I will highlight case studies in the medical imaging, chemistry and cardiac science.

Milgram's landmark six-degrees-of-separation experiment led to the fascinating small world hypothesis: take any two people in a social network, and they will be connected by a short chain of acquaintances. The extent to which the hypothesis is true is still actively debated. In this talk we give new experimental and theoretical results concerning Milgram's experiment. In particular, we discuss the possibility and the importance of performing purely digital replicas of the experiment, without human subjecs taking part in it. Joint work with Silvio Lattanzi and D.Sivakumar

Given a set of n points in L_1, how many dimensions are needed to represent all pairwise distances within a specific distortion ? This dimension-distortion tradeoff question is well understood for the L_2 norm, where O((log n)/epsilon^{2}) dimensions suffice to achieve 1+epsilon distortion. In sharp contrast, there is a significant gap between upper and lower bounds for dimension reduction in L_1. In this work, we show the first near linear lower bounds for dimension reduction in L_1. In particular, we show that 1+epsilon distortion requires at least n^{1-O(1/log(1/epsilon))} dimensions. Our proofs are combinatorial, but inspired by linear programming. In fact, our techniques lead to a simple combinatorial argument that is equivalent to the LP based proof of Brinkman-Charikar for lower bounds on dimension reduction in L_1.

Joint work with Alex Andoni, Moses Charikar and Huy Nguyen

There are numerous real-world problems that translate to searching for short distances. These distances can either be explicit (think of road navigation in Google maps) or implicit (think of the distance between humans and mice as the number of changes in their genomes). In my talk, I will describe some techniques that are useful for solving various shortest paths problems efficiently. I will begin with the problem of finding a shortest path in a "grid-like" graph. This problem arrises when computing the distance (minimum number of changes) between two sequences (say two genomes), and has many applications in computational biology, speech recognition, and information retrieval. A slightly more complicated grid-like graph arises when computing the distance (minimum number of changes) between two trees (say two XML files). This has applications in computer vision, compiler optimization, and natural language processing. I will then move to layered graphs (where shortest paths can be used to decode Hidden Markov Models) and then to planar graphs (where shortest paths can be used for VLSI design and geographical routing problems). Finally, I will discuss shortest paths in general graphs, and describe how to maintain shortest paths in a (more realistic) network whose edges occasionally fail. The problem has applications in game (auction) theory and is in tight connection with classical problems such as all-pairs shortest paths. My goal is to illustrate some general techniques that are useful for many of these problems. These techniques include the efficient computation of distance products, the reduced lengths method, and the use of compression as a tool for acceleration.

We consider the problem of finding a maximum flow in directed planar graphs with multiple sources and sinks. For general (i.e., non-planar) graphs, the multiple-source multiple-sink maximum flow problem is as difficult as the standard single-source single-sink one. The reduction, however, does not preserve planarity. No efficient planarity exploiting algorithms for this problem were known until the current line of work. We present a divide-and-conquer algorithm that solves the problem on a planar graph with n nodes in O(n^1.5 log(n)) time. This is asymptotically faster than any previously known algorithm. Joint work with Glencora Borradaile, Philip Klein, Yahav Nussbaum and Christian Wulff-Nilsen. Preprints can be found at http://arxiv.org/abs/1012.5870 and http://arxiv.org/abs/1008.5332