Fall 2005 - Winter 2006

Date Speaker and Abstract
2.9.2005 Speakers: The professors of SOCS
Title: Overview of the research activities at SOCS
Abstract: Professors from SOCS will give a 5-minute summary of the research going on in their lab. This is a great opportunity for new students to learn about the department and gather information necessary to eventually decide which research area and supervisor to choose.
9.9.2005 Speaker: Allen Tannenbaum
Affiliation: School of Electrical and Computer Engineering, Georgia Tech
Area: Computer vision, Image Processing, Biomedical Imaging
Title: Methods for Segmentation and Registration of Medical Imagery
Abstract: We will describe some recent work on two key problems in medical imagery: segmentation and registration. We will also describe controlled active vision techniques for image guided surgery and therapy.
The underlying method is based on certain flows which give rise to (nonlinear) geometric equations which are invariant with respect to a given transformation group action. We will provide some relevant results from the theory of curve and surface evolution, and show how these may be used for a number of areas in computer vision and image processing, such as image enhancement, optical flow, registration image segmentation, shape theory, and invariant scale-spaces. We will demonstrate these techniques with a wide variety of medical images including MR, CT, and ultrasound.
The talk is designed to be accessible to a general audience with an interest in medical imaging.

16.9.2005 No colloquium.

23.9.2005 No colloquium.

30.9.2005 Speaker: Wes Huang
Affiliation: Rensselaer Polytechnic Institute
Area: Robotics
Title: Mapping and Exploration with Sensing-Limited Robots
Abstract: Despite their sensing limitations, blind people are able to explore and navigate in the world. We have been developing algorithms for robots with sensing limitations --- sparse and limited-range sensing --- to make maps and subsequently navigate using those maps. Our motivation is twofold: to improve the capabilities of inexpensive robots with a limited array of sensors and to investigate the relationship between sensing limitations and a robot's mapping and navigation abilities. As an example of the sensing limitations we have in mind, our robots are equipped with only five IR rangefinders that have a maximum range of 80 cm.
First, I will present our work in creating topological maps with these robots. These topological maps are defined in terms of robot behaviors: nodes in our map are locations where behaviors terminate, and the robot has a choice of behaviors at each node to take it to another location. Our approach in this work has been to develop behaviors that explicitly consider the geometry of the world, so the resulting map represents relevant aspects of the geometry while still
reflecting the "topological" connectivity between places. In particular, we have devised robot behaviors that trace the generalized Voronoi diagram under the $L_\infty$ distance metric, resulting in a complete algorithm for mapping rectilinear worlds with sparse short-range sensing.
Next, I will discuss how topological maps from multiple robots (without a common reference frame) can be merged using a combination of techniques from image registration and graph matching. Finally, I will show some preliminary results in applying a particle filter SLAM (simultaneous localization and mapping) technique to robots with sparse sensing to create maps of large-scale environments.
7.10.2005 Speaker: Rick Durrett
Affiliation: Cornell University
Title: Life in a Small World
Abstract: In 1998 Strogatz and Watts created their small world random graph by starting with a ring of sites each of which was connected to its k nearest neighbors in each direction and then rewiring a small fraction p of connections. One can in a straightforward way define a two dimensional version starting from a torus. This gives a graph that is a more reasonable model for the spread of infectious diseases. We get colds and the flu not only from our next door neighbors in suburbia, but also from people we see at work and from germs our children bring home from school. Motivated by this story, we will investigate the behavior of epidemics, percolation, the Ising model, random walks, and the voter model on the small world graph and compare their behavior to processes on regular lattices. The talk will cover parts of Chapters 5 and 6 of my almost finished book which can be found at http://www.math.cornell.edu/~durrett/
14.10.2005 Speaker: Srinivasan Keshav
Affiliation: University of Waterloo
Title: Tetherless Computing: Why, What, and How
Abstract: A new type of computing is emerging from the convergence of several trends: shrinking computational costs, smaller and more powerful mobile devices, and the proliferation of communication service providers as new broadband devices--such as 802.11 access points--become not only cheap but also allow wireless transmission of data at 500 times the speed of even 3G cellular connections. Interestingly, a seemingly contrary trend of concentrating computational power in centralized, well-connected data centers has also emerged. In the new paradigm of “tetherless computing,” client applications running on small, inexpensive, mobile devices, such as Personal Digital Assistants (PDAs), Radio Frequency ID (RFID) tag readers, and mobile telephones, maintain intermittent broadband wireless connectivity with back-end services running on powerful computers, enabling novel classes of applications.
In this talk, I will outline the nature, scope and social context of tetherless computing. I will then present an architecture for tetherless computing that, unlike existing solutions, provides *both* disconnection and mobility transparency. Our solution leverages the strengths of Distributed Hash Tables and Delay Tolerant Networking (DTN). Early results confirm that our architecture is robust, efficient, and highly scaleable.
This is joint work with Aaditeshwar Seth and Patrick Darragh at the University of Waterloo.
21.10.2005 Speaker: Douglas Eck
Affiliation: Université de Montréal
Area: Machine Learning & Music
Title: Predicting the Similarity Between Two Music Audio Files
Abstract: I will give a short overview of some open questions in music information retrieval (MIR) that have relevance in the domain of machine learning.  I will then focus on the issue of predicting the similarity between two sound files containing music. By way of introducing the problem, I will briefly describe a recent algorithm from our lab that proved successful at predicting the genre and artist of a sound file.  This algorithm won the genre prediction category and placed second in the artist recognition category at a recent international MIR contest (MIREX 2005).  I will spend most of the talk discussing a method to extract long-timescale structure from music audio files. Specifically I will introduce the Autocorrelation Phase Matrix, a data structure that stores intermediate results of the standard autocorrelation function. With
this matrix it is possible to recover phase information that is normally lost in computing autocorrelation. I will discuss why this information is important and will talk about how the Autocorrelation Phase Matrix can be useful for problems like tempo prediction and beat tracking.  I will conclude with speculations on the utility of this structure as a general feature for measuring music similarity.
28.10.2005 Speaker: David Notkin
Affiliation: University of Washington
Title: An Empirical Study of Code Clone Genealogies
Abstract: There has been a broad assumption that code clones are inherently bad and that eliminating clones by refactoring would solve the problems of code clones. To investigate whether this assumption is valid, we developed a formal definition of clone evolution and built a clone genealogy tool that automatically extracts the history of code clones from a source code repository. Using our clone genealogy extractor, we studied the evolution of code clones in two Java open source projects.
Our study of clone evolution contradicts some conventional wisdom about clones; refactoring may not benefit many clones for two reasons. First, many code clones exist in the system for only a short time, disappearing soon after; extensive refactoring of such short-lived clones may not be worthwhile if they are to diverge from one another very soon. Second, many clones, especially long-lived clones that have changed consistently with other elements in the same group, are not locally refactorable due to the programming language limitations. Our study discovers that there are types of clones that refactoring would not help, and it opens up opportunities for clone maintenance tools that target unaddressed classes of clones using clone genealogy information.
This is joint work with Miryung Kim, Vibha Sazawal, and Gail Murphy.
4.11.2005 No colloquium.

