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

Seminar Home
Fall 2013 Schedule
Winter 2014 Schedule
Summer 2014 Schedule

( Fall 2012 )
Category Seminar Info
2012/12/06 CQIL - Cryptography and Quantum Information Place: McConnell 320
Time: 10:00 - 11:00
Speaker: Winton Brown
Affiliation: University of Sherbrooke
Title: Scrambling speed of random quantum circuits
Abstract: Random transformations are typically good at "scrambling" information. Specifically, in the quantum setting, scrambling refers to the process of mapping most initial pure product states under a unitary transformation to states which are macroscopically entangled, in the sense of being close to completely mixed on all or most subsystems containing a fraction fn of all n particles for some constant f. While the term scrambling is used in the context of the black hole information paradox, scrambling is related to problems involving decoupling in general, and to the question of how large isolated many-body systems reach local thermal equilibrium under their own unitary dynamics. I will discuss the speed at which various notions of scrambling/decoupling occur in a simplified but natural model of random two-particle interactions: random quantum circuits. For a circuit representing the dynamics generated by a local Hamiltonian, the depth of the circuit corresponds to time. We resolve a conjecture raised in the context of the black hole information paradox with respect to the depth at which a typical quantum circuit generates an entanglement assisted encoding against the erasure channel. In addition, we prove that typical quantum circuits of poly(log n) depth satisfy a stronger notion of scrambling and can be used to encode r1 n qubits into n qubits so that up to r2 n errors can be corrected, for finite rates r1 and r2 > 0.
2012/11/28 Graduate Seminar Series Place: MC103
Time: 12 - 12:30
Speaker: Bundit Laekhanukit
Affiliation: PhD Student, McGill
Area: Discrete Math
Title: Approximation Algorithms and Hardness of Approximations
Abstract: Optimization problems are problems that naturally arise in many computational tasks. For example, consider a situation in which we want to route a packet between two nodes in a network; then this problem can be phrased as the shortest path problem, which is a well-studied optimization problem. Unfortunately, while we can solve the shortest path problem in polynomial time, many other optimization problems are NP-hard, which means that we could not expect a polynomial-time algorithm that could solve the problems optimally unless P = NP. Hence, we turn to algorithms that find approximate solutions in (quasi) polynomial-time, giving birth to the area of approximation algorithms. In this talk, we will discuss how to design approximation algorithms for NP-hard problems, and we will discuss that some problems have high approximation resistance, i.e., it is NP-hard even to find a good approximate solution.
2012/11/28 Graduate Seminar Series Place: MC103
Time: 12:00 - 1:00
Speaker: Arash Nourian
Affiliation: President of CS Graduate Student Society(CSGS)
Title: General Assembly of CS Graduate Student Society
Abstract: The General Assembly is a forum that allows any member to bring their concerns, questions, issues, motions or amendments to the highest governing body of the CGGS. Active participation is important and critical to the future of CSGS as you can talk about your concerns and to work on long-term campaigns and plans to improve the quality of graduate studeies within the department. In this GA, the new amendments to the constitution are put to vote. The constitution requires further amendments which will be designed by the new governing body. Members will vote on them in the next general assembly. We will have elections for all the executive positions and If you are interested in running, all the information about the responsibilities of the positions can be found in the attached constitution. The open positions are: President Chair VP finance and operations VP Social VP Academic VP communications Please send me your nominations no later than Tuesday November 27th at 11:30AM. Serving your society is a great opportunity, especially at a time when CSGS is undergoing such major changes. The individuals who are elected into these important positions will work to improve the quality of social life as well as addressing the members' concerns with in the department. Food and drinks will also be provided.
2012/11/20 Graduate Seminar Series Place: MC103
Time: 12 - 12:30
Speaker: Xing Shi Cai
Affiliation: Master's student, McGill
Title: A probabilistic analysis of Kademlia networks
Abstract: Nowadays Kademlia is one of the most widely used dhts (Distributed Hash Table) in P2P (peer-to-peer) networks. This work studies one essential question about Kademlia overlay networks from a mathematical perspective: how long does it take to locate a node? To answer it, we introduce a random graph K to model a Kademlia overlay and study how long it takes to locate a given vertex in K by using Kademlia’s routing algorithm.
2012/11/15 General Place: MC103
Time: 9:30 - 11:00
Speaker: Andrew Richards
Affiliation: Codeplay
Area: Compilers, Parallelism
Title: The Unique Challenge of Producing Compilers for GPUs
Abstract: The main engine of growth in computing power right now is the GPU, not the CPU. This talk will explain why. To enable all this new processing power to be used in software, compilers need to be written which can target GPUs. But, unlike CPUs, GPUs have whole new processing architectures released every few years, and rely extensively on graphics features and parallelism. This creates unique new challenges for compiler developers, which this talk will discuss. Codeplay targets consumer electronics, so the talk will be specifically about the real-world commercial use of GPUs and how to deliver those results to hundreds of millions of customers worldwide. Biography of Speaker:

