Skip to content. Skip to navigation
McGill Home SOCS Home
Personal tools
You are here: Home Announcements and Events Seminars Seminar History

Seminar Home
Fall 2013 Schedule
Winter 2014 Schedule
Summer 2014 Schedule

( Fall 2008 )
Category Seminar Info
2008/12/11 Vision, Graphics, and Robotics Place: MC 437 (CIM seminar room)
Time: 11:00 - 12:00
Speaker: Richard Wildes
Affiliation: Dept. of Computer Science & Center for Vision Research, York University, Toronto
Title: Early Representation and Analysis of Visual Spatiotemporal Information
Abstract: When confronted with spatiotemporal data, an intelligent system that must make sense of the ensuing stream can be overwhelmed by its shear quantity. Video and other temporal sequences of images are notorious for the vast amount of raw data that they comprise. An initial organization which affords distinctions that can guide subsequent processing would be a key enabler for dealing efficiently with data of this nature. Toward such ends, an approach to representing visual spacetime with a distributed oriented energy representation will be presented. This representation systematically exposes the structure of visual spacetime in terms of local, multiscale orientation. Advantages of this approach will be illustrated via application to spatiotemporal grouping, tracking and stereo. Biography of Speaker:

Richard Wildes received his Ph.D. from the Massachusetts Institute of Technology in 1989. Subsequently, he joined Sarnoff Corporation in Princeton, New Jersey as a Member of the Technical Staff in the Vision Technologies Group, where he remained until 2001. In 2001, he joined the Department of Computer Science and Engineering at York University, Toronto, where he is an Associate Professor and a member of the Centre for Vision Research. Honours include receiving a Sarnoff Corporation Technical Achievement Award, the IEEE D. G. Fink Prize Paper Award for his Proceedings of the IEEE publication “Iris recognition: An emerging biometric technology” and twice giving invited presentations to the US National Academy of Sciences. His main areas of research interest are computational vision, as well as allied aspects of image processing, robotics and artificial intelligence.

