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 2014 Schedule
Winter 2015 Schedule
Summer 2015 Schedule
Archives

Date
( Winter 2008 )
Category Seminar Info
2008/04/16 CQIL - Cryptography and Quantum Information Place: MC320
Time: 10:00 - 11:00
Speaker: Louis Salvail
Affiliation: Aarhus/McGill/UdM
Title: On the Power of Two-Party Quantum Cryptography
Abstract: In this talk, the power of two-party quantum cryptography is investigated. We provide a framework allowing to determine how much information is leaked to a dishonest player by any quantum protocol implementing a classical two-party primitive under the sole assumption that the protocol is correct. All our results apply even if the adversary is restricted to be quantum honest-but-curious. In this model, quantum communication is more powerful than its classical counterpart but it is also severely restricted. We show that the only two-party primitives admitting non-leaking quantum protocols are the trivial ones. On the other hand, any non-trivial primitive admits a quantum protocol that even if it is leaking, provides an implementation that cannot be matched by any classical protocol. Our framework is applied to different universal two-party primitives. We determine the minimum leakage of any quantum protocol for several flavors of oblivious transfers. In particular, we show that quantum protocols for oblivious transfer against honest-but-curious adversaries approach triviality as the length of the strings to be transmitted increases.
2008/04/15 General Place: McConnell 103
Time: 15:30 - 16:30
Speaker: Derek Dreyer
Affiliation: Max Planck Institute for Software Systems
Title: Mixing Up the ML Module System
Abstract: Biography of Speaker:

Derek obtained his Phd from CMU in 2005 working with Bob Harper on the SML Module system. From January 2005 to December 2007,he was a research assistant professor at the Toyota Technological Institute at Chicago (TTI-C). Since January 2008, he is an independent researcher (tenure-track faculty) at the Max Planck Institute for Software Systems (MPI-SWS) in Saarbracken, Germany, heading the Type Systems and Functional Programming group.


2008/04/11 CSE - Computational Science & Engineering Place: MC103
Time: 14:30 - 15:30
Speaker: Wolfgang Bangerth
Affiliation: Department of Mathematics, Texas A&M University
Title: Numerics for Inverse Problems in Biomedical Imaging
Abstract:

In many of the modern biomedical imaging modalities, the measurable signal can be described as the solution of a partial differential equation that depends nonlinearly on the tissue properties (the ”parameters”) one would like to image. Consequently, there are typically no explicit solution formulas for these so-called ”inverse problems” that can recover the parameters from the mea- surements, and the only way to generate body images from measurements is through numerical approximation.

The resulting parameter estimation schemes have the underlying partial differential equations as side-constraints, and the solution of these optimization problems often requires solving the partial differential equation thousands or hundred of thousands of times. The development of efficient schemes is therefore of great interest for the practical use of such imaging modalities in clinical settings. In this talk, the formulation and efficient solution strategies for such inverse problems will be discussed, and we will demonstrate its efficacy using examples from our work on Optical Tomography, a novel way of imaging tumors in humans and animals. The talk will conclude with an outlook on even more complex problems that attempt to automatically optimize experimental setups to obtain better images.


2008/04/03 Faculty Candidate Talk Place: MC497
Time: 9:30 - 10:30
Speaker: Vida Dujmović
Affiliation: Carleton University in Ottawa
Title: Geometric Reconfigurations and Crossing Number
Abstract: The first result concerns geometric reconfigurations. A geometric graph is a graph whose vertices are distinct points in the plane and whose edges are straight-line segments between pairs of points. To untangle a geometric planar graph means to move some of the vertices so that the resulting geometric graph has no crossings. Pach and Tardos [Discrete Computational Geometry, 2002] asked if every n-vertex geometric planar graphs can be untangled while keeping at least nε vertices fixed. We answer this question in the affirmative with ε = ¼. The previous best known bound was Ω((long n / log log n)1/2).

The second result concerns the crossing number. The crossing number of a graph is the minimum number of crossings in a drawing of the graph in the plane. We prove that every graph G that does not contain a fixed graph as a minor has crossing number Ο(Δn), where G has n vertices and maximum degree at most Δ. This dependence on Δ and n is best possible.
Biography of Speaker:

After having received an Honors Bachelor in Engineering from the University of Zagreb, in Croatia, Vida Dujmović came to McGill University to do a Master and a Doctorate in Computer Science. She is presently a Research Fellow in the Computational Geometry Lab at Carleton University in Ottawa.


2008/04/02 CQIL - Cryptography and Quantum Information Place: MC320
Time: 10:30 - 11:30
Speaker: Tsuyoshi Ito
Affiliation: NII/McGill
Title: Limiting cheating by entangled dishonest provers in cooperative games
Abstract:

A central question in quantum information theory and computational complexity is how powerful nonlocal strategies are in cooperative games with imperfect information, such as multi-prover interactive proof systems. Kempe, Kobayashi, Matsumoto, Toner and Vidick introduced two methods to modify two-prover one-round classical-message games so that provers cannot benefit much from sharing a prior entanglement. By using these methods, they proved NP-hardness of distinguishing entangled games where provers win with probability 1 from those where provers win with probability at most 1-1/poly(n), where n is the number of possible questions. In this talk, we consider modification of three-prover one-round classical-message games and apply their analysis techniques to prove that the same problem is NP-hard for three-prover one-round classical-message games with one-bit answers, and for two-prover one-round classical-message games with two-bit answers. These results are tight in the sense that the problem is known to be in P for two-prover one-round classical-message games with one-bit answers.

