Date( Fall 2007 ) Category Seminar Info 2007/12/05 General Place: MC320 Time: 15:00 - 16:00 Speaker: Renato De Mori Affiliation: Université d’Avignon (France) Title: The European Project LUNA on Spoken Language Understanding Abstract: The LUNA project addresses the problem of real-time understanding of spontaneous speech in telephone applications. In today’s commercial applications based on speech recognition, the quality of the human-to-computer interaction is still far from being enjoyable and effective. To improve the usefulness and acceptability of automatic dialogue systems, a solution is to raise the level of intelligence of automatic systems up to Spoken Language Understanding (SLU). A set of challenging scientific problems are addressed by SLU, namely language and semantic modeling for speech understanding; strategies for obtaining semantic interpretations from spoken messages; new semantic confidence indicators; new methods for knowledge updating using active learning; robustness; portability across domains and languages. Three levels are considered for the SLU interpretation process: generation of semantic concepts for SLU, by means of translation from a word lattice to a conceptual constituents lattice; generation and validation of semantic structure hypotheses, through semantic composition, combination of confidence indicators and active learning; and context-sensitive semantic validation. Research results will be validated on different application scenarios, targeted to dialogue-based telephone services of different complexity (e.g. call routing with utterance classification, dialogue systems with complex semantic domains). A specific corpus of service-related data is collected and annotated. A toolkit for multilingual dialogue services will be developed, and selected modules integrated with existing voice platforms and used to develop and field test sample applications in four languages (French, German, Italian and Polish). ALL ARE WELCOME 2007/11/30 Software Engineering Place: McConnell 103 Time: 12:30 - 13:30 Speaker: Martin Robillard Affiliation: McGill University Title: Digging for Gold in Program Artifacts Abstract: Every year, dozens of new program mining techniques are proposed. Is all the information we mine equally valuable? In this talk, we will explore that question by reflecting on a number of recent program mining techniques. 2007/11/30 Software Engineering Place: McConnell 103 Time: 15:30 - 16:30 Speaker: Martin Robillard Affiliation: McGill University Title: Programming Environments: Success and Challenges Abstract: A presentation of some of the key ideas and problems that have influenced the development of programming environments, from Smalltalk'76 to Eclipse. 2007/11/26 Math Place: Burnside 1205 Time: 16:30 - 17:30 Speaker: Anne Broadbent Affiliation: University of Montreal Title: Bipartite Games and Winning Strategies Abstract: We study bipartite games that arise in the context of nonlocality with the help of graph theory. Our main results are that deciding whether a no-communication classical winning strategy exists for certain games (called forbidden-edge and covering games) is NP-complete, while the problem of deciding if these games admit a non-signalling winning strategy is in P. We also show that every pseudo-telepathy game yields both a proof of the Bell-Kochen-Specker theorem and an instance of a two-prover interactive proof that is classically sound, but that becomes unsound when provers use shared entanglement. Biography of Speaker: Anne Broadbent is a Ph.D. candidate in the Département d'informatique et de recherche opérationnelle at the University of Montreal. 2007/11/21 Math Place: MC103 Time: 16:00 - 17:00 Speaker: Paul Seymour Affiliation: Princeton University Area: Graph Theory Title: The densest graphs with no $K_{2,t}$ minor Abstract: For a graph $H$ and an integer $n$, let $e(H,n)$ be the maximum number of edges of an $n$-vertex simple graph with no minor isomorphic to $H$. For all choices of $H$, it is known that $e(H,n)$ is at most linear in $n$; but finding it exactly is much more difficult. For instance, it is easy to see that for $n\ge t-2$, $e(K_t,n)\ge (t-2)n -(t-1)(t-2)/2$. Mader showed that equality holds for $t\le 7$, but {\it not} for $t=8$ and larger, a distressing phenomenon for those who believe in Hadwiger's conjecture. For other graphs $H$, the function $e(H,n)$ has not been studied so exhaustively. The answer is easy when $H = K_{1,t}$, but seems to be open when $H$ = K_{2,t}$. The natural conjecture is that$e(K_{2,t},n) \le (n-1)(t+1)/2$, for then equality would hold at least whenever$t$divides$n-1$. In joint work with Maria Chudnovsky and Bruce Reed, we have proved this for$t$sufficiently large ($t\ge 100\$ would be plenty). We sketch the proof and related topics. 2007/11/06 CQIL - Cryptography and Quantum Information Place: MC320 Time: 11:30 - 12:30 Speaker: Kamil Bradler Affiliation: McGill University Title: Quantum Information with a Dash of Relativity Abstract: In current quantum information there is an unspoken message that (1) all the participants are inertial and (2) in a given logical qubit basis we don't need to be particularly worried about the spacetime transformation properties of the quantum information carriers forming the basis. These assumptions are unjustified if the spacetime structure of the Universe is taken into account. In other words, there are some situations where we have to exactly know how the states relativistically transform and it is necessary to include the whole bunch of new effects the theory of relativity brings. We will demonstrate two such effects on some quantum information protocols. From the Special theory of relativity point of view it will be the role of the Wigner phase and the General Theory of Relativity will be represented by the Unruh effect. Biography of Speaker: Kamil Bradler is a postdoctoral fellow with the Cryptography and Quantum Information group at McGill. 2007/10/19 CQIL - Cryptography and Quantum Information Place: MC320 Time: 11:00 - 12:00 Speaker: Nilanjana Datta Affiliation: University of Cambridge Area: Quantum information theory Title: Entanglement manipulation of arbitrary states Abstract: Entanglement plays a fundamental role in quantum information processing and is regarded as a valuable, fungible resource, The practical ability to transform (or manipulate) entanglement from one form to another is useful for many applications. Usually one considers entanglement manipulation of states which are multiple copies of a given bipartite entangled state and requires that the fidelity of the transformation to (or from) multiple copies of a maximally entangled state approaches unity asymptotically in the number of copies of the original state. The optimal rates of these protocols yield two asymptotic measures of entanglement, namely, entanglement cost and distillable entanglement. It is not always justified, however, to assume that the entanglement resource available, consists of states which are multiple copies, i.e., tensor products, of a given entangled state. More generally, an entanglement resource is characterized by an arbitrary sequence of bipartite states which are not necessarily of the tensor product form. In this seminar, we address the issue of entanglement manipulation for such general resources and obtain expressions for the entanglement cost and distillable entanglement. Biography of Speaker: Nilanjana Datta is an affiliated lecturer of the Faculty of Mathematics at Cambridge University and a fellow of Pembroke College. Since 2002, her research has primarily been in the field of Quantum Information Theory. Some problems she has worked on include data compression for sources with memory, perfect transfer of quantum states and entanglement over spin networks, proof of the additivity conjectures of the Holevo capacity and the minimum output entropy for various models of quantum channels, complementary channels, capacities of quantum channels with memory, entanglement manipulation, and the evaluation of the optimal rates of various quantum information protocols using the quantum information spectrum method. 2007/10/16 Software Engineering Place: MC103 Time: 10:30 - 11:30 Speaker: Barbara Ryder Affiliation: Rutgers University Title: Blended Program Analysis Abstract: A new analysis paradigm, blended program analysis, enables practical, effective analysis of large framework-intensive Java applications for performance diagnosis. Blended analysis combines a dynamic representation of program calling structure with a static analysis applied to a region of that calling structure with observed performance problems. The initial instantiation of the paradigm addresses the issue of performance bottlenecks stemming from overuse of temporary objects, common in these applications. A blended escape analysis, which approximates object effective lifetimes, has been designed and implemented. Experiments demonstrating its utility in explaining the usage of newly created objects in a program region have yielded promising results (ISSTA07). A case study on the Trade benchmark shows how blended escape analysis helped to locate the single call path responsible for a performance problem involving objects created at 9 distinct sites and as far away as 6 levels of call, in a region which calls 223 distinct methods with a maximum call depth of 20. This talk will informally discuss the paradigm, the ISSTA07 paper results, and future plans. 2007/09/26 Algorithms Place: McConnell 320 Time: 16:00 - 17:00 Speaker: Rahul Savani Affiliation: University of Warwick Title: A simple P-matrix linear complementarity problem for discounted games Abstract: We consider zerosum discounted games, which are played by two players on a finite directed graph with rewards on vertices. The players' strategies together determine an infinite path in the game graph. One player tries to maximize, the other minimize the discounted sum of the rewards encountered on the path. These games provide one of the few natural problems - Is the value of a game greater than k? - that are in NP interesct coNP, but for which no polynomial-time algorithms are known. One of the main algorithms for solving these games is "strategy improvement", however its worst case complexity is not known to be superpolynomial. In this talk we present a simple reduction from discounted games to the P-matrix linear complementarity problem (PLCP), and discuss the application of known algorithms for PLCPs to discounted games. In particular, we recover a variant of strategy improvement. We also discuss the underlying combinatorial framework, which is given by unique sink orientations of cubes. Joint work with Marcin Jurdzinski. 2007/09/24 General Place: BIRKS 111 Time: 14:00 - 15:00 Speaker: Kiran Mehta Affiliation: Director, R&D - Data Services, Informatica Corporation Title: Enterprise Data Integration (+Wii giveaway) Abstract: Information is the lifeblood of today's enterprise. Data is used for both the day to day operations and strategic decision making. For the proper functioning of various applications, individuals and departments within an enterprise timely availability, completeness and correctness of data is very crucial. However, as enterprises become more global, merge with or acquire other companies, and work within a large ecosystem of partners and vendors, business data gets more and more fragmented. For corporations to be able to derive greater business value from its information assets, it is critical that data is integrated from multiple independent and heterogeneous data sources and delivered to the application in a timely manner. This talk will provide an overview of data integration technology, architectural approaches to solving it and the myriad of complex open problems in this space. Biography of Speaker: Kiran heads the Data Services group at Informatica. Prior to joining Informatica in 2006, Kiran Mehta held various technical and management positions at IBM Research and RedBrick Systems. Informatica Corporation delivers data integration software that is open, platform-neutral, reduces costs, speeds time to results, and scales to handle data integration projects of any size or complexity. 2007/09/20 Vision, Graphics, and Robotics Place: ENGMC 437 (CIM seminar room) Time: 15:00 - 16:00 Speaker: Marc-Antoine Drouin Affiliation: Visual Information Technology Group, National Research Council Canada (NRC) Area: Computer Vision Title: Occlusion handling in multi-baseline stereo Abstract: We present an overview of some recent advances in multiple-baseline stereo. Three multi-baseline matching algorithms are introduced. The first one detects occlusions in the depth map obtained from regular efficient stereo matching algorithms. Occlusions are detected as inconsistencies of the depth map by computing the visibility of the map as it is reprojected into each camera. The matching cost function is modified according to the detected occlusions by removing the offending cameras from the computation of the matching cost. The algorithm gradually modifies the matching cost function according to the history of inconsistencies in the depth map, until convergence. The second algorithm is a hybrid between fast heuristic occlusion overcoming algorithms that precompute an approximate visibility and slower methods that use correct visibility handling. Our approach is based on iterative dynamic programming and computes simultaneously disparity and camera visibility. Interestingly, dynamic programming makes it possible to compute exactly part of the visibility information. The remainder is obtained through heuristics. Finally, we also propose an algorithm that improves the localization of disparity discontinuities of disparity maps obtained by stereo matchers. Rather than associating a disparity label to every pixel of a disparity map, it associates a position to every disparity discontinuity. This formulation allows us to find an approximate solution to a 2D labeling problem with robust smoothing term by minimizing multiple 1D problems, thus making possible the use of dynamic programming. The validity of the proposed our algorithms is established using real imagery with ground truth and they compare favorably with other state-of-the-art algorithms. 2007/08/31 Vision, Graphics, and Robotics Place: MC437 Time: 11:00 - 12:00 Speaker: Marc Pollefeys Affiliation: ETH Zurich and UNC Chapel Hill Area: Computer Vision Title: Towards capturing dynamic 3D events from video Abstract: Images and videos form a rich source of information about the visual world. The extraction of 3D information from images is an important research problem in computer vision and graphics. The ubiquitous presence of cameras and the tremendous advances of processing and communication technologies yields important opportunities and challenges in those areas. This talk focuses on approaches to obtain 3D reconstruction of dynamic scenes. We present two approaches. The first approach uses Bayesian inference to recover dynamic shapes from silhouettes seen from multiple viewpoints, even in the presence of partial occlusion. Our approach not only recovers the dynamic shape, but over time is also able to infer the shape of the occluders present in the scene. Next we present our approach to analyze and recover articulated motion with non-rigid parts, e.g. the human body motion with non-rigid facial motion, from a single viewpoint under affine projection from feature trajectories. We model the motion using a set of intersecting linear subspaces. Based on this model, we can analyze and recover the articulated motion using subspace methods. Our framework consists of motion segmentation, kinematic chain building, and shape recovery. We test our approach through experiments and demonstrate its potential to recover articulated structure with non-rigid parts via a single-view camera without prior knowledge of its kinematic structure. Biography of Speaker: Marc Pollefeys is a full professor in the Dept. of Computer Science at ETH Zürich since 2007. He currently also remains associated with the Dept. of Computer Science of the University of North Carolina at Chapel Hill where he started as an assistant professor in 2002 and became an associate professor in 2005. Before he was a postdoctoral researcher at the Katholieke Universiteit Leuven in Belgium, where he also received his M.S. and Ph.D. degrees in 1994 and 1999, respectively. His main area of research is computer vision. One of his main research goals is to develop flexible approaches to capture visual representations of real world objects, scenes and events. Dr. Pollefeys has received several prizes for his research, including a Marr prize, an NSF CAREER award and a Packard Fellowship. He is the author or co-author of more than 90 peer-reviewed or invited papers. He was co-chair of the Third Symposium on 3D Data Processing, Visualization and Transmission and has organized workshops and courses at major vision and graphics conferences and has served on the program committees of many conferences. He is a regular reviewer for most of the major vision, graphics and photogrammetry journals. Prof. Pollefeys is on the Editorial Board of the IEEE Transactions on Pattern Analysis and Machine Intelligence, the International Journal of Computer Vision and Foundations and Trends in Computer Graphics and Computer Vision.