^January February – 2011 ^March

Paper (1): "Feature based Locomotion Controllers" - abstract: This paper introduces an approach to control of physics-based characters based on high-level features of movement, such as center-of-mass, angular momentum, and end-effectors. Objective terms are used to control each feature, and are combined by a prioritization algorithm. We show how locomotion can be expressed in terms of a small number of features that control balance and end-effectors. This approach is used to build controllers for human balancing, standing jump, and walking. These controllers provide numerous benefits: human-like qualities such as arm-swing, heel-off, and hip-shoulder counter-rotation emerge automatically during walking; controllers are robust to changes in body parameters; control parameters and goals may be modified at run-time; control parameters apply to intuitive properties such as center-of-mass height; and controllers may be mapped onto entirely new bipeds with different topology and mass distribution, without modifications to the controller itself. No motion capture or off-line optimization process is used.

Paper (2): "Robust Physics based Locomotion Using Low Dimensional Planning" - abstract: This paper presents a physics-based locomotion controller based on online planning. At each time-step, a planner optimizes locomotion over multiple phases of gait. Stance dynamics are modeled using a simplified Spring-Load Inverted (SLIP) model, while flight dynamics are modeled using projectile motion equations. Full-body control at each instant is optimized to match the instantaneous plan values, while also maintaining balance. Different types of gaits, including walking, running, and jumping, emerge automatically, as do transitions between different gaits. The controllers can traverse challenging terrain and withstand large external disturbances, while following high-level user commands at interactive rates.

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 vertex coloring problem in the message-passing model of distributed computing. In this model the network is represented by a graph G of maximum degree Delta, in which the vertices host processors, and the communication is performed over the edges of G. Vertex coloring has numerous applications in communication networks, and thus it has drawn a considerable attention of researchers in the last three decades. The question of how many colors an efficient algorithm (that is, an algorithm with polylogarithmic time) is required to use is a central long-standing open question. Currently, efficient randomized algorithms that employ Delta + 1 colors are known, but it is unknown whether this number of colors can be achieved deterministically and efficiently. In 1987, in a seminal FOCS paper, Linial devised an efficient deterministic algorithm that employs Delta^2 colors. In his paper Linial also asked whether it is possible to employ a significantly smaller number of ! colors while still maintaining a deterministic algorithm with polylogarithmic running time. Despite a very intensive research in this direction in the last twenty years, this question remained open prior to our work. We present a deterministic algorithm that runs in polylogarithmic time, and employs Delta^{1 + epsilon} colors, for an arbitrarily small positive constant epsilon. Thus, our algorithm settles the long-standing question of Linial. Moreover, our results give rise to significantly improved algorithm for O(Delta)-coloring, and even for o(Delta)-coloring of very wide graph families. These results are achieved using a novel graph-decomposition technique. Specifically, the vertex set of the graph is partitioned into subsets that satisfy certain helpful properties. In particular, the subsets induce sparse subgraphs. This allows coloring the subgraphs with sufficiently small number of colors while utilizing the parallelism of the network to the full extent. Our recent results show that this technique is very powerful, and is useful for additional problems such as edge coloring.

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