Seminar Home
Fall 2012 Schedule
Winter 2013 Schedule
Summer 2013 Schedule
Archives
|
Date
(
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
Abstract: 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
Abstract: 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
|
|