2008/12/04 Vision, Graphics, and Robotics Place: ENGMC 437 (CIM seminar room)
Time: 11:00 - 12:00
Speaker: James Elder
Affiliation: Centre for Vision Research, York University, Toronto
Area: Computer Vision
Title: Cities, Jungles and Contours
Abstract: I will talk about two recent projects. Though quite different in most respects, both studies suggest a special role for contours in early, rapid visual processing. The first study investigates the use of linear perspective cues to estimate the rotation of a sensor relative to the canonical 3D Cartesian frame of an urban scene. Coughlan & Yuille [1] coined this the “Manhattan World” problem. They argued that the problem is best solved using all the information in the image, pooling over all pixel gradients under a generative mixture model of the scene. However, images contain a lot of statistical dependencies, and such ‘naïve Bayes’ methods do not model this redundancy. For example, we [2] and others have shown that images can be reconstructed to a high perceptual fidelity from contour information alone, suggesting that pixels between contours are redundant and can be ignored. Consistent with these prior findings, we show here that by throwing out the 90% of pixels between contours, Manhattan Frame estimation is made twice as accurate relative to previous methods based upon dense gradient maps, and these results can be obtained roughly five times faster. In our second study, we move from the city to the jungle. Much has recently been made of how quickly human observers can detect animals in natural scenes; cortical signals on which detection is based emerge within 100 msec of stimulus onset [3]. Given this speed, it has been suggested that the underlying visual mechanisms must be relatively primitive, but in fact little is known about the exact nature of the visual cues on which these mechanisms rely. Here we investigate the role and dynamics of four potential cues: contour shape, texture, luminance and colour. Our psychophysical results suggest that the fastest mechanisms underlying animal detection in natural scenes use contours as a principal discriminative cue, while slower mechanisms integrate these rapidly-computed contour shape cues with image texture cues. Consistent with prior studies, we find little role for luminance and colour cues throughout the time course of visual processing, even though information relevant to the task is available in these signals. [1] Coughlan, J.M., Yuille, A.L. (2003) Manhattan world: Orientation and outlier detection by Bayesian inference. Neural Computation 15(5) 1063 – 1088. [2] Elder, J.H. (1999) Are edges incomplete? International Journal of Computer Vision, vol. 34, no. 2/3, 97-122. [3] Kirchner, H., & Thorpe, S. J. (2006). Ultra-rapid object detection with saccadic eye movements: Visual processing speed revisited. Vision Research, 46, 1762-1776.
2008/11/28 CQIL - Cryptography and Quantum Information Place: MC103
Time: 11:00 - 12:00
Speaker: Thomas Decker
Affiliation: McGill University
Title: Symmetric measurements attaining the accessible information
Abstract: A theorem of Davies shows that for symmetric quantum states there exists a symmetric POVM that has a simple structure and that maximizes the mutual information. To apply this theorem the representation of the symmetry group has to be irreducible. We obtain similar yet weaker results for reducible representations. The results are applied to the double trines and it is shown with numerical methods that for these states the pretty good measurement is optimal.
2008/11/26 Software Engineering Place: McConnell 103
Time: 10:30 - 11:30
Speaker: Jun Li
Affiliation: McGill University
Title: LLVM: A Compilation Framework for Multi-Stage Optimization
Abstract: LLVM (Low Level Virtual Machine) is a language and target-independent a compiler framework designed to support transparent, life- long program analysis and transformation for arbitrary programs, by providing high-level information to compiler transformations at compile-time, link-time, run-time, and in idle time between runs. LLVM defines a common, low-level code representation in Static Single Assignment (SSA) form, with several novel features: a simple, language-independent type-system that exposes the primitives commonly used to implement high-level language features; an instruction for typed address arithmetic; and a simple mechanism that can be used to implement the exception handling features of high-level languages uniformly and efficiently. The LLVM compiler framework and code representation together provide a combination of key capabilities that are important for practical, lifelong analysis and transformation of programs.
2008/11/21 CQIL - Cryptography and Quantum Information Place: MC320
Time: 11:30 - 12:30
Speaker: Anne Broadbent
Affiliation: University of Waterloo
Area: Quantum information
Title: Quantum public key encryption
Abstract: We present a quantum protocol for information-theoretically secure public key cryptography. Our protocol allows Alice to publish a single-use quantum public key so that, using this key, Bob can send Alice a perfectly private message without having to interact with her. We show that in the case that the message is classical, the ciphertext and decryption operation can be made classical. Time permitting, we will see how this technique can be applied to yield a quantum circuit analogue of the Diffie-Hellman construction and a quantum threshold decryption scheme.
2008/11/12 Algorithms Place: McConnell 103
Time: 10:30 - 11:30
Speaker: Andrew Casey
Affiliation: McGill University
Title: New lexer specification language, MetaLexer
Abstract: MetaLexer is a new lexer specification language. It extends traditional lexer specification languages (e.g. lex, JLex, JFlex) with two significant new features: 1) Separation of lexer state transitions from actions 2) Multi-dimensional extensibility These features make lexers specified in MetaLexer clearer, more modular, and more extensible than lexers specified in traditional syntax. They also make MetaLexer well-suited to specifying lexers for mixed-syntax languages (e.g. AspectJ, which mixes aspect syntax with Java syntax). This talk will provide an overview of the MetaLexer specification language.
2008/11/07 CQIL - Cryptography and Quantum Information Place: MC103
Time: 11:00 - 12:00
Speaker: Howard Barnum
Affiliation: Los Alamos National Laboratory
Area: Quantum Information
Title: Nonclassicality without entanglement enables bit commitment

We investigate the existence of secure bit commitment protocols in the convex framework for probabilistic theories. The framework makes only minimal assumptions, and can be used to formalize quantum theory, classical probability theory, and a host of other possibilities. We prove that in all such theories that are locally non-classical but do not have entanglement, there exists a bit commitment protocol that is exponentially secure in the number of systems used.

Joint work with O. Dahlsten, M. Leifer, B. Toner.

(Co-sponsored by the MITACS Quantum Information Processing project.)