Andrew Richards is the CEO and founder of Codeplay (a GPU compiler developer for consumer electronics companies), as well as chair of the OpenCL-HLM group which is defining a new C++ higher-level GPGPU programming model. Daan Nijs is a GPU compiler developer at Codeplay

2012/11/14 Graduate Seminar Series Place: MC103
Time: 12 - 12:30
Speaker: Olivier Rémillard
Affiliation: Master's student, McGill
Area: computer animation
Title: Embedded Thin Shell
Abstract: Biography of Speaker:

We present a new technique for simulating high resolution surface deformations of soft objects that have a harder skin. We combine a high resolution thin shell with a coarse finite element mesh, and define a special coupling constraint that allows the formation and shape of wrinkles to be determined solely by the shell and interior deformation parameters. This leads to models that approximate the behaviour of fine resolution simulations without the computational expense of using a large number of elements to simulate deformations under the surface. Quadratic shape functions let us use very coarse finite element resolutions to model the overall global deformations efficiently while avoiding visual discretization artifacts that linear functions would produce on the embedded mesh. We validate our model with high resolution simulations and show examples of our method in the generation of wrinkles for facial and character animation, as well as for soft objects such as furniture.

2012/11/13 CQIL - Cryptography and Quantum Information Place: McConnell 320
Time: 14:30 - 15:30
Speaker: Nicolas Menicucci
Affiliation: University of Sydney
Area: Quantum information
Title: Optical continuous-variable cluster states
Abstract: I will describe the theoretical underpinnings of one-way quantum computation using continuous-variable systems, as well as the pros and cons of several different methods of experimental implementation using lasers. Issues related to error correction and fault tolerance -- many of which remain open problems -- will also be discussed.
2012/11/05 Graduate Seminar Series Place: MC103
Time: 12 - 12:30
Speaker: Ben Kybartas
Affiliation: Master's student
Area: computer games
Title: Procedural Narrative Generation in Video Games
Abstract: Using procedural narrative generation in video games provides a flexible way to extend gameplay and provide more depth to the game world at low cost to the developers. Current examples of narrative generation in commercial games, however, tend to be simplistic, resulting in repetitive and uninteresting stories. In this talk, we will present the challenges and benefits of narrative generation. Our system, called ReGEN, is developed for narrative generation using a context-aware graph rewriting framework. ReGEN uses a graph representation of the game world to create narratives which reflect and modify the current world state. Using a novel set of metrics to evaluate narrative quality, the approach is validated by comparing the generated narratives to other procedurally generated stories, as well as to authored narratives from commercially successful and critically praised games. The results show that our generated narratives compare favourably to authored narratives. ReGEN's metrics provide a new approach to narrative analysis, and the system provides a unique and practical approach to story generation.
2012/10/25 Graduate Seminar Series Place: MC103
Time: 12 - 12:30
Speaker: Anil Ada
Affiliation: PhD student, McGill
Area: theoretical computer science
Title: Communication Complexity
Abstract: What are the limitations to what computers can learn? Do certain mathematical theorems have have short proofs? Can quantum mechanics be exploited to speed up computation? Is every problem whose solution is efficiently verifiable also efficiently solvable (i.e. is P = NP)? At first these may seem like unrelated questions, but at a high level, they are all concerned with understanding which tasks are complex and which tasks are easy. Although the underlying model and the resource of interest can be different in different contexts, there seems to be a unifying theme captured by the concept of "communication complexity". In many seemingly unrelated settings, efficient solutions to problems can be viewed as efficiently solving certain communication tasks. In other words, many hard tasks have an implicit communication bottleneck, and one can prove the hardness of these tasks by studying them in the context of communication complexity.

In this talk we will: 1) formally define the basic communication complexity model, 2) give some concrete examples to demonstrate how it relates to various branches of theoretical computer science, and 3) argue that these connections are extremely fruitful.

