Invited Speakers

City of Rhodes, gravure

  • Allan Borodin, Department of Computer Science, University of Toronto:
    The Power and Limitations of Simple Algorithms: A Partial Case Study of Greedy Mechanism Design for Combinatorial Auctions

    Abstract

    Given the diversity of computational problems, models of computation, solution concepts, and algorithmic approaches, it often seems a challenge to view computer science/informatik as a coherent discipline. Fortunately, various unifying ideas (e.g. NP-completeness) have brought significant perspective to a very complex and ever expanding field.

    In a less ambitious program, I have been thinking about simple algorithmic approaches that arise frequently in approximation algorithms for combinatorial optimization. To be more specific, I am in interested in "greedy-like" algorithms and recently I am trying to understand the use of such algorithms in combinatorial auctions. I will discuss some precise models for simple greedy-like algorithms and how such algorithms can and cannot achieve desirable properties such a truthfulness, and convergence to "good" equilibria.

    The ideas in this talk are based on recent work with Brendan Lucier and also relate to Yuli Ye's talk in ICALP.

  • Erik Demaine (MIT), "Actuator Nets: Folding, Reconfiguring, and Deploying Sensors"

    Abstract

    What happens when sensors can move around or otherwise change their geometry? When all sensors can move (a robot swarm), we would like to be able to determine and manipulate high-level properties, such as the boundary of the swarm or the connectivity of the communication network. When only a few sensors can move, we would like the mobile sensors to be able to deploy immobile sensors to improve or repair the network connectivity or coverage. When the sensors are attached to a connected substrate, and they can manipulate the substrate, we would like to be able to reconfigure the substrate into arbitrary shapes. I will describe several algorithmic projects to address all of these problems.