Fall 2004

Date Speaker and Abstract
10.9.2004 Speaker: Alan Frieze
Affiliation: Carnegie Mellon University
Area: Applications of Probabilistic Combinatorics in Theoretical Computer Science
Title of Talk: Random Graph Models of "Real World Networks"
Abstract: Large real world networks can perhaps best be viewed as the outcomes of random processes. Classical random graph models seem not to be good descriptions of the process. In particular, there is a problem in reconciling the typical degree sequence. Other models have been proposed and we will review them from a mathematical point of view.

17.9.2004 Speaker: Joelle Pineau
Affiliation: McGill University
Title: Efficient Decision-Making under Uncertainty for Real-World Robotics
Abstract: For robots to have an impact in real-world environments, including homes, offices, and hospitals, they must be able to operate reliably despite the presence of uncertainty. Uncertainty arises as a result of random action outcome, noisy or incomplete sensor information, as well as poor modeling. The Partially Observable Markov Decision Process (POMDP) provides a rich framework for planning under uncertainty, but exact solutions are most often computationally intractable. New algorithms which leverage structural properties of the domain have recently improved the scalability of POMDP planning, to the point where it can be applied to a variety of robot planning tasks. I present two such algorithms: Point-Based Value Iteration (PBVI) and Hierarchical Policy-Contingent Abstraction (PolCA+), and show results obtained from applying these to large robot problems, including the high-level control of a robotic nursing assistant.

24.9.2004 Speaker: Karan Singh
Affiliation: University of Toronto
Area: Graphics
Title of Talk: Psychorealism : Artist Driven Interactive Graphics
Abstract: Computer graphics is rapidly striding toward a state where the real and virtual in an animation blend indidtinguishably together. Beyond the mere exercise of recreating reality, the computer animated short film "Ryan" aims to show the realism of the messy, chaotic and glorious entity we call "human nature". director Chris Landreth refers to this pursuit as "psychorealism". This talk shows two artist driven techniques, quintessential to the film, that push the limits of interactive data modeling, animation and visualization. The first is in the rendering domain where artists struggle to transcend the CG pin-hole camera, while they almost always deviate from strict linear perspective in traditional media. The talk will develop a conceptual framework to construct and interactively control shape and illumination under nonlinear projection and adress their implementation within a conventional animation pipeline. The second deals with the construction and interactive control of sparse geometry. While geometric models today can capture the realism of physical objects, the visual appeal of sparse geometric representations like line drawings and wire sculptures is timeless. Inspired by such representations, the talk will present a new geometric curve primitive wih stiffness and elasticity properties that wraps and bends interactively around scene geometry.

1.10.2004 Speaker: Patrick Hayden
Affiliation: McGill University
Area: Quantum Computing
Title of Talk: The Role of Privacy in Quantum Information Theory
Abstract: The invention of quantum cryptography in the 1980s demonstrated that the laws of quantum mechanics can be exploited to develop unconditionally secure cryptography. The discovery of teleportation a decade later then provided a natural way of building an encrypted, authenticated channel out of quantum entanglement. These pivotal advances suggested the existence of an intrinsic connection between communication and privacy in quantum mechanics that has recently been solidified from a number of directions.
In this talk, I'll survey some of the ideas underlying these recent advances. First, I'll sketch how an improved method for encrypting quantum states leads directly to a correspondingly more efficient variant of teleportation. Next, I'll indicate how to build an intrinsically secure quantum channel, that is, one that is authenticated and encrypted at a negligible cost. Finally, I'll give a very brief account of how the connection between communication and privacy has been exploited in quantum Shannon theory, both as a unifying principle and a technical tool.

8.10.2004 Speaker: Kenneth Birman
Affiliation: Cornell University
Area: Distributed Systems
Title of Talk: Scalability: the New Frontier for Distributed Systems Research
Abstract: A new generation of massive distributed systems has emerged to challenge assumptions about how to build robust networked applications. For example, Google is said to have more than 100,000 computers in its data centers, and centers containing 5,000 to 10,000 are becoming commonplace. Even larger systems will arise as we retrofit distributed monitoring, management and control infrastructure onto the electric power grid; deploy wireless sensor networks to help combat forest fires; create new tools to help commuters in congested urban regions; direct clients in crowded theme parks. Technologies familiar from smaller client-server distributed settings just don't scale to the necessary degree, and they require a tremendous amount of human hand-holding, especially if disrupted by failure.
This talk explores a promising new option: so-called "epidemic" (or "gossip") protocols implemented in a peer-to-peer architecture. The approach yields a completely new style of distributed solution: one in which guarantees are probabilistic, but so likely as to be certain. Moreover, it leads to novel and very exciting new software architectures that self-organize, self-configure and self-repair.

15.10.2004 Speaker: Peter Selinger
Affiliation: University of Ottawa
Area: Mathematical Logic, Category Theory, (Quantum) Programming Language Design, Security
Title of Talk: Towards a Quantum Programming Language
Abstract: In this talk, I will propose the design of a programming language for quantum computing. Traditionally, quantum algorithms are usually expressed at the hardware level, for instance in terms of the quantum circuit model or quantum Turing machines. These approaches do not encourage structured programming or abstractions such as data types. In my talk, I will describe the syntax and semantics of a simple quantum programming language with high-level features such as loops, recursive procedures, and structured data types. The language is functional in nature, statically typed, free of run-time errors, and it has an interesting denotational semantics in terms of complete partial orders of superoperators.

