Theory Day in Sydney 2011
Friday 28-Jan-2011, 9am-5pm New Law School Seminar 024, University of Sydney
The 2011 Sydney Theory Day will be was organized in the University of Sydney on 28-Jan-2011. The aim of this one-day event is to bring together researchers interested in all aspects of theoretical computer science, and discuss current trends and problems in the field, as well as future directions. The meeting is sponsored by the University of Sydney and NICTA. Workshop program:Invited speakers:
- Otfried Cheong, KAIST, Korea
- Benjamin Doerr, MPI and Saarland Uni, Germany
- Catherine Greenhill, UNSW
- Bernard Mans, Macquarie University
- Toby Walsh, NICTA
- David Wood, University of Melbourne
- 9:15-9:30: Coffee
- 9:30-10:30: Otfired Cheong
- 10:30-11:30 Benjamin Doerr
- 11:30-11:45 Coffee break
- 11:45-12:45 Toby Walsh
- 12:45-13:45 Lunch
- 13:45-14:45 Catherine Greenhill
- 14:45-15:45 Bernard Mans
- 15:45-16:00 Coffee break
- 16:00-17:00 David Wood
Organization: Joachim Gudmundsson, Julian Mestre, and Taso Viglas.
Otfried Cheong, KAIST
Title: Motion planning with bounded curvature
Abstract: The problem of planning the motion of a robot subject to so-called non-holonomic constraints (for instance, bounds on velocity or acceleration or bounds on the turning angle) has received considerable attention in the robotics literature. Theoretical studies of non-holonomic motion planning are far sparser. We consider a point robot in the plane whose turning radius is constrained to be at least one and that is not allowed to make reversals. This restriction corresponds naturally to constraints imposed by the steering mechanism found in car-like robots. I will survey the known theoretical results on this problem, and sketch some proof ideas for three particular problems: the region of points reachable inside a convex polygon, visiting a sequence of points, and a bound on the detour enforced by the curvature constraint.
Benjamin Doerr, MPI and Uni Saarland
Title: Randomized rumor spreading: talking to more or less random people
Abstract: Randomized Rumor Spreading is a simple mechanism to distribute a piece of information (rumor) in a network. It builds on the paradigm that vertices call random neighbors to send or retrieve information. In spite of its simplicity and the lack of central coordination, such mechanisms spread a rumor initially present at a single vertex to all others in logarithmic time if the graph is sufficiently nice (e.g., a complete graph, a hypercube, a random graph G(n,p), p not too small, and many others). In the talk, I will discuss two recent results on randomized rumor spreading. (i) How to improve the rumor spreading protocol adding simple dependencies to the random decisions of the vertices. (ii) How fast is rumor spreading in social networks, in particular, preferential attachment graphs?
Toby Walsh, NICTA & UNSW
Title: The complexity of breaking symmetry
Abstract: Symmetry is a common feature of many combinatorial problems. Unfortunately eliminating all symmetry from a problem is computationally intractable in general. In this talk, I argue that parameterized complexity provides insight into that intractability and helps identify special cases in which symmetry can be dealt with more tractably.
Catherine Greenhill, UNSW
Title: Generating graphs randomly
Abstract: The problem of generating a random element from the set of all labelled simple graphs with a given degree sequence has many applications. I will take a not-so random walk through the history of this problem, from the configuration model of the late 1970s through to the remarkable recent algorithm of Bayati, Kim and Saberi.
Bernard Mans, Macquarie University
Title: On time-varying graphs for highly dynamic networks Abstract: The past few years have seen intensive research efforts carried out in some apparently unrelated areas of dynamic systems–delay-tolerant networks, opportunistic-mobility networks, social networks–obtaining closely related insights. Of particular interest for this talk is the fact that most highly dynamic infrastructure-less networks are characterized by a possible absence of end-to-end connection paths at any instant. In most cases, however, a form of communication route can be established over time and space. This particularity leads to consider the relevance of a given route not only in terms of hops (topological length), but also in terms of time (temporal length). These networks (variously called delay-tolerant, disruptive-tolerant, challenged) are naturally modeled as time-varying graphs (or evolving graphs), where the existence of an edge is a function of time. We first describe the time-varying graph model and terminology that are used throughout the talk. We show that as new notations and concepts are introduced, classical and basic graph problems are challenged and new important open problems appear. To illustrate the difficulty at hand, we present deterministic results on the computability and complexity of different problems: broadcasting, measuring temporal lags, and exploration. We prove that the solvability and complexity of this problem vary with the metric considered, as well as with the type of knowledge a priori available to the entities. This is join work with: A. Casteigts and P. Flocchini (Ottawa U.), and N. Santoro (Carleton U.)
David Wood, University of Melbourne
Title: Algorithmic applications of graph treewidth
Abstract: The “treewidth” of a graph is a measure of its similarity to a tree. Treewidth is of fundamental importance in the theory of algorithms, in that large classes of graph optimisation problems can be solved in linear time on graphs with bounded treewidth. This talk will give a broad introduction to this topic, as well as exploring other connections with graph structure theory and graph drawing. Little background knowledge will be assumed.
A similar event was organized in May 2008 (TDS2008) and included invited presentations from Sartaj Sahni (University of Florida), Pat Morin (Carleton University), Peter Bro Miltersen (University of Aarhus), Rob van Glabbeek (NICTA and UNSW), and Tony Wirth (University of Melbourne). The 2008 Sydney Theory Day was sponsored by EII, University of Sydney and NICTA.