2012/10/18 CQIL - Cryptography and Quantum Information Place: McConnell 320
Time: 16:00 - 17:00
Speaker: Grant Salton
Affiliation: McGill University
Title: Measuring distance by harvesting entanglement
Abstract: I will briefly introduce key topics in the field of relativistic quantum information, focussing mainly on the process by which entanglement can be 'harvested' from a quantum field. I will then show that entanglement harvested from a quantum field by interaction with local detectors undergoing anti-parallel acceleration can be used to measure the distance of closest approach between the two detectors. Information about the separation is stored nonlocally in the phase of the joint state of the detectors after the interaction; a single detector alone contains none. Although each detector alone sees the same thermal spectrum (due to Unruh radiation), the joint state between them may be entangled. In the vicinity of a critical distance of closest approach between the detectors, the phase of the entangled state depends sensitively on the distance. We will contrast this with the case of parallel acceleration, in which no such critical distance exists, and we will discuss the connection of this case with entanglement harvested from an expanding universe.
2012/10/10 Graduate Seminar Series Place: MC103
Time: 12 - 12:30
Speaker: Sheldon Andrews
Affiliation: PhD student, SOCS McGill
Area: computer animation
Title: Learning Control Policies for Grasping Animation
Abstract: Synthesizing motions for human grasping tasks remains an open problem in computer animation. In this presentation, I begin with a short overview on character animation using a multibody dynamical simulation. I emphasize aspects which make grasping particularly interesting (and difficult). I then present our method for performing one-handed manipulation of objects. Our approach uses offline simulations to learn control policies for a multiphase controller framework. Parameters for individual controllers are found by minimizing phase appropriate objective functions. For this purpose, a derivative-free numerical optimization method is used. The generated motions are physically plausible and the resulting policy is general enough to be used in real time. I will show some videos of our results and discuss some of the techniques used to improve performance.
2012/10/04 CQIL - Cryptography and Quantum Information Place: McConnell 320
Time: 16:00 - 17:00
Speaker: Alex May
Affiliation: McGill University
Title: Summoning Information in Spacetime, or Where and When Can a Qubit Be?
Abstract: If information is localized near a point, it should be possible in principle to quickly exhibit that information nearby. Building on this notion of localization, we characterize the propagation of quantum information through spacetime by giving a simple description of all the situations in which that information can be summoned to a set of spacetime points. The answer depends only the various causal relationships between the points at which the challenges occur and the points at which the information must be produced. In general, whenever summoning is possible, it can be achieved using a combination of quantum error correction and teleportation.
2012/10/02 Graduate Seminar Series Place: MC103
Time: 12 - 12:30
Speaker: Annie Ying
Affiliation: McGill, SOCS, PhD student
Area: Software Evolution
Title: Code Fragment Summarization through Expertise Modeling
Abstract: When a programmer uses general search engines to find code examples, the information accompanying a returned link does not always contain adequate cues for determining whether the link is worth-while to pursue. To mitigate this issue, in this talk, I will introduce the problem of code fragment summarization for extracting succinct cues on Web pages containing code fragments. We developed a machine learning approach using expertise-related, syntactic, and query-related features, guided by an oracle we collected: 73 summaries and 1000 human judgements of whether a code line is in a summary. Our results show that syntactic and query-related features can form summaries that approximate summaries in the oracle, with a precision of 0.55. The novel use of light-weight expertise-related features shows promise, increasing the precision to 0.58. A qualitative analysis shows that even the summaries with lower precision can be useful.

This is joint work with Prof. Martin Robillard.

2012/09/26 General Place: MC103
Time: 11:30 - 12:30
Speaker: Raul Silvera
Affiliation: IBM Toronto Lab
Area: systems, development, alumni experience
Title: State of compilation technology and trends and challenges for the industry
Abstract: Raul will discuss the current state of compilation technology at IBM, its value for the industry and the world at large, and some of the current challenges and opportunities. He will also have a general discussion of life as a software developer at a large software corporation such at IBM, both from work/life balance and career development perspectives. Biography of Speaker:

Raul Silvera is a Senior Technical Staff Member (STSM) at the IBM Canada Lab in Toronto. He's a graduate of the M.Sc. program at the School of Computer Science of McGill University. He joined IBM in 1997 and has been focused on development of compilation technology for the IBM Power and System Z platforms, including code analysis, optimization, parallelization, and code generation for C, C++, Fortran and other static languages. He has participated on many industry standard committees, including C++, OpenMP and Fortran, has led a large team of software professionals at IBM and as part of IBM has had the opportunity to make an impact on several of the largest computing sites in the world.