2008/11/05 Software Engineering Place: McConnell 103
Time: 10:30 - 11:30
Speaker: Barthelemy Dagenais
Affiliation: McGill University
Title: Automatically Locating Framework Extension Examples
Abstract: Using and extending a framework is a challenging task whose difficulty is exacerbated by the poor documentation that generally comes with the framework. Even in the presence of documentation, developers often desire implementation examples for concrete guidance. We propose an approach that automatically locates implementation examples from a code base given lightweight documentation of a framework. Based on our experience with concern-oriented documentation, we devised an approach that uses the framework documentation as a template and that finds instances of this template in a code base. The concern instances represent self-contained and structured implementation examples: the relationships and the roles of parts composing the examples are uncovered and explained. We implemented our approach in a tool and conducted a study comparing the results of our tool with results provided by Eclipse committers, showing that our approach can locate examples with high precision.
2008/10/29 Software Engineering Place: McConnell 103
Time: 10:30 - 11:30
Speaker: Eric Bodden
Affiliation: McGill University
Title: Finding Programming Errors Earlier by Evaluating Runtime Monitors Ahead-of-Time
Abstract: Runtime monitoring allows programmers to validate, for instance, the proper use of application interfaces. Given a property specification, a runtime monitor tracks appropriate runtime events to detect violations and possibly execute recovery code. Although powerful, runtime monitoring inspects only one program run at a time and so may require many program runs to find errors. Therefore, in this paper, we present ahead-of-time techniques that can (1) prove the absence of property violations on all program runs, or (2) flag locations where violations are likely to occur. Our work focuses on tracematches, an expressive runtime monitoring notation for reasoning about groups of correlated objects. We describe a novel flow-sensitive static analysis for analyzing monitor states. Our abstraction captures both positive information (a set of objects could be in a particular monitor state) and negative information (the set is known not to be in a state). The analysis resolves heap references by combining the results of three points-to and alias analyses. We also propose a machine learning phase to filter out likely false positives. We applied a set of 13 tracematches to the DaCapo benchmark suite and SciMark2. Our static analysis rules out all potential points of failure in 50% of the cases, and 75% of false positives on average. Our machine learning algorithm correctly classifies the remaining potential points of failure in all but three of 461 cases. The approach revealed defects and suspicious code in three benchmark programs.
2008/10/27 Algorithms Place: Burnside 1205
Time: 16:30 - 17:30
Speaker: Gordon Wilfong
Affiliation: Bell Labs
Title: A Fractional Model of the Border Gateway Protocol (BGP)
Abstract: The Border Gateway Protocol (BGP) is the interdomain routing protocol used in the Internet. Unfortunately, BGP cannot be guaranteed to converge. BGP convergence issues have been studied using a graph theoretic model of BGP called the Stable Paths Problem (SPP). It has been shown that some instances of SPP have no solution and this implies that the corresponding instances of BGP will fail to converge. However, we define a fractional version of SPP and show that any instance of SPP is guaranteed to have a fractional solution. The proof is based on the game theoretic result known as Scarf's Lemma. We then show that a number of well-known graph theoretic problems are actually subproblems of (fractional) SPP. No previous knowledge of BGP or interdomain routing will be assumed; the talk will begin with a brief overview of these issues. This is joint work with Penny Haxell at University of Waterloo.
2008/10/20 Algorithms Place: Burnside 1205
Time: 16:30 - 17:30
Speaker: Peter Winkler
Affiliation: Dartmouth
Title: Branched Polymers
Abstract: A branched polymer is a finite, connected set of non-overlapping unit balls in space. On account of their use as a physical model in chemistry and biology, it is desirable to generate random branched polymers so that behavior comparisons can be made. Previous attempts have used grid models and rejection sampling, but these have severly limited efficiency. However, by rederiving recent work of Bridges and Imbrie using elementary methods, we can generate perfectly random branched polymers in the plane and 3-space. Our methods also permit computation of expected diameter in 3-space, and provide a simple combinatorial proof for a notoriously hard theorem concerning random walks. Joint work with Rick Kenyon (Brown).
2008/10/15 Software Engineering Place: McConnell 103
Time: 10:30 - 11:30
Speaker: Gregory Prokopski
Affiliation: McGill University
Title: Analyzing the Performance of Code-copying Virtual Machines
Abstract: Many popular programming languages use interpreter-based execution for portability, supporting dynamic or reflective properties, and ease of implementation. Code-copying is an optimization technique for interpreters that reduces the performance gap between interpretation and JIT compilation, offering significant speedups over direct-threading interpretation. Due to varying language features and virtual machine design, however, not all languages benefit from codecopying to the same extent. We consider here properties of interpreted languages, and in particular bytecode and virtual machine construction that enhance or reduce the impact of code-copying. We implemented code-copying and compared performance with the original direct-threading virtual machines for three languages, Java (SableVM), OCaml, and Ruby (Yarv), examining performance on three different architectures, ia32 (Pentium 4), x86 64 (AMD64) and PowerPC (G5). Best speedups are achieved on ia32 by OCaml (maximum 4.88 times, 2.81 times on average), where a small and simple bytecode design facilitates improvements to branch prediction brought by code-copying. Yarv only slightly improves over direct-threading; large working sizes of bytecodes, and a relatively small fraction of time spent in the actual interpreter loop both limit the application of codecopying and its overall net effect. We are able to show that simple ahead of time analysis of VM and execution properties can help determine the suitability of code-copying for a particular VM before an implementation of code-copying is even attempted.
2008/10/08 Software Engineering Place: McConnel 103
Time: 10:30 - 11:30
Speaker: Martin Robillard
Affiliation: McGill University
Title: Retrieving Task-Related Clusters from Change History
Abstract: During software maintenance tasks, developers often spend an important amount of effort investigating source code. This effort can be reduced if tools are available to help developers navigate the source code effectively. For this purpose, we propose to search the change history of a software system to identify clusters of program elements related to a task. We evaluated the feasibility of this idea with an extensive historical analysis of change data. Our study evaluated to what extent change sets approximating tasks could have benefited from knowledge about clusters of past changes. A study of 3 500 change sets for seven different systems and covering a cumulative time span of close to 12 years of development shows that less than 12% of the changes could have benefited from change clusters. We report on our observations on the factors that influence how we can use change clusters to guide program navigation.
2008/10/08 Software Engineering Place: McConnel 103
Time: 10:30 - 11:30
Speaker: Barthelemy Dagenais
Affiliation: McGill University
Title: Enabling Static Analysis for Partial Java Programs
Abstract: Software engineering tools often deal with the source code of programs retrieved from the web or source code repositories. Typically, these tools only have access to a subset of a program's source code (one file or a subset of files) which makes it difficult to build a complete and typed intermediate representation (IR). Indeed, for incomplete object-oriented programs, it is not always possible to completely disambiguate the syntactic constructs and to recover the declared type of certain expressions because the declaration of many types and class members are not accessible. We present a framework that performs partial type inference and uses heuristics to recover the declared type of expressions and resolve ambiguities in partial Java programs. Our framework produces a complete and typed IR suitable for further static analysis. We have implemented this framework and used it in an empirical study on four large open source systems which shows that our system recovers most declared types with a low error rate, even when only one class is accessible.
2008/10/06 Algorithms Place: Burnside 1205
Time: 16:30 - 17:30
Speaker: Simon Gravel
Affiliation: Cornell University
Title: Think locally, act globally: how to search with iterated maps
Abstract: We show how simple dynamical systems can be designed to search efficiently for solutions of difficult constraint problems such as Boolean satisfaction, sphere packing, and the folding of proteins. In this approach constraints are seen as geometrical objects, and the solutions are encoded in attractive fixed points of the dynamical systems. We compare the performance of the resulting general-purpose search strategy to the state-of-the-art in Boolean satisfaction and packing problems, and discuss some unexpected sphere arrangements found by this approach.
2008/09/29 Algorithms Place: Burnside 1205
Time: 16:30 - 17:30
Speaker: Christophe Weibel
Affiliation: McGill
Title: f-vectors of Minkowski sums of polytopes
Abstract: Minkowski sum is a basic operation with applications in all kind of fields. The combinatorial properties of sums of polytopes are however not well known. We present in this talk some recent results and bounds on the number of faces sums of polytopes can have in function of their summands.
2008/09/24 CQIL - Cryptography and Quantum Information Place: McConnell 103
Time: 10:30 - 11:30
Speaker: Bill Rosgen
Affiliation: University of Waterloo
Title: Additivity and Random Unitary Channels