The talk is based on joint works with Hirotada Kobayashi (NII), Keiji Matsumoto (NII), Daniel Preda (UC Berkeley), Xiaoming Sun (Tsinghua University) and Andrew C.-C. Yao (Tsinghua University).


2008/04/02 Faculty Candidate Talk Place: MC437
Time: 9:30 - 10:30
Speaker: Alena Shmygelska
Affiliation: Stanford University
Title: Novel Search Methods for De Novo Protein Structure Prediction
Abstract: Proteins form the very basis of life. If we were to open up any living cell, we would find, apart from DNA and RNA molecules whose primary role is to store genetic information, a large number of different proteins that comprise the cell itself (for example the cell membrane and organelles), as well as a diverse set of enzymes that catalyze various metabolic reactions. Functions of proteins are the consequences of their functional tree-dimensional shape. Therefore, to control these versatile properties, we need to be able to predict the structure of proteins; in other words, solve the protein folding problem. In this talk, I will address the protein folding problem by introducing new randomized search methods that focus on efficient sampling of coarse-grained and biologically relevant protein models.

Particularly: (1) nature-inspired self-organizing search metaphors such as Extremal Optimization, and (2) adaptive randomized optimization search methods based on variants of Monte Carlo methods will be discussed. The leading research objective for this work is to elucidate the process of protein folding by means of novel computational approaches
Biography of Speaker:

Alena Shmygelska completed a Physics and Biomedical Engineering Honors Program at Dnepropetrovsk State University in Ukraine, and a B.Sc. with Highest Honors in Computer Science at Slippery Rock University in Pennsylvania. Alena presently holds a Postdoctoral Fellow position at Stanford University in California, which she has accepted after completion of a Ph.D. in Computer Science at the University of British Columbia in 2006.


2008/03/31 Math Place: Burnside 1205
Time: 16:30 - 17:30
Speaker: Amram Meir
Affiliation: York University
Title: Cutting squares and cubes asymptotically fairly
Abstract:

A pretty mathematical "folklore" problem (solvable easily by induction) states : Given a square and an integer n > 5, it is possible to cut the given square into exactly n squares? (It is not required in general, of course , that the cut squares be equal in size).

Two problems arise naturally:

(i) Is a similar statement true for cutting a cube into a given number of cubes in dimensions d = 3,4,..., (with the value 5 replaced possibly by some other number depending on d)?

(ii) Can the procedure be done "asymptotically fairly" in the sense that for suitable cuttings the ratios the size of the largest square (cube) cut / the size of the smallest square (cube) cut will converge to 1, as n approaches infinity?

The talk will provide some answers as well as some details of (or hints for) proofs.


2008/03/28 CSE - Computational Science & Engineering Place: MC103
Time: 14:30 - 15:30
Speaker: Mohamed Oussama Damen
Affiliation: Electrical and Computer Engineering Department, University of Waterloo
Title: TBA
Abstract:
2008/03/26 CQIL - Cryptography and Quantum Information Place: MC320
Time: 10:00 - 11:00
Speaker: Francois Le Gall
Affiliation: ERATO-SORST
Title: Quantum Property Testing of Group Solvability
Abstract: Testing efficiently whether a finite set with a binary operation over it, given as an oracle, is a group is a well-known open problem in the field of property testing. Recently, Friedl, Ivanyos and Santha have made a significant step in the direction of solving this problem by showing that it it possible to test efficiently whether the input is an Abelian group or is far, with respect to some distance, from any Abelian group. In this work, we make a step further and present an efficient quantum algorithm that tests whether the input is a solvable group, or is far from any solvable group.
2008/03/20 Faculty Candidate Talk Place: McConnell Engineering Building, Room 437
Time: 9:30 - 10:30
Speaker: Erin Wolf Chambers
Affiliation: University of Illinois at Urbana-Champaign, Department of Computer Science
Title: Computing Short Yet Interesting Cycles
Abstract: Numerous applications in areas such as graphics, sensor networks, and robotics call for finding small topological features, such as small holes or cycles, in order to simplify or analyze the object. Two fundamental problems in this area are finding non-contractible cycles, or cycles that cannot be continuously deformed to a point, and finding non-separating cycles, or cycles whose removal does not disconnect the surface. This talk will survey current algorithms for addressing these problems as well as several related open questions which remain in the area. No prior knowledge of topology is necessary.
Biography of Speaker:

Erin Wolf Chambers received a B.Sc. in Computer Science (Minor in Mathematics) in 2003 from the University of Illinois at Urbana-Champaign, and continued her graduate studies at that institution where she will be presented with a Ph.D. Diploma in Computer Science this spring.


2008/03/18 Bioinformatics Place: MC437
Time: 9:30 - 10:30
Speaker: Theodore Perkins
Affiliation: McGill Centre for Bioinformatics
Title: Cellular Information Processing: How to Think Like Bacteria
Abstract:

Living cells are extraordinarily complex---in the molecules that comprise them, in the interactions between those molecules, and in their resulting dynamics. As our models of biomolecular systems grow more accurate and complex, we begin to lose the ability to understand the models themselves. This has prompted a search for underlying principles that can help us explain the organization of these systems and interpret their function. In this talk, I will discuss my work on the information processing capabilities of gene regulation systems. I will describe how even simple biochemical models show that gene regulatory systems can in principle ``compute" solutions to Bayesian discrimination problems and other dynamical signal processing tasks---useful capabilities for cells, which are constantly bombarded by noisy, uncertain information about their environment.