2012/09/20 Graduate Seminar Series Place: MC103
Time: 15 - 15:30
Speaker: Yam Chhetri
Affiliation: Former Master's student, SOCS McGill
Area: software evolution and natural language processing
Title: Classifying and recommending reference API documentation
Abstract: Reference documentation is an important source of information on API usage. However, information useful to programmers can be buried in irrelevant or boiler-plate text, making it difficult to discover. In this talk, I will explain a technique we used to detect and recommend fragments of API documentation potentially important to a programmer who has already decided to use a certain API element. We categorize text fragments in API documentation based on whether they contain information that is indispensable, valuable, or neither. From the fragments that contain knowledge worthy of recommendation, we extract word patterns, and use these patterns to automatically find new fragments that contain similar knowledge in unseen documentation. In an evaluation study with randomly-sampled method definitions from ten open source systems, we found that with a training set of about 1 000 manually-classified sentences, we could issue recommendations with about, on average, 90% precision and 69% recall.
2012/09/20 CQIL - Cryptography and Quantum Information Place: McConnell 320
Time: 16:00 - 17:00
Speaker: Olivier Landon-Cardinal
Affiliation: University of Sherbrooke
Title: Local topological order inhibits thermal stability
Abstract: We put severe constraints on the existence of a self-correcting quantum memory made of a two-dimensional (2D) array of particles. Such a memory would passively protect the encoded information thanks to its dynamics at low temperature. To be robust to perturbation, candidates for such devices encode information in topological degrees of freedom, which are impervious to local errors on a short timescale. However, we show that, for any topologically ordered 2D local commuting projector code, thermal excitations can accumulate and corrupt the encoded information. We thus prove a no-go theorem, extending the known results to non-stabilizer codes.
2012/09/19 Vision, Graphics, and Robotics Place: TBA
Time: 16:00 - 17:00
Speaker: Victor Zordan
Affiliation: University of California Riverside
Area: Computer Animation
Title: Coordinated, responsive physics-based simulation control for humanoids
Abstract: Physical modeling for simulated humanoids continues to grow both as a research topic and in its usage for commercial applications, especially computer animation. This talk will cover a set of techniques for controlling and combining physics based simulation with human motion capture data. The ultimate goal of these techniques is to create coordinated, responsive controllers that remain natural looking under a variety of unexpected conditions. Two themes that will be discussed include the benefit of whole-body momentum in controlling behavior as well as the employment of real-time performance with physics for interactive control. Biography of Speaker:

Dr. Victor Zordan is an associate professor at University of California Riverside currently at Berkeley on sabbatical working in the Visual Computing Laboratory. His research interests center around game and special effects animation for characters with an emphasis on realism and control-ability. Victor has developed a host of techniques that merge motion capture and dynamic simulation to create flexible and responsive behavior for humanoids. His research interests span the field of computer animation with a strong bias in physics-based modeling and interfaces.

2012/09/12 CQIL - Cryptography and Quantum Information Place: MC103
Time: 13:30 - 14:30
Speaker: Tobias Fritz
Affiliation: Perimeter Institute
Area: information theory and mathematics
Title: Entropy as a functor
Abstract: Shannon entropy is of one the most useful concepts in applied mathematics. I will explain how it can be regarded as a functor on the category of finite probability spaces, and how this can be turned into a characterization of Shannon entropy. This is joint work with John Baez and Tom Leinster. Biography of Speaker:

Tobias Fritz received his doctorate from the Max Planck Institute of Mathematics, Bonn, Germany, has been a post-doctoral fellow at the Institute of Photonic Sciences, Barcelona, Spain, and has now joined the Perimeter Institute for Theoretical Physics in Waterloo, Canada.

2012/08/16 Graduate Seminar Series Place: MC103
Time: 12 - 12:30
Speaker: Rahul Garg
Affiliation: PhD Student, SABLE lab, McGill
Area: Programming Languages and Scientific Computing
Title: Portable Matrix Operation Library for GPUs
Abstract: Does your work involve matrix operations with large dense matrices? Not satisfied with speed you are getting on CPUs? Then you may be aware that modern GPUs provide considerably better performance on many types of matrix computations than most CPUs. However, so far you had to choose vendor-specific APIs (eg: Nvidia CUBLAS only works on Nvidia) making your code non-portable. I present a high-performance portable BLAS library that runs on many GPUs including AMD, Nvidia and Intel GPUs. I will present initial performance results, and discuss future plans.