22.10.2004 Speaker: Martin Robillard
Affiliation: McGill University
Area: Software Engineering
Title of Talk: Representing High-level Concerns in Source Code
Abstract: Evolving a software system often requires discovering and understanding the implementation of different concerns, or high-level concepts that a developer must consider as a unit. Concerns may correspond to system features (e.g., the auto-save feature in a text editor), or to more technical issues such as enforcing a security policy in a distributed system. Correctly finding and understanding the implementation of a concern whose code is not well encapsulated in a module is a critical and difficult task which, if not done properly, can result in the introduction of costly regression faults in a system.
In this talk, I will present a model, technique, and tool I developed to help software engineers find, understand, and document how high-level concerns are implemented in a system. The model, called Concern Graph, captures the implementation of a concern independently of the physical representation of the code (e.g., lines in files, indentation). The concern graph model also tolerates a certain degree of inconsistency between a description of a concern in source code and an actual code base, making it possible to reuse concern descriptions across different versions of a system.
These ideas have been implemented in a software tool called FEAT that allows developers to iteratively and semi-automatically build and use concern graphs during software evolution tasks. Empirical studies with FEAT has shown that concern graphs are inexpensive to create, are helpful during program evolution tasks, and can be reused in different versions of a system.

29.10.2004 Speaker: Mathieu Blanchette
Affiliation: McGill University
Area: Bioinformatics
Title of Talk: Reverse Engineering the Human Genome
Abstract: The human genome is one of the largest program ever "written" and it is the most adaptable, flexible, and fault-tolerant. It is executed on slow hardware with very fuzzy rules, and high failure rates: the cell. It has been written through a Billion years of massively parallel trial-and-errors, which has resulted in a complex and haphazard structure. And the documentation s**ks! The goal of this talk is to give an overview of the methods that have recently been developed for reverse engineering the human genome, in other words for giving a functional annotation to its different regions. I will focus mostly on the process of abstracting biological knowledge into a mathematical or algorithmic framework, which for me is the main challenge in bioinformatics. I will particularly illustrate how understanding of the programmer (evolution) can give insights about the program (the genome). The result will be a set of clean computational problems, some of which can be solved by standard algorithmic or machine learning approaches that will briefly be mentioned, others requiring novel techniques. Biological applications considered will include the detection of protein-coding genes, regulatory elements, RNA genes, etc. The talk will be aimed at computer scientists who forgot most of their college biology.

5.11.2004 Speaker: Faith Fich
Affilitation: University of Toronto
Area: Complexity Theory
Title of Talk: How Difficult is it to Take a Snapshot?
Abstract: The atomic snapshot object is an important and well-studied primitive in distributed computing that allows processes to obtain a consistent view of an entire block of shared memory, even if updates are being performed concurrently. This talk will describe applications of this object, present some implementations of it from registers in both asynchronous and synchronous distributed systems, and discuss some recent lower bounds.

12.11.2004 Speaker: Anindya Banerjee
Affiliation: Kansas State University
Area: Programming Languages / Security
Title of Talk: Secure Information Flow and Access Control in a Java-like Language
: Confidentiality is a security policy that asserts that secret inputs to an application cannot be deduced by an attacker through the attacker's observation of the application's public output. How does one provide high assurance that the end-to-end behaviour of an application, programmed in a Java-like language, satisfies confidentiality? We show, via examples, how different features of object-oriented languages, e.g., dynamic dispatch, method call, aliasing, object allocation, can all lead to violations of confidentiality. These examples provide the intuitions for a type-based information flow analysis that disallows programs with insecure information flow and thus satisfies end-to-end confidentiality. This satisfaction of confidentiality is formalized by means of a theorem termed "noninterference theorem" in the security literature.
We extend our information flow analysis to tackle the problem of detecting possibly malevolent mobile code in Java-like languages. In such programs, dynamic access control, via the stack inspection mechanism, is predominantly used in current practice. While access control is often used with the intent of enforcing confidentiality and integrity policies, few rigorous connections have been made between information flow and runtime access control. We investigate a design pattern by which the stack inspection mechanism can be used to achieve confidentiality. A type-based static analysis admits programs fitting this pattern. The analysis ensures noninterference.

19.11.2004 No colloquium!
26.11.2004 Speaker: Gregor Kiczales
Affiliation: University of British Columbia
Area: Aspect-Oriented Programming
Title of Talk: Aspect-Oriented Programming
Abstract: Aspect-oriented programming (AOP) is a new technique for improving expressiveness and modularity in software. The central idea in AOP is that while the hierarchical and block structured modularity mechanisms of object-oriented and procedural programming are extremely powerful, they are unable to modularize all concerns of interest in complex systems. Instead in any complex system there will be aspects of the implementation which crosscut the hierarchical decomposition, and so cannot be modularized using traditional techniques.
AOP does for concerns that are naturally crosscutting what OOP did for concerns that are naturally hierarchical -- it provides language support that allows crosscutting structure to be explicit, clear and modular. Once they are well modularized, all the usual benefits of better modularity apply: including code that is easier to design, develop, maintain and reuse.
In the talk I will present the motivation and basic idea of AOP, I will outline open research issues and summarize what's happening in industry.

McGill | SOCS Last modified: 2/19/05, Jörg Kienzle