I will also describe the inverse Bayesian discrimination problem, and show that probabilistic decision-making is not just possible in principle, but consistent with detailed measurements of the complex regulatory behavior of the lac operon in E. coli. These observations suggest that far more sophisticated information processing than was previously suspected may be taking place in living cells, implemented by means of chemical reactions. Indeed, in the second part of the talk, I will show that nearly arbitrary analog computations can be approximated by typical gene regulatory mechanisms. This fact, however, may be obscured by standard methods for measuring gene function---an important caveat for experimentalists. This work broadens our understanding of the computational capabilities of gene regulatory systems, providing new hypotheses for the interpretation of natural systems, and suggesting possibilities for the design of synthetic gene networks.


Biography of Speaker:

Ted Perkins received his doctoral degree at the University of Massachusetts at Amherst in May 2002. He has a M.Sc. from the University of Wisconsin-Madison, and completed his undergraduate studies at Carleton College where he received a B.A with a major in Computer Science. He presently holds the position of Assistant Professor (Special Category) in the McGill Bioinformatics Centre.


2008/03/17 Math Place: Burnside 1205
Time: 16:30 - 17:30
Speaker: Panagiotou Konstantinos
Affiliation: ETH Zurich
Title: Extremal Subgraphs of Random Graphs
Abstract:

Let K_l denote the complete graph on l vertices. We prove that there is a constant c = c(l) > 0, such that whenever p >= n^{-c}, with probability tending to 1 when n goes to infinity, every maximum K_l-free subgraph of the binomial random graph G_{n, p} is (l-1)-partite. This answers a question of Babai, Simonovits and Spencer.

The proof is based on a tool of independent interest: we show, for instance, that the maximum cut of almost all graphs with M edges, where M >> n, is nearly unique. More precisely, given a maximum cut C of G_{n, M}, we can obtain all maximum cuts by moving at most O (n^{3/2}/M) vertices between the parts of C.

Joint work with Graham Brightwell and Angelika Steger.



2008/03/17 General Place: TR0070
Time: 14:30 - 15:30
Speaker: Marcel Mitran
Affiliation: IBM Toronto Lab
Area: Systems, compilers
Title: System Z and JIT Compilation
Abstract: Where did the 8-bit byte come from? What was the first commercially available out-of-order processor? What is the only platform that can boast that 95% of Fortune 500 companies store their mission critical financial data on it? What platform is so dependable that it goes down for no more than 5 minutes a year and has a mean-time-to-failure of around 40 years? This talk will introduce System z -- IBMs mainframe technology. The rich history of the platform will be reviewed. The hardware, operating system and ISA will be described. IBMs Java Just-In-Time compiler and its exploitation of the architecture will be introduced.
2008/03/13 CQIL - Cryptography and Quantum Information Place: MC100N
Time: 10:00 - 11:00
Speaker: Fatih Ozaydin
Affiliation: Osaka University
Title: On Landauer's Principle
Abstract:
2008/03/12 CQIL - Cryptography and Quantum Information Place: MC320
Time: 10:00 - 11:00
Speaker: Min-Hsiu Hsieh
Affiliation: University of Southern California
Title: A general method for studying quantum error correction
Abstract: In this talk, I will present a general method for studying quantum error correction codes (QECCs). This method not only provides us an intuitive way of understanding QECCs, but also leads to several extensions of standard QECCs, including the operator quantum error correction (OQECC), the entanglement-assisted quantum error correction (EAQECC), and the newly developed QECCs that can transmit both classical and quantum information. Biography of Speaker:

Min-Hsiu Hsieh received his B.S. and M.S. degree from National Taiwan University, Taiwan. He is currently a Ph.D. candidate under the guidance of Prof. Todd Brun and Prof. Igor Devetak. He won the best student paper award from Viterbi School of Engineering in 2007. His research interests are on quantum information theory and quantum coding theory.


2008/03/10 Faculty Candidate Talk Place: McConnell Engineering Building, Room 437 (Cancelled)
Time: 9:30 - 10:30
Speaker: Florian Markowetz
Affiliation: Princeton University
Title: Computational methods to analyze large-scale and high-dimensional gene perturbation screens
Abstract: Recent advances in biotechnology have produced a wealth of genomic data,which capture a variety of complementary cellular features. One of the key sources of data stems from observing phenotypes after perturbing the activity of target genes in the cell. While these data promise to yield key insights into molecular biology and medicine, much of the information present remains underutilized because of the lack of scalable approaches for detecting signals across large, diverse data sets. In my talk I will introduce computational methods to analyze gene perturbation screens from different perspectives and in combination with other sources of data to gain a detailed understanding of cellular mechanisms. In particular, my talk covers three different approaches: First, I will describe Nested Effects Models, a novel methodology to efficiently infer features of pathways from the nested structure of observed perturbation effects. Second, I will introduce a probabilistic model that integrates high-throughput data with gene perturbation experiments and existing hand-curated biological knowledge-bases. Third, I will show results of a study on the effects of knocking down Nanog, one of the key transcription factors regulating self-renewal and differentiation in embryonic stem cells. Our computational results reveal a central part of the regulatory network that revolves around Nanog and guide further research on Nanog's role in differentiation of mouse ES cells. Biography of Speaker:

Florian Markowetz holds degrees in Mathematics and Philosophy from the University of Heidelberg, and a Ph.D. in Computational Biology from the Free University Berlin. His Ph.D. thesis was honored by the Max Planck Society with an Otto-Hahn medal. He is presently pursuing postdoctoral research at Princeton University.