11.11.2005 No colloquium.

18.11.2005 Speaker: Frank Pfenning
Carnegie Mellon University
Title: Distributed System Security via Logical Frameworks
Abstract: In an on-going project at Carnegie Mellon University we are implementing a scalable distributed security architecture using smartphones and embedded devices in order to control access to a variety of resources such as office doors and computer accounts. At the heart of the effort is a so-called authorization logic which plays a dual role for policy specification and policy enforcement. A policy is specified as a collection of logical axioms that permit us to reason about who has access to which resources. A policy is enforced by requiring a formal proof of the right to access a resource before that access is granted.
We sketch the overall architecture and then focus on the authorization logic and how it is implemented in a logical framework. We also discuss some recent results that exploit the representation of authorization logic in a logical framework in order to prove important properties of policies, such as non-interference between principals.
25.11.2005 No colloquium.

30.11.2005 Speaker: Rich Sutton
Affiliation: University of Alberta
Title: Empirical Artificial Intelligence
Abstract: I propose that experience --- the explicit sequence of actions and sensations over an agent's life --- should play a central role in all aspects of artificial intelligence. In particular:
  1. Knowledge representation should be in terms of experience. Recent work has shown that a surprisingly wide range of world knowledge can be expressed as predictions of experience, enabling it to be automatically verified and tuned, and grounding its meaning in data rather than in human understanding.
  2. Planning/reasoning should be in terms of experience. It is natural to think of planning as comparing alternative future
    experiences. General methods, such as dynamic programming, can be used to plan using knowledge expressed in predictive form.
  3. State representation should be in terms of experience. Rather than talk about objects and their metric or even topological relationships, we represent states by the predictions that can be made from them. For example, the state "John is in the coffee room" corresponds to the prediction that going to the coffee room will produce the sight of John.

Much here has yet to be worked out. Each of the "should"s above can also be read as a "could", or even a "perhaps could". I am optimistic and enthusiastic because of the potential for developing a compact and powerful theory of AI in the long run, and for many easy experimental tests in the short run.

2.12.2005 Speaker: Janos Pach
Affiliation: City College, CUNY and Renyi Institute, NYU
Title: From Sam Loyd to Laszlo Fejes Toth: The fifteen puzzle and discrete motion planning
Abstract: We discuss a variety of discrete motion planning questions that can be regarded as far-reaching generalizations of the fifteen puzzle. For instance, given an initial position of a system of n congruent circular or square modules in the plane, is it possible to transform it into a prescribed target position, obeying certain natural motion rules? If the answer is yes, what is the smallest number of steps sufficient for completing this task? We survey some recent developments in this field, including the discovery of unexpected connections between questions of this type and old density problems for disk packings, due to Laszlo Fejes Toth (1915-2005).

Speakers of Previous Semesters

McGill | SOCS Last modified: 11/28/05, Jörg Kienzle