- Monday, 10 March 2014, 10:30AM -- DC 1304
- Seminar -- Computer Science
- Speaker: Reza Shokri, Post-doc researcher, Institute of Information Security, Dept. Comp. Sci., ETH Zurich
Title: "Computational Privacy: Two Fundamental Problems"
Abstract: New services are being introduced and new businesses are flourishing by mining the rich flow of individuals' information over the Internet. This success, however, comes at a price of users' privacy. Businesses might misuse user data, and governments can massively track individuals. My research focuses on designing privacy preserving schemes for emerging technologies. In my talk, I will present two fundamental challenges in computational privacy: quantification of users' privacy, and its protection using obfuscation mechanisms. I will present a metric and an analytical framework, based on statistical inference, to consistently quantify privacy across different systems. I will then introduce a new theoretical methodology to design privacy-protection obfuscation mechanisms that optimally balance privacy versus utility, and are provably robust against any attack. I will show examples of these approaches in the context of location-based services along with technical methods for quantifying and protecting location privacy.
Reza Shokri is currently a post-doctoral researcher in the Institute of Information Security, Department of Computer Science, ETH Zurich. Prior to this, he was a research assistant in the School of Computer and Communication Sciences at EPFL, where he received his PhD in March 2013. His research focuses on quantitative analysis of privacy and on designing privacy-preserving schemes for various platforms, including location-based services, recommender systems, web, and genomic. His work on quantifying location privacy was recognized as the runner-up for the annual award for Outstanding Research in Privacy Enhancing Technologies (PET Award) 2012. For more information please visit http://www.shokri.org.
- Monday, 10 March 2014, 2:30PM -- QNC 0101
- Colloquium -- Institute for Quantum Computing
- Speaker: Prof. Enrique Solano, University of the Basque Country, Bilbao, Spain
Title: "Quantum simulations as our quantum theatre"
Abstract: I will introduce the field of quantum simulations from a wide
scientific perspective. Then, I will discuss the relevance of quantum
simulations for reproducing different aspects of quantum physics:
nonrelativistic and relativistic quantum dynamics, physical and unphysical
quantum operations, as well as strong and ultrastrong light-matter
interactions. Finally, I will give examples in the context of trapped-ion
and circuit QED technologies.
- Tuesday, 11 March 2014, 11:00AM -- DC 1304
- Colloquium -- Computational Mathematics
- Speaker: Kilian Q. Weinberger, Assistant Professor in Computer Science & Engineering, Washington University
Title: "Learning with Marginalized Corruption"
Remarks: Refreshments will be available
If infinite amounts of labeled data are provided, many machine learning algorithms become perfect. With finite amounts of data, regularization or priors have to be used to introduce bias into a classifier. We propose a third option: learning with marginalized corrupted features. We (implicitly) corrupt existing data as a means to generate additional, infinitely many, training samples from a slightly different data distribution -- this is computationally tractable, because the corruption can be marginalized out in closed form. Our framework leads to machine learning algorithms that are fast, generalize well and naturally scale to very large data sets. We showcase this technology as regularization for general risk minimization and for marginalized deep learning to learn document representations. We further show that marginalized corruption is not limited to features. Marginalized corrupted labels can be used to create dense representations of image tags, and we show that these are significantly better suited for applications such as tag prediction.
Kilian Q. Weinberger is an Assistant Professor in the Department of Computer Science & Engineering at Washington University in St. Louis. He received his Ph.D. from the University of Pennsylvania in Machine Learning under the supervision of Lawrence Saul and his undergraduate degree in Mathematics and Computer Science from the University of Oxford. During his career he has won several best paper awards at ICML, CVPR and AISTATS. In 2011 he was awarded the AAAI senior program chair award and in 2012 he received the NSF CAREER award. Kilian Weinberger's research is in Machine Learning and its applications. In particular, he focuses on high dimensional data analysis, metric learning, machine learned web-search ranking, transfer- and multi-task learning as well as biomedical applications. Before joining Washington University in St. Louis, Kilian worked as a research scientist at Yahoo! Research in Santa Clara.
- Tuesday, 11 March 2014, 2:30PM -- QNC 0101
- Seminar -- Institute for Quantum Computing
- Speaker: Wolfram Pernice, Karlsruhe Institute of Technology, Germany
Title: "Light force devices and non-classical optics on a chip"
Abstract: Nanophotonic devices allow for realizing complex optical functionality that is otherwise difficult to achieve with free-space optical setups. While such circuits find a multitude of applications in telecommunication and optical signal processing, their tremendous potential for non-classical optics remains largely unexplored. I will present an integrated platform in which key challenges of integrated quantum optics are addressed by combining nanophotonic and superconducting nanowire devices with optomechanical resonators. Superconducting nanowires are particularly promising for recording single photon events in a chip-scale framework. Besides offering near-perfect detection efficiency, they also provide small footprint and scalability as a key step towards integrated quantum optical circuits. In order to enable photon-emission on-chip we use nanoscale carbon-nanotube sources for electroluminescent generation of light. Working with a nonlinear optical substrate material furthermore enables active control of photon interaction. Leveraging additional degrees of freedom provided by free-standing mechanical structures thus yields a rich architecture for studying fundamental physics and emerging applications in chip-based metrology.
- Tuesday, 11 March 2014, 3:00PM -- MC 5136
- Combinatorial Optimization Seminar -- Combinatorics and Optimization
- Speaker: Steffen Marcus, University of Utah
Title: "On the Piecewise Polynomality of Double Hurwitz Numbers"
Abstract: Hurwitz numbers count degree d branched covers of the Riemann sphere by a genus g Riemann surface with prescribed ramification over one branch point and simple ramification over the others. They are intimately related to the geometry of the moduli space of curves through the famous ELSV formula. Double Hurwitz numbers similarly count covers with prescribed ramification over two points. In this talk I’m going to explain how we can describe double Hurwitz numbers as in- tersection numbers on the moduli space of curves using the geometry of the moduli space of relative stable maps. This helps explain geometrically the chamber/wall- crossing piecewise polynomial structure of double Hurwitz numbers. This is joint work with Renzo Cavalieri.
- Wednesday, 12 March 2014, 10:30AM -- DC 1304
- Seminar -- Computer Science
- Speaker: Dr. H. Andrés Lagar-Cavilla, Co-Founder of Gridcentric, Inc.
Title: "You Can Have your Virtual Cake and Eat It Too"
Abstract: The last decade has seen a staggering transformation of the technology that powers computing around the world. First, virtualization gained traction as an antidote to IT management burden and server sprawl. While slow, early virtualization products provided so much value that the processor vendors had to give up on their disregard for x86 virtualization. Then, open source virtualization ramped up, and with it, the advent of practical, truly multi-tenant cloud computing platforms at economies of scale.
It has been often noted that cloud computing turns computation into an utility, like electricity, or water. I posit that today, when opening the computing utility tap, we get sealed plastic bottles rather than running water, or 12V batteries rather than a steady 110V AC flow. A tremendous opportunity is being
wasted through the inertia of legacy patterns, which impose unneeded operational and cognitive overhead. We are barely scratching the surface of what can be done with utility computing.
Here is one example of what I mean: the SnowFlock system. Cloud users (and providers) size VMs for peak capacity like the physical server one purchases for a rack. They boot them, as if they were a PC, with a BIOS. They install software on each VM they boot, as if virtual disks could not be snapshotted. They keep the VMs up forever, regardless of shifts in load. All of it, as if a VM were a real piece of iron! With SnowFlock, we showed that one could fork VMs like UNIX forks processes. That VMs can leave behind the legacy notions of the physical world, and focus on being nimble, elastic slices of an underlying multi-tenant infrastructure. By forking VMs efficiently, workloads can scale out their cloud use in a second, spawn VMs that process for a minute or less, claiming and relinquishing resources in a fluid, fine-grained fashion. SnowFlock is a new paradigm that taps on the nature of cloud elasticity, simplifies writing cloud applications, and greatly improves the multiplexing of provider resources.
After reviewing previous work including SnowFlock, I will focus on key questions for the future of cloud: In a world of omniscient government agencies, can we ensure through technical means complete confidentiality of user data in a cloud, even that residing in memory? In a world covered with cellular data networks, where do we draw the line between clients and servers? How far can we push the envelope when attempting to keep client and cloud state in sync? Addressing questions like this, will turn cloud computing into a true utility: seamless, convenient, robust, and secure.
H. Andrés Lagar-Cavilla is a systems builder, and an experimental researcher. Andrés obtained his PhD from University in Toronto in 2009, along the way winning the NSERC 2010 Doctoral award, and the Eurosys 2009 Best Paper award. Andrés is both and academic as well as an industrial researcher. In the last five years, Andrés has published a dozen papers in top tier venues, and led a team of ten people at Gridcentric Inc, towards crystallizing his vision for cloud computing into a revenue-generating production technology. Andrés's contributions to software systems span the fields of virtualization, operating systems, cloud computing, security, mobile devices, power management, disaster recovery, virtual desktops, high-performance computing, and graphics acceleration. Andrés and his wife Claudia are the overjoyed parents to Lucas.
- Wednesday, 12 March 2014, 2:30PM -- MC 5046
- Algebra Seminar -- Pure Mathematics
- Speaker: Brendan Nolan, University of Kent (Canterbury)
Title: "“(Generalised) Dixmier-Moeglin Equivalence”"
Abstract: It is typically difficult to classify the irreducible representations of a given algebra A. A good first step is to try to find the primitive ideals i.e. the annihilators of the simple modules. Primitive ideals are prime (in the noncommutative sense) and if one is lucky, the primitive ideals will coincide with two other types of prime ideals: (i) the prime ideals which are locally closed in Zariski topology and (ii) the prime ideals P of A which are such that the centre of the ring of fractions of A/P is an algebraic extension of the ground field (these are called rational ideals). When these ideals coincide, the algebra A is said to satisfy the Dixmier-Moeglin equivalence.
I will outline the proof of the Dixmier-Moeglin equivalence for a well-behaved class of Ore extensions, relying on Cauchon’s Deleting Derivations algorithm. I will discuss the hope that, in some such Ore extensions, the prime ideals which are any given ”distance” from being primitive will coincide with the prime ideals which are the same ”distance” from being locally closed and with the prime ideals which are the same ”distance” from being rational.
- Wednesday, 12 March 2014, 3:30PM -- MC 6486
- Graph Theory Seminar -- Combinatorics and Optimization
- Speaker: Alan Arroyo Guevara, University of Waterloo
Title: "The 2-Linkage Problem"
Abstract: Given a graph G and four vertices x1, x2, y1, y2, a 2-linkage is a pair of vertex disjoint paths, one connecting x1 to y1 and the other connecting x2 to y2. Jung showed that a 4-connected graph G has no 2-linkage if, and only if, it is planar and x1, x2, y1, y2 occur in this cyclic order on the boundary walk of some face. A few years later, Seymour and Thomassen generalized this result and characterized when a 2-linkage exists for a general graph. In this talk, we present and prove a generalization of Jung's theorem and discuss why planarity plays an important role in determining when a 2-linkage exists.
- Thursday, 13 March 2014, 9:30AM -- Math & Computer, Room 5158 true
- PhD Thesis Presentation/Defence -- Applied Mathematics
- Speaker: Krishan Rajaratnam, Dept. of Applied Mathematics, University of Waterloo
Title: "Orthogonal separation of the Hamilton-Jacobi equation on Spaces of Constant Curvature"
Abstract: What is in common with the Kepler problem, a Hydrogen atom and a rotating black-hole? These systems are described by different physical theories, but much information about them can be obtained by separating an appropriate Hamilton-Jacobi equation. The separation of variables of the Hamilton-Jacobi equation is an old but still powerful tool for obtaining exact solutions.
In this presentation we will give an overview of the recently constructed geometric theory of orthogonal separable coordinates for the Hamilton-Jacobi equation on spaces of constant curvature. These coordinates are of interest in mathematical physics because they also allow for the separation of the Helmholtz equation in Euclidean space and the Klein-Gordon equation in Minkowski space.
The theory revolves around a certain type of conformal Killing tensor, hereafter called a concircular tensor. Our first main result shows how to use these tensors to construct a special class of separable coordinates (hereafter called Kalnins-Eisenhart-Miller (KEM) coordinates) on a given space. Conversely, the second result generalizes the Kalnins-Miller classification to show that any orthogonal separable coordinates in a space of constant curvature are KEM coordinates. A closely related recursive algorithm is defined which allows one to intrinsically (coordinate independently) search for KEM coordinates which separate a given (natural) Hamilton-Jacobi equation. This algorithm is exhaustive in spaces of constant curvature.
We will expose this theory by applying it to prove separability of well known coordinate systems in Euclidean 3-space, and then to study the separability properties of the Calogero-Moser system.
- Thursday, 13 March 2014, 1:30PM -- MC 5136B
- Number Theory Seminar Seminar -- Pure Mathematics
- Speaker: Hector Pasten, Queen’s University
Title: "“Modular forms, ABC and effective unit equation”"
Abstract: In this talk I will give a brief overview of a known approach to the ABC conjecture using modular forms. Then I will explain how this approach actually gives a partial result for the ABC conjecture and Szpiro’s conjecture. As a consequence, we will obtain a new effective proof of the finiteness of solutions to the S-unit equation, which does not involve linear forms in logarithms. This is joint work with Ram Murty.
- Thursday, 13 March 2014, 2:00PM -- MC 5158
- Algebraic Combinatorics Seminar -- Combinatorics and Optimization
- Speaker: David M. R. Jackson, University of Waterloo
Title: "A Quantum Invariant of Knots"
Abstract: This will be an informal talk about knot invariants which
will not presuppose any background in knot theory. The theory is rich in combinatorial constructions combined with specific algebras. Thus the area also serves as a rich context for studying the combinatorial and enumerative properties of these algebras. Such algebras include Hopf algebras and Lie algebras, and their
combinatorialisation (for example, through Penrose's diagrammatic tensor calculus). My aim is to reach the Reshetikhin-Turaev Theorem for constructing invariants,
and then to show how the Jones polynomial, the invariant of the title, may be deduced from it.
- Thursday, 13 March 2014, 3:30PM -- MC 6486
- Combinatorial Optimization Seminar -- Combinatorics and Optimization
- Speaker: Speaker #1: Ricci Tam Speaker #2: Thomas Sumbler, University of Waterloo
Title: "Speaker #1: Lattice Point Enumeration Speaker #2: The Colourful Linear Feasibiity Problem"
Abstract: Speaker #1:Given a lattice polytope $P$, the "lattice-point enumerator" is a function on $t$ that counts the number of lattice points in the $t$-dilation of $P$. This function is associated with the Ehrhart series - a generating function counting lattice points in $t$-dilations of a polytope. I will sketch a proof showing that the lattice-point enumerator is in fact a polynomial.
Speaker #2: The colouful linear feasibility problem has been described as "an outstanding problem on the border line between tractable and intractable problems." Suppose there are d+1 coloured sets of points, with 0 in the convex hull of each set. Can we find a set of points, one from each colour, that contains 0 in their convex hull? This presentation will give a formal description of the problem, and describe a couple algorithms for its solution.
- Thursday, 13 March 2014, 3:30PM -- Math &, Room 5158 true
- Colloquium -- Applied Mathematics
- Speaker: Dr. David Kopriva, Department of Mathematics | The Florida State University
Title: "Accurate Computation of Wave Scattering in Discontinuous Media with a Discontinuous Galerkin Spectral Element Method"
Remarks: Wine and cheese to follow in MC 5136
Abstract: Interesting phenomena arise when waves scatter at material interfaces. Electromagnetic waves, for instance, can be fully reflected, fully transmitted or even jump gaps depending on incident angles and the relative dielectric properties between the materials. Scattering off moving interfaces challenges one's intuition. Crucial to the accurate computation of these phenomena is the ability to approximate hyperbolic PDEs where the coefficients have jump discontinuities and to propagate the waves accurately through the continuous portions of the domain. We will show how to compute material interface problems with spectral accuracy using a discontinuous Galerkin spectral element method, which naturally handles jump discontinuities in material properties and solutions.
- Thursday, 13 March 2014, 4:00PM -- M3 3127
- Seminar -- Statistics & Actuarial Science
- Speaker: Andriy Derkach, University of Toronto
Title: "Statistical methodologies for genetic association studies with rare variants"
Abstract: In the search for genetic factors that are associated with complex heritable human traits, considerable attention has been focussed on rare variants that individually have small effects. Many recent papers have proposed testing strategies to detect association between traits and groups of rare variants with competing claims about the performance of various tests. The power of a given test in fact depends on the nature of any association and on the rareness of the variants in question
In this presentation we review such tests within a unified framework that covers a whole range of genetic models. We divide tests into linear and quadratic classes. We study performance of both classes through exact and asymptotic power calculations and novel simulation studies. We show that test statistics from both classes are complementary and they are powerful under limited settings. To achieve robustness, we propose to combine the evidence of association from two or more complementary tests. We consider the minimum-p and Fisher's methods of combining p-values from linear and quadratic statistics. Our extensive simulation studies show that both methods are robust across wide range. Our results also show that power to detect association in plausible genetic scenarios is low for studies of medium size unless a high proportion of the chosen variants are causal. To increase power, we also consider response-dependent sampling in association studies with rare variants. We also show that, under a broad range of generalized likelihoods and sampling plans, score statistic for testing association between a response Y and genetic variants are identical for two main likelihood approaches, and are of the same form as for ordinary random sampling on Y. Lastly, we evaluate proposed methodology and various sampling strategies with extensive simulations.
This is joint work with Dr. Lei Sun and Dr. Jerry Lawless.
- Friday, 14 March 2014, 3:30AM -- MC 5136B
- Analysis Seminar Seminar -- Pure Mathematics
- Speaker: Eberhard Kirchberg, Humboldt Universit ̈at zu Berlin
Title: "“An inner characterization of local reflexivity for C*-algebras and related open questions”"
- Friday, 14 March 2014, 11:00AM -- DC 2310
- Database Research Group Master's Thesis Presentation -- Computer Science
- Speaker: Xin Pan, graduate student, David R. Cheriton School of Comp. Sci., Univ. Waterloo
Title: "Database High Availability using SHADOW Systems"
Abstract: Various High Availability DataBase systems (HADB) are used to provide
Pairing an active database system with a standby system is one commonly
techniques. The active system serves read/write workloads. One or more
replicate the active and serve read-only workloads. Though widely used,
this technique has
some significant drawbacks: The active system becomes the bottleneck
under heavy write
workloads. Replicating changes synchronously from the active to the
reduces the performance of the active system. Asynchronous replication,
however, risk the
loss of updates during failover. The shared-nothing architecture of
is unnecessarily complex and cost inefficient.
In this thesis we present SHADOW systems, a new technique for database
In a SHADOW system, the responsibility for database replication is
the database systems into a shared, reliable, storage system. The active
and standby systems
share access to a single logical copy of the database, which resides in
SHADOW introduces write offloading, which frees the active system from
the need to
update the persistent database, placing that responsibility on the
system instead. By exploiting shared storage, SHADOW systems avoid the
database-managed synchronized replication, while ensuring that no
updates will be lost
during a failover. We have implemented a SHADOW system using PostgreSQL,
present the results of a performance evaluation that shows that the
SHADOW system can
outperform both traditional synchronous replication and standalone
- Friday, 14 March 2014, 11:30AM -- DC 2306C (AI Lab) true
- Health Informatics Master's Thesis Presentation -- Computer Science
- Speaker: Xiao Yang, graduate student, David R. Cheriton School of Comp. Sci., Univ. Waterloo
Title: "Quick and Automatic Selection of POMDP Implementations on Mobile Platform Based on Battery Consumption Estimation"
Abstract: Partially Observable Markov Decision Process (POMDP) is widely used to model sequential decision making process under uncertainty and incomplete knowledge of the environment. It requires strong computation capability and is thus usually deployed on powerful machine. However, as mobile platforms become more advanced and more popular, the potential has been studied to combine POMDP and mobile in order to provide a broader range of services. And yet a question comes with this trend: how should we implement POMDP on mobile platform so that we can take advantages of mobile features while at the same time avoid being restricted by mobile limitations, such as short battery life, weak CPU, unstable networking connection, and other limited resources.
In response to the above question, we first point out that the cases vary by problem nature, accuracy requirements and mobile device models. Rather than pure mathematical analysis, our approach is to run experiments on a mobile device and concentrate on a more specific question: which POMDP implementation is the ``best'' for a particular problem on a particular kind of device. Second, we propose and justify a POMDP implementation criterion mainly based on battery consumption that quantifies ``goodness'' of POMDP implementations in terms of mobile battery depletion rate. Then, we present a mobile battery consumption model that translates CPU and WIFI usage into part of the battery depletion rate in order to greatly accelerate the experiment process. With our mobile battery consumption model, we combine a set of simple benchmark experiments with CPU and WIFI usage data from each POMDP implementation candidate to generate estimated battery depletion rates, as opposed to conducting hours of real battery experiments for each implementation individual. The final result is a ranking of POMDP implementations based on their estimated battery depletion rates. It serves as a suggestion on POMDP implementation selection for mobile developers.
We develop a mobile software toolkit to automate the above process. Given basic POMDP problem specifications, a set of POMDP implementation candidates and a simple press on the ``start'' button, the toolkit automatically performs benchmark experiments on the target device on which it is installed, and records CPU and WIFI statistics for each POMDP implementation candidate. It then feeds the data to its embedded mobile battery consumption model and produces an estimated battery depletion rate for each candidate. Finally, the toolkit visualizes the ranking of POMDP implementations for mobile developers' reference.
Evaluation is assessed through comparsion between the ranking from estimated battery depletion rate and that from real experimental battery depletion rate. We observe the same ranking out of both, which is also our expectation. What's more, the similarity between estimated battery depletion rate and experimental battery depletion rate measured by cosine-similarity is almost 0.999 where 1 indicates they are exactly the same.
- Friday, 14 March 2014, 2:30PM -- MC 5046
- Geometry & Topology Seminar Seminar -- Pure Mathematics
- Speaker: Valentino Tosatti, Northwestern University
Title: "“Calabi-Yau theorems for non-Kahler metrics”"
Remarks: **PLEASE NOTE ROOM CHANGE**
Abstract: The celebrated Calabi-Yau theorem is an existence result for Kahler metrics with prescribed volume form (or equivalently prescribed Ricci curvature) on a compact Kahler manifold. Re- cently, some progress has been made in finding extensions of this result to different classes of non-Kahler metrics, such as balanced or Gauduchon metrics. I will describe several such theorems, including applications, and discuss some open questions. This is joint work with Ben Weinkove.
- Friday, 14 March 2014, 3:30PM -- MC 5158
- Tutte Seminar Seminar -- Combinatorics and Optimization
- Speaker: Elliot Anshelevich, Rensselaer Polytechnic Institute
Title: "Stable Matching, Friendship and Altruism"
Abstract: We will discuss both integral and fractional versions of "correlated stable matching" problems. Each player is a node in a social network and strives to form a good match with a neighboring player; the player utilities from forming a match are correlated. We consider the existence, computation, and inefficiency of stable matchings from which no pair of players wants to deviate. We especially focus on networks where players are embedded in a social context, and may incorporate friendship relations or altruism into their decisions. When the benefits from a match are the same for both players, we show that incorporating the well-being of other players into their matching decisions significantly decreases the price of stability, while the price of anarchy remains unaffected. Furthermore, a good stable matching achieving the price of stability bound always exists and can be reached in polynomial time. We extend these results to more general matching rewards, when players matched to each other may receive different utilities from the match. For this more general case, we show that incorporating social context (i.e., "caring about your friends") can make an even larger difference, and greatly reduce the price of anarchy. Finally, we extend most of our results to network contribution games, in which players can decide how much effort to contribute to each incident edge, instead of simply choosing a single node to match with.