2008/03/10 General Place: Trottier 0070 (Cancelled/Postponed)
Time: 14:30 - 15:30
Speaker: Marcel Mitran
Affiliation: IBM Toronto Lab
Area: Systems, Compilers
Title: System Z and JIT Compilation (Cancelled/Postponed)
Abstract: Where did the 8-bit byte come from? What was the first commercially available out-of-order processor? What is the only platform that can boast that 95% of Fortune 500 companies store their mission critical financial data on it? What platform is so dependable that it goes down for no more than 5 minutes a year and has a mean-time-to-failure of around 40 years? This talk will introduce System z -- IBMs mainframe technology. The rich history of the platform will be reviewed. The hardware, operating system and ISA will be described. IBMs Java Just-In-Time compiler and its exploitation of the architecture will be introduced.
2008/03/07 CSE - Computational Science & Engineering Place: MC103
Time: 14:30 - 15:30
Speaker: Chris Paige
Affiliation: School of Computer Science, McGill University
Area: Dedicated to Gene Golub (1932-2007)
Title: The bidiagonalization algorithms of Gene Golub and William Kahan
Abstract: In 1965 Gene Golub (at Stanford) and (Canadian) William Kahan (who was then at the University of Toronto), published: “Calculating the singular values and pseudo-inverse of a matrix”. Journal of the Society for Industrial and Applied Mathematics, Series B, Numerical Analysis, 2:205–224, 1965. (Paper #7 in Nick Trefethen’s list of 13 classic papers in applied mathematics). In this were two algorithms for effectively orthogonally transforming a rectangular matrix into bidiagonal form. Their main purpose was computing the singular value decomposition (SVD), and this led to the SVD algorithm by Golub and Reinsch (1970) that we essentially use today. These bidiagonalization algorithms took on a life of their own—they became the basis for several useful algorithms, both for direct and iterative methods. We will mention some of these, including a fascinating new application suggested by Sutton and Edelman (2005) for computing the CS-Decomposition (CSD) of an orthogonal matrix. We will also sketch some recent unexpected results involving applications of these two bidiagonalization algorithms. Biography of Speaker:

Chris Paige is an Emeritus Professor in the School of Computer Science, McGill University. In 2004, he was awarded the Bernard Bolzano Honorary Medal for Merit in the Mathematical Sciences.


2008/03/06 Vision, Graphics, and Robotics Place: MC437
Time: 15:00 - 16:00
Speaker: Daniel Martinec
Affiliation: Czech Technical University
Area: Computer Vision
Title: Robust Rotation and Translation Estimation in Multiview Reconstruction
Abstract: It is known that the problem of multiview reconstruction can be solved in two steps: first estimate camera rotations and then translations using them. This work presents new robust techniques for both of these steps. (i) Given pair-wise relative rotations, global camera rotations are estimated linearly in least squares. (ii) Camera translations are estimated using a standard technique based on Second Order Cone Programming. Robustness is achieved by using only a subset of points according to a new criterion that diminishes the risk of chosing a mismatch. It is shown that only four points chosen in a special way are sufficient to represent a pairwise reconstruction almost equally as all points. This leads to a significant speedup. In image sets with repetitive or similar structures, non-existent epipolar geometries may be found. Due to them, some rotations and consequently translations may be estimated incorrectly. It is shown that iterative removal of pairwise reconstructions with the largest residual and reregistration removes most non-existent epipolar geometries. The performance of the proposed method is demonstrated on difficult wide base-line image sets. Biography of Speaker:

Daniel Martinec recently completed his Ph.D. research at the Czech Technical University.


2008/03/05 CQIL - Cryptography and Quantum Information Place: MC320
Time: 10:00 - 11:00
Speaker: Nicolas Dutil
Affiliation: McGill University
Title: Assisted entanglement of distillation
Abstract: In this talk, we analyze the following situation: given a tripartite mixed state, what is the optimal EPR rate distillable between Alice and Bob with the help of Charlie under LOCC?.We give upper and lower bounds for the optimal EPR rate achievable for this problem. The upper bound is formulated using the entanglement of assistance as a building block. The lower bound is obtained by considering a modified version of the problem where classical communication is one-sided. This modified version gives rise to a quantity similar to the entanglement of assistance:the assisted one-way entanglement capacity of a tripartite mixed state. We generalize these problems to arbitrary multipartite mixed-state and look at upper and lower bounds. Biography of Speaker:

Nicolas Dutil is a Ph.D. candidate in the School of Computer Science at McGill.


2008/02/22 CSE - Computational Science & Engineering Place: MC103
Time: 14:30 - 15:30
Speaker: Miguel Anjos
Affiliation: Department of Management Sciences, University of Waterloo
Title: Large-Scale Fixed-Outline Floorplanning Design Using Convex Optimization
Abstract:

The floorplanning problem consists of arranging a set of rectangular modules on a rectangular chip area so that to optimize an appropriate measure of performance. This problem is known to be NP-hard, and is particularly challenging if the chip dimensions are fixed, which creates a so-called fixed-outline floorplanning problem. Floorplanning is becoming increasingly important as a tool to design flows in the hierarchical design of Application Specific Integrated Circuits and System-On- Chip. Therefore, it has received much attention recently due to the increasingly high complexity of modern chip design. We propose a two-stage optimization methodology to solve the floorplanning problem. In the first stage, an attractor-repeller convex optimization model provides the relative positions of the modules on the floorplan. The second stage places and sizes the modules using second-order cone optimization. With the relative positions of modules obtained from the first stage, a Delaunay triangulation is employed to obtain a planar graph and hence a relative position matrix to connect the two stages. Experimental results on standard benchmarks demonstrate that we obtain significant improvements on the best results in the literature for these benchmarks. Most importantly, our methodology provides greater improvement over other floorplanners as the number of modules increases.

This is joint work with Chaomin Luo (Waterloo) and Anthony Vannelli (Guelph).


2008/02/18 Faculty Candidate Talk Place: MC437
Time: 9:30 - 10:30
Speaker: Mark Braverman
Affiliation:
Title: Studying Dynamical Systems
Abstract: Mark Braverman has studied at the Israel Institute of Technology (Technion), Yale University, and will be graduating in April 2008 at the University of Toronto. Biography of Speaker:

Studying dynamical systems is key to understanding a wide range of phenomena ranging from planets' movement to climate patterns to market dynamics. Various numerical tools have been developed to address specific questions about dynamical systems, such as predicting the weather or planning the trajectory of a satellite. However, the theory of computation behind these problems appears to be very difficult to develop. While we have vast knowledge about computability and complexity of discrete problems, little is known about computability of even the most natural problems arising from dynamical systems.

The focus of our study is dynamical systems that arise from iterating quadratic polynomials on the complex plane. They give rise to the amazing variety of fractals known as Julia sets, and are closely connected to the Mandelbrot set. Julia sets are perhaps the most drawn objects in Mathematics due to their fascinating fractal structure. The theory behind them is even more fascinating, and the dynamical systems generating them are in many ways archetypal.

In this talk we discuss what it means for a planar set to be computable. We then present a variety of recent results, both positive and negative, on the computability and complexity of Julia sets. In particular we show that while the vast majority of Julia sets are computable - many even in polynomial time, some are as hard to compute as the Halting Problem and will never be drawn. The work paves the way to understanding computational properties of more complicated dynamical systems.


2008/02/15 Faculty Candidate Talk Place: MC 437
Time: 9:30 - 10:30
Speaker: Mohit Singh
Affiliation: Carnegie Mellon University
Title: Iterative Methods in Combinatorial Optimization
Abstract: Linear programming has been a successful tool in combinatorial optimization to achieve polynomial time algorithms for problems in P and also to achieve good approximation algorithms for problems which are NP-hard. We demonstrate that iterative methods give a general framework to analyze linear programming formulations of combinatorial optimization problems. We show that iterative methods are well-suited for problems in P and lead to new proofs of integrality of linear programming formulations for various problems in P. This understanding provides us the basic groundwork to address various problems that are NP-hard and to achieve good approximation algorithms.

In this talk, we focus on degree bounded network design problems. The most well-studied problem in this class is the Minimum Bounded Degree Spanning Tree problem. We present a polynomial time algorithm that returns a spanning tree of optimal cost and the degree of any vertex is one more than its degree bound. This generalizes a result of Furer and Raghavachari to weighted graphs, and thus settles a 15-year-old conjecture of Goemans affirmatively. This is essentially the best possible result for this problem. For degree constrained versions of more general network design problems, we obtain first additive approximation algorithms using the iterative method. These results add to a rather small list of combinatorial optimization problems which have an additive approximation algorithm and show that iterative methods provide a unifying framework for solving large class of constrained network design problems. Biography of Speaker:

After having begun his graduate studies at the Indian Institute of Technology, Mohit Singh joined the Tepper School of Business at Carnegie Mellon University.


2008/02/08 CSE - Computational Science & Engineering Place: MC103
Time: 14:30 - 15:30
Speaker: Ronald Haynes
Affiliation: Department of Mathematics and Statistics, Acadia University
Title: Schwarz Waveform Moving Mesh Methods
Abstract: An efficient solution of many complex PDEs requires methods which are adaptive in both space and time. In this talk I will outline existing adaptive strategies and focus on Moving mesh (r- refinement) methods which provide a mechanism to concentrate the computational effort spatially. Traditionally these techniques were implemented in a (moving) method of lines context, relying of the efficacy of the initial value problem software to deal with the time integration. Time steps are either chosen globally for all mesh and solution components or globally within independent solution and mesh solves using a decoupled strategy. In this talk I will propose solving the physical PDE and mesh PDE in a Schwarz waveform relaxation framework. This allows the integration to proceed independently within subdomains of space and time. Numerical results for sequential Jacobi and Gauss Seidel and parallel Jacobi implementations will be provided. I will conclude with preliminary convergence results which obtain a contraction using a maximum principle argument.
2008/02/08 Math Place: Burnside 934
Time: 14:30 - 15:30
Speaker: Nick Harvey
Affiliation: MIT
Title: Computational Complexity of Matchings, Matroids, and Submodular Functions
Abstract: Matchings, matroids, and submodular functions are closely related objects that play a foundational role in several areas of combinatorics. We consider the computational complexity of several optimization problems involving these objects. The focus is on two specific results. - An algorithm for non-bipartite matching with running time O(n^w) on graphs with n vertices, where w < 2.38 is the matrix multiplication exponent. This is the fastest known running time for dense graphs. - A family of matroids of rank n/2 on a ground set of size n such that (log_2 3) n - o(n) oracle queries are necessary to solve the matroid intersection problem on this family. This is the first non-trivial progress on a question of Welsh from 1976. Our arguments are based on communication complexity and representation theory of the symmetric group.
2008/02/07 Faculty Candidate Talk Place: MC437
Time: 9:30 - 10:30
Speaker: Nicholas Harvey
Affiliation: Computer Science and Artificial Intelligence Laboratory - MIT
Title: Iteratively Constructing Preconditioners via the Conjugate Gradient Method
Abstract: Solving a linear system is one of the most fundamental computational problems. Unfortunately, the basic algorithm that most of us learn (Gaussian elimination) is often useless in practice due to slow running time or stability issues. Instead, it is more common to use iterative solvers, the simplest ones being steepest descent and conjugate gradient. The snag with iterative solvers is that their performance often depends on the condition number of the given system, so it is common to modify the system by applying a preconditioner matrix which reduces the condition number. This raises a key question: given a linear system, how can we find a good preconditioner?
In this work, we develop a variant of conjugate gradient method which uses geometric rescaling techniques to iteratively construct preconditioners. The general idea is very simple. We run the conjugate gradient method until it "gets stuck". The fact that it is stuck then implies a way to modify the preconditioner so that the conjugate gradient steps will be "less stuck" in the future.
This talk will be self-contained -- the audience only needs to know basic linear algebra, and how to interpret pictures of algorithms that are stuck.
Joint work with John Dunagan, Microsoft Research. Biography of Speaker:

Nicholas Harvey began his graduate studies at the University of Waterloo and then continued at the Massachusetts Institute of Technology where he will be graduating this year.


2008/02/07 CIM - Centre for Intelligent Machines Place: MC437
Time: 15:00 - 16:00
Speaker: Yiannis Rekleitis
Affiliation: Adjunct Professor, Centre for Intelligent Machines
Title: Autonomous Planetary Exploration using Irregular Triangular Mesh
Abstract:

In this talk, I am going to present work done at the Canadian Space Agency. In particular, our approach to planetary exploration together with the challenges we face is going to be discussed. Our objective is autonomous over-the-horizon navigation using a laser based vision sensor. With the term over-the-horizon, we mean locations beyond the sensor's reach.

Central to our efforts is the task of developing the autonomous capabilities of space robotic systems and in particular of planetary rovers. In order for a rover to be fully autonomous it has to be able to sense its environment, reason about the terrain it faces, plan a path, and navigate safely along the planned trajectory. In order to avoid the problems of harsh lighting conditions and to produce scientific valuable topographical maps in medium scale, we have selected the use of a laser based vision sensor. In this part of the talk I am going to present our successful autonomous experiments in over-the-horizon navigation in CSA's Mars-like terrain.

Biography of Speaker:


2008/02/06 CQIL - Cryptography and Quantum Information Place: MC320
Time: 10:00 - 11:00
Speaker: Simon Pierre Desrosiers
Affiliation: McGill University
Title: Quantum Entropic Cryptography
Abstract: We shall present a short history of security definition for encryption leading to definitions of generalised quantum entropic security and entropic indistinguishability. We shall also show one encryption scheme that achieves these definitions.
2008/02/04 Math Place: BURN 708
Time: 16:00 - 17:00
Speaker: Tibor Szabo
Affiliation: ETH Zurich
Area: Discrete math and optimization
Title: Thresholds for positional games
Abstract: The notion of positional games played an instrumental role in the development of the concept of derandomization in the theory of algorithms. In the talk we discuss two-player positional games played on the edge set of the complete graph. We investigate a mysterious phenomenon, the "random graph intuition", surrounding these games and settle a couple of long-standing open problems of the area.
2008/01/31 Vision, Graphics, and Robotics Place: MC437
Time: 15:00 - 16:00
Speaker: Jean-Philippe Tardif
Affiliation: GRASP Lab, School of Engineering and Applied Science, U. Penn.
Area: Computer Vision
Title: Omnidirectional vision: calibration and self-calibration
Abstract: The topic of this seminar relates to the problem of calibration and self-calibration of omnidirectional cameras, ie. that have a very large field of view. These include pin-hole, wide-angle and fish-eye cameras, as well as many catadioptric cameras possibly with a view angle larger than 180 degrees and also with a non-single viewpoint. Conventional camera models usually fail describing the geometry of such cameras. The traditional approach to this problem has been to develop specific camera models and calibration algorithms for each type of device. During our research, we developed a general camera model making it possible to represent all the above cameras, as well as algorithms for estimating the parameters of the model in controlled and non-controlled environments. Biography of Speaker:

Jean-Philippe Tardif is a post-doctoral fellow in the GRASP laboratory of University of Pennsylvania since October 2007. He recently received a Ph.D. in computer vision from Université de Montréal. His areas of research are structure from motion, SLAM, omnidirectional camera calibration and self-calibration, structured light reconstruction and place recognition. Over the years, he has collaborated with researchers from INRIA Rhône-Alpes and CNRS Clermont-Ferrand in France. He has also contributed to technological art projects in collaboration with artists of the SAT (Société des Arts Technologiques of Montréal). In particular, he is the co-inventor of a multiple projector system for which he holds a patent. This invention is the foundation for the LightTWIST immersive projection system.


2008/01/30 CQIL - Cryptography and Quantum Information Place: MC320
Time: 10:00 - 11:00
Speaker: Thomas Decker
Affiliation: McGill University
Title: Quantum algorithms for hidden polynomials
Abstract: We define a class of black box hidden polynomial problems which are a natural generalisation of abelian hidden subgroup problems where the subgroups and their cosets correspond to graphs of linear functions over a finite field F with d elements. In the more general class, the polynomials can be m-variate and of total degree n. For fixed m and n the problem is hard on a classical computer as the black box query complexity is polynomial in the field size d. We reduce the problems to quantum state identification problems so that the query complexity is independent of the field size d. We derive an efficient measurement for distinguishing the resulting quantum states provided that the characteristic of F is sufficiently large. Its success probability and implementation are closely related to a classical problem involving polynomial equations. (Joint work with Jan Draisma and Pawel Wocjan.)
2008/01/29 CSE - Computational Science & Engineering Place: MC103
Time: 14:30 - 15:30
Speaker: Laurence Loumes
Affiliation: Department of Mechancial Engineering, McGill University
Title: Multilayer Gelatin Impedance Pump: A nature inspired valveless pump with bio-medical applications
Abstract: This talk introduces the concept of multilayer impedance pump, a novel pumping mechanism inspired from the embryonic heart structure. The multilayer impedance pump (MIP) is a composite two-layer fluid-filled elastic tube featuring a thick gelatin-like internal layer similar in nature to the embryonic cardiac jelly, and that is used to amplify longitudinal elastic waves. Pumping is based on the impedance mismatch and elastic wave interactions. Results show that the two-layer configuration can be an efficient wave propagation combination, and that it allows the pump to produce significant flow for small excitations. The multilayer impedance pump is a complex system in which flow and structure exhibit a resonant behavior. At resonance, a constructive elastic wave interaction coupled with a most efficient energy transmission between the elastic walls and the fluid is responsible for the maximum exit flow and maximizes the pump efficiency. Using a MIP model excited in a similar fashion to the embryonic heart and the exact same multilayer tube with a peristaltic excitation, we are able to bring an additional proof on the impedance nature of the embryonic heart. To understand the role of this unique gel-like cardiac jelly layer in the embryonic heart, we perform a comparison between the exact same impedance pump with and without the additional gelatin layer. The results shed light on the dynamic role of the cardiac jelly in the embryonic heart and on nature^Òs optimized design. Finally, several bio-medical applications of multilayer impedance pumping are presented. A physiologically correct model of aorta is used to test the pump as an implantable cardiovascular assist device. Coffee and cookies are served before the seminar.
2008/01/28 Math Place: Burnside 1205
Time: 16:30 - 17:30
Speaker: David Wood
Affiliation: Universitat Politècnica de Catalunya
Area: Graph theory
Title: Graph minors and products
Abstract: A "clique minor" in a graph can be thought of as a set of connected subgraphs that are pairwise disjoint and pairwise adjacent. This talk is about clique minors in the Cartesian product of graphs. The main result is a rough structural characterisation theorem for Cartesian products with bounded clique minors (that is less rough than the general structure theorem of Robertson and Seymour). For example, it implies that if the product of two sufficiently large graphs has bounded clique minors then it is: (1) a planar grid (product of two paths) plus a vortex of bounded width in the outerface, (2) a cylindrical grid (product of a path and a cycle) plus a vortex of bounded width in each of the two `big' faces, or (3) a toroidal grid (product of two cycles). We also develop connections with pseudoachromatic colourings and connected dominating sets that imply near-tight bounds on maximum cardinality of a clique minor in grid graphs (products of paths) and Hamming graphs (products of cliques). Finally, Hadwiger's conjecture for Cartesian products will be discussed. Only basic graph theory will be assumed.
2008/01/23 CQIL - Cryptography and Quantum Information Place: MC320
Time: 10:00 - 11:00
Speaker: Patrick Hayden
Affiliation: McGill Computer Science
Area: Quantum information theory
Title: The maximal p-norm multiplicativity conjecture is false
Abstract: In a 1973 retrospective honouring the 25th anniversary of Shannon's breakthrough paper creating the field of information theory, John Pierce made the following provocative comment: "I think that I have never met a physicist who understood information theory. I wish that physicists would stop talking about reformulating information theory and would give us a general expression for the capacity of a channel with quantum effects taken into account rather than a number of special cases." More than thirty years later, Pierce's challenge has still not been fully met. In this talk, I'll begin by introducing the capacity problem, then indicate why it has proved harder than anyone could rightfully have anticipated. I'll then focus on a particular question known as the maximal p-norm multiplicativity conjecture that would have resolved the issue once and for all. In particular, I'll exhibit counterexamples demonstrating that the conjecture is false.
2008/01/23 CIM - Centre for Intelligent Machines Place: MD357
Time: 16:30 - 17:30
Speaker: Il Yong Kim
Affiliation: Department of Mechanical and Materials Engineering , Queen's University
Title: Computational Multidisciplinary Design Optimization
Abstract: Multidisciplinary Design Optimization (MDO) is a methodology for the design of complex engineering systems and subsystems that coherently exploits the synergism of mutually interacting phenomena. MDO accounts for interactions amongst several different disciplines. The goal is to develop engineering systems that have the best performance in terms of functionality, manufacturability, and overall life-cycle cost. This seminar will introduce the fundamental concepts of typical computational design optimization, multidisciplinary optimization, and multiobjective optimization. The principles, advantages, and disadvantages of most popular optimization methods will be briefly explained, and several practical case studies in automotive engineering and biomechanics will be presented. Biography of Speaker:

Il Yong Kim is an Assistant Professor in the Department of Mechanical and Materials Engineering at Queen’s University, Canada. His research interest is Multidisciplinary System Design Optimization with applications in automotive mechanical systems and bioengineering systems. He received his M.S. and Ph.D. degrees in mechanical engineering from the Korea Advanced Institute of Science and Technology (KAIST). He worked as an instructor and postdoctoral researcher in the Department of Aeronautics and Astronautics at the Massachusetts Institute of Technology, where he taught undergraduate and graduate design courses. He received a number of awards including Educational Excellence and Innovation Grant at MIT and a silver medal in the Samsung Electronics Paper Competition.


2008/01/21 Math Place: BURN 1205
Time: 16:30 - 17:30
Speaker: Omid Amini
Affiliation: Max Planck Institut fur Informatik
Area: Discrete math and optimization
Title: Mixing in oriented graphs
Abstract: I will give an account of the new notion of pseudo-randomness for orientations of graphs, that we have called mixing, and its consequences in the extremal theory of digraphs. Joint work with Florian Huc (INRIA Sophia-Antipolis) and Simon Griffiths (Cambridge University).
2008/01/18 Algorithms Place: MC320
Time: 16:00 - 17:00
Speaker: Shin-Ichi Tanigawa
Affiliation: Kyoto University
Area: Graph theory, computational geometry
Title: Fast enumeration algorithms for non-crossing geometric graphs
Abstract: A non-crossing geometric graph is an embedded graph on a given set of points in the plane with non-crossing straight line segments. In this talk we present a new technique for enumerating non-crossing geometric graphs for a given point set. By applying our idea to specific enumeration problems, we obtain faster algorithms for enumerating plane straight-line graphs, non-crossing spanning connected graphs, non-crossing spanning trees and non-crossing minimally rigid frameworks. Furthermore, the proposed idea is relatively simple, and can be potentially applied to the other various non-crossing geometric graph classes, whose enumeration algorithms have not been reported so far. Joint work with Naoki Katoh.
2008/01/17 Vision, Graphics, and Robotics Place: MC437
Time: 15:00 - 16:00
Speaker: Behzad Mansouri
Affiliation: McGill Vision Research, Dept. Ophthalmology, McGill University, Montreal
Area: Vision, Computer Games
Title: Computer Games; a New Gateway to the Treatment of Amblyopia (Lazy Eye)
Abstract: Amblyopia is the most common cause of monocular blindness in adults. It affects 3-5% of the population worldwide. Despite its high prevalence and significant consequences, there is no effective treatment. Currently, the only therapeutic option is to restrict the vision of the remaining good eye either by patching or using chemicals to dilate and therefore blur the vision in the good eye. Animal models suggest that the loss of binocular function in amblyopia is due to a loss of binocular cortical connections early in life. If true, restoration of binocular function in adulthood would be unlikely. Less attention has been paid to the influence of suppressive cortical interactions which appear to be an important part of the clinical picture in humans with amblyopia and for which treatment may be possible. We show that, under conditions where suppressive influences are minimal, global binocular combination is present for visual stimuli designed to activate the amblyopic eyes. This suggests that binocular connections are intact in amblyopia and that suppressive interactions underlie the binocular loss, offering hope for restoration of function. Our preliminary results using our novel stimulus presentation paradigm which directly addresses suppression in amblyopia, show promise as an effective treatment for amblyopia. This opens the way for developing a new approach to the treatment of amblyopia in adults and children using video game technologies. Biography of Speaker:

Dr. Mansouri obtained his Medical Diploma from TUMS (Tehran University of Medical Sciences) in 1998. He worked as a general practitioner and researcher for 2 years in North Iran, Gilan. He studied Neuroscience at McGill University and obtained a Ph.D. in 2005. He is currently a post-doctoral fellow at the McGill Vision Research Unit, working with Robert Hess.


2008/01/16 Faculty Candidate Talk Place: MC437
Time: 9:30 - 10:30
Speaker: Gad Kimmel
Affiliation: University of California, Berkeley
Area: Bioinformatics
Title: Computational Problems in Human Genetics
Abstract: The question how genetic variation and personal health are linked is one of the compelling puzzles facing scientists today. The ultimate goal is to exploit human variability to find genetic causes for multi-factorial diseases such as cancer and coronary heat disease. Recent technology improvement enables the typing of millions of single nucleotide polymorphisms (SNPs) in a large amount of individuals. Consequently, there is a great need for efficient and accurate computational methods for rigorous and powerful analysis of these data. In my talk I am going to concentrate on three computational problems, which are induced by this technology: study design, estimating local ancestries in admixed population, and accurate and fast evaluation of the significance with a correction for population stratification. Biography of Speaker:

Dr. Gad Kimmel is a Postdoctoral Associate at the International Computer Science Institute (ICSI) and the University of California at Berkeley. He has graduated, with distinction, at the Tel Aviv University.


2008/01/11 CSE - Computational Science & Engineering Place: MC103
Time: 14:30 - 15:30
Speaker: Pierre Gauthier
Affiliation: Department of Earth and Atmospheric Sciences, UQAM
Title: Mathematical problems Associated with Atmospheric Data Assimilation and Weather Prediction
Abstract: Over the last twenty years, significant changes have been introduced in operational data as- similation systems in support of numerical weather prediction. These changes aimed at making a better use of the large volumes of satellite data being received daily. As data assimilation is basically cast as a statistical estimation problem, particular attention need to be paid to the mod- eling and estimation of both the background-error and the observation error. These statistics are often reduced to the knowledge of the bias and error covariances, which can only be estimated by comparing a given weather forecast to the available observations. This presentation will introduce some of the mathematical challenges that need to be addressed to further improve the assimilation systems. For instance, as the development of meteorological systems depends on existing atmospheric instabilities, small differences in the initial conditions, the analysis, can lead to important changes in the forecast. These instabilities can be characterized by computing the singular vectors associated with the tangent linear and adjoint models. This information has been used in several observation campaigns to deploy targeted observations in areas where an accurate analysis is required to correctly forecast the development of weather systems. This relates closely to the use of flow dependent error statistics with either, approximate forms of the Kalman filter or implicitly as is done in current 4D variational data assimilation systems. Finally, the variational form of the assimilation problem will be presented altogether with its so-called dual form and the convergence properties of the two problems will be compared (El Akkraoui et al., 2008).