The question of the additivity of the classical capacity is one of the central problems in quantum information theory. This is the problem of whether entangling inputs to quantum channels can improve the rate at which classical information can be transmitted. In this talk progress on the additivity conjecture and some closely related conjectures are discussed.

One approach to resolving these conjectures is to consider simpler classes of quantum channels, in the hope that these classes can give insight into the general problem. Such a class is given by the random unitary channels, where a channel in this class is given by a convex combination of unitary channels. Using a scheme to approximate any quantum channel by one that is random unitary, it can be shown that the problem of the additivity of the minimum output entropy can be equivalently restricted to the random unitary channels. This approximation scheme also has applications to the problem of distinguishing quantum circuits, and so it is hoped that the construction is of independent interest.

2008/09/22 Math Place: Burnside 1205
Time: 16:30 - 17:30
Speaker: Yoshiaki Oda
Affiliation: Keio University, Japan
Title: Special cases of the Vehicle Routing Problem
Abstract: The Traveling Salesman Problem (TSP) is one of the most famous NP-hard problems. So, much works have been done to study polynomially solvable cases, that is, to find good conditions for distance matrices such that an optimal tour can be found in polynomial time. These good conditions give some restriction on the optimal tour, for example, Monge property, Demidenko conditions and so on. Moreover, it is significant to find algorithms which compute the shortest tour with the restriction. A pyramidal tour appears frequently in those concepts. For a given weighted graph G, a vertex v of G, and an integer k, the Vehicle Routing Problem (VRP) is to find a minimum weight connected subgraph F of G such that F is a union of at most k cycles sharing only one vertex x. In this talk, we apply good conditions for the TSP to the VRP. At first, we define a new concept which is an extension of a pyramidal tour and we show that a minimum weight connected subgraph among them can be computed in polynomial time. Next, we show that if a given weighted graph satisfies several conditions for the TSP, an optimal solution for the VRP can also be computed in polynomial time.
2008/09/15 Math Place: Burnside 1205
Time: 16:30 - 17:30
Speaker: Caterina De Simone
Affiliation: CNR, Rome
Title: Optimal colouring of the edges of the join of two regular graphs
Abstract: We prove that the edges of every graph G that is the join of two regular graphs can be coloured with Delta(G) colours. The proof yields a combinatorial algorithm to optimally colour the edges of this type of graphs. This is a joint work with Anna Galluccio