Faculty of Mathematics, University of Waterloo

WebNotice Postings: 23-Apr-2018 through 29-Apr-2018

Postings for all Departments

Monday, 23 April 2018, 10:30AM -- DC 1302
Data Systems Group Seminar -- Computer Science
Speaker: Barzan Mozafari, Department of Computer Science and Engineering, University of Michigan
Title: "Making Approximate Query Processing Mainstream: Progress and the Road Ahead"
Abstract: Approximate Query Processing (AQP) has been a subject of academic research for over 25 years now. However, until recently, it has had little success in terms of commercial adoption. In talk, we explain the interface and deployment barriers that have historically slowed down the adoption of AQP by database vendors and enterprise users alike. We then discuss some of the recent advances that have successfully overcome some of these barriers. We also introduce several research directions and exciting opportunities that would not be possible in a database with precise answers. In particular, we explore several opportunities at the intersection of statistics and data management, including our Database Learning — a database system that learns and becomes smarter over time — as well as novel abstractions for speeding up machine learning workloads through approximate operators and error-computation tradeoffs.

• • • • •

Bio: Barzan Mozafari is a Morris Wellman Assistant Professor of Computer Science and Engineering at the University of Michigan, Ann Arbor, where he leads a research group designing the next generation of scalable databases using advanced statistical models. Prior to that, he was a Postdoctoral Associate at MIT. He earned his Ph.D. in Computer Science from UCLA in 2011. His research career has led to several open-source projects, including DBSeer (an automated database diagnosis tool), BlinkDB (a massively parallel approximate query engine), and SnappyData (an HTAP engine that empowers Apache Spark with transactions and real-time analytics). He has won the National Science Foundation CAREER award, as well as several best paper awards in ACM SIGMOD and EuroSys. He is the founder of Michigan Software Experts, and a strategic advisor to SnappyData, a company that commercializes the ideas introduced by BlinkDB.

Monday, 23 April 2018, 11:30AM -- MC 5417 true
Seminar -- Applied Mathematics
Speaker: Julian Rennert, Department of Applied Mathematics, University of Waterloo
Title: "(quasi-) Hopf algebras and their origin in physics"
Abstract: Symmetry has always played an important role in physics and our description of nature. Quantum theory in particular allows for more general symmetries than those we know from classical physics and the most general, compatible with our current understanding of quantum physics, are given by so-called quasi-Hopf algebra symmetries. In this first lecture we give a simple introduction into the topic of (quasi-) Hopf algebras and present some of their origins and current applications in physics and mathematics such as 3D quantum gravity, Knot-invariants and quantum computing.

Monday, 23 April 2018, 11:30AM - ** Date Change ** - now Wednesday, 25 April 2018, 12:00PM
** See updated entry for additional event information **
Speaker: Julian Rennert, Department of Applied Mathematics, University of Waterloo
Title: "Poisson-Lie groups and quasi-Poisson spaces as semi-classical limits of (quasi-) Hopf algebras"

Monday, 23 April 2018, 1:00PM -- DC 2310
Data Systems Group Master's Thesis Presentation -- Computer Science
Speaker: Weicong Ma, David R. Cheriton School of Computer Science
Title: "On the Utility of Adding An Abstract Domain and Attribute Paths to SQL"
Abstract: Albeit its popularity today, RDBMS and the relational model still have many limitations. For example, one needs to pay premature attention to naming issues in the schema designing phase; and the syntax for conjunctive queries is verbose and redundant, especially for multi-table joins and composite primary/foreign keys. In this thesis, we introduce and explain the method to handle and resolve these issues that is proposed by Borgida, Toman, and Weddell: the conceptual schema that supports abstract relations and attributes, and an extended query language SQLpath built on top of standard SQL that supports the usage of attribute paths and abstract attributes in queries. We demonstrate a systematic approach to map a database schema expressed in the relational model to the abstract relational model and illustrate how to write SQLpath queries with attribute paths to solve query problems involving complex table joins. This thesis can server as both an introduction and tutorial to abstract database modelling and the SQLpath query language.

Additionally, we performed an empirical experiment to evaluate the performance of SQLpath when solving real database query problems by employing students with prior experience with SQL to read and write SQLpath queries and recorded their accuracy and time consumption against usage of regular SQL.

The result of this experiment is presented in this thesis, including a statistical analysis of the results. In short, we uncover evidence that SQLpath is more efficient to use for both reading and writing conjunctive and alike queries, especially for non-trivial cases where multiple constraints were required. However, while SQLpath can hide explicit table joins when writing queries spanning multiple intermediate tables, whether this benefit can make users produce more accurate results still remains unclear as we were not able to draw any conclusion from collected data due to lack of statistical significance.

Tuesday, 24 April 2018, 1:00PM -- QNC 1201
Institute for Quantum Computing PhD Seminar -- Computer Science
Speaker: Chunhao Wang, David R. Cheriton School of Computer Science
Title: "Dissipative Quantum Search"
Abstract: We give a dissipative quantum search algorithm that is based on a novel dissipative query model. If there are $N$ items and $M$ of them are marked, this algorithm performs a fixed-point quantum search using $O(\sqrt{N/M}\log(1/\epsilon))$ queries with error bounded by $\epsilon$. In addition, we present a continuous-time version of this algorithm in terms of Lindblad evolution.

Tuesday, 24 April 2018, 2:00PM -- QNC 1201
Institute for Quantum Computing PhD Seminar -- Computer Science
Speaker: Chunhao Wang, David R. Cheriton School of Computer Science
Title: "A Quantum Algorithm for Simulating Non-sparse Hamiltonians"
Abstract: We present a quantum algorithm for simulating the dynamics of Hamiltonians that are not necessarily sparse. Our algorithm is based on the assumption that the entries of the Hamiltonian are stored in a data structure that allows for the efficient preparation of states that encode the rows of the Hamiltonian. We use a linear combination of quantum walks to achieve a poly-logarithmic dependence on the precision.

The time complexity measured in terms of circuit depth of our algorithm is $O(t\sqrt{N}\norm{H}\polylog(N, t\norm{H}, 1/\epsilon))$, where $t$ is the evolution time, $N$ is the dimension of the system, and $\epsilon$ is the precision. Our algorithm can directly be applied as a subroutine for unitary implementations and solving linear systems, achieving a $\widetilde{O}(\sqrt{N})$ dependence for both applications.

Wednesday, 25 April 2018, 12:00PM -- M3-3103 true
Seminar -- Applied Mathematics
Speaker: Julian Rennert, Department of Applied Mathematics, University of Waterloo
Title: "Poisson-Lie groups and quasi-Poisson spaces as semi-classical limits of (quasi-) Hopf algebras"
Abstract: In this second lecture we show how (quasi-) Hopf symmetries, that were found in the realm of quantum theory, led to interesting new structures in (classical) Poisson geometry. We consider so-called (quasi-) Poisson-Lie groups as the semi-classical limits of (quasi-) Hopf algebras and, in particular, compare the (quasi-) Lie-bialgebra structures of the Lie algebra su(2).

Wednesday, 25 April 2018, 1:30PM -- M3 4206
Comprehensive Exam -- Applied Mathematics
Speaker: Giselle Sosa Jones, Department of Mathematics, University of Waterloo
Title: "Space-Time Hybridizable Discontinuous Galerkin Methods for Free Surface Waves Problems"
Abstract: Free surface problems are of great interest in many fields such as naval and maritime engineering. For example, one may be interested in how water waves will interact and affect ships and offshore structures so that they can be designed properly. Mathematically, free surface problems are modeled by systems of partial differential equations that describe the motion of a fluid, and certain nonlinear boundary conditions that define the free surface. These problems are particularly hard to solve, because the free surface that defines the shape of the domain is part of the solution of the problem and has to be determined at each time step. This is why we require a numerical method that easily handles time dependent domains, that is higher order accurate in both space and time, and that satisfies desirable conservation and stability properties. Space-time discontinuous Galerkin (DG) methods are known for being suitable for problems where the domain changes in time, which makes them appropriate for free surface problems. Also, by making no distinction between space and time, it is easy to make them higher order accurate. Moreover, Hybridizable/Embedded Discontinuous Galerkin (HDG/EDG) methods have been proven to have several advantages over standard DG methods. In HDG/EDG methods, a variable that lives only on the facets is introduced. This allows to couple the degrees of freedom on elements only to the degrees of freedom on facets. Therefore, the element degrees of freedom can be eliminated and a linear system only for the facet variables has to be solved. In EDG methods, the facet variables are approximated by continuous functions. In the case of incompressible flows, for example, HDG methods are H(div)-conforming, locally momentum conserving and energy stable. Moreover, they produce pointwise divergence free velocity fields. Previous work in the area of numerical methods applied to free surface problems, has resulted in issues with stability due to the discontinuous approximation of the free surface, as a result of the discontinuous polynomial approximation of DG methods. For this reason we propose using a space-time HDG method to discretize the system of partial differential equations, but a space-time EDG to discretize the free surface boundary conditions, which allows to obtain a continuous approximation to the wave height. In this talk, we discuss the challenges associated to solving free surface problems as well as our proposal for solving said problems. We present a HDG discretization of Laplace’s equation with linear free surface boundary conditions. This HDG method produces approximations to the velocity potential and its gradient that converge with optimal rate. Additionally, an element-by-element postprocessing can be performed in order to obtain superconvergence of the scalar variable. We present a numerical test that shows the rates of convergence of the method, and also a simulation of water waves generated by a wave maker.

Thursday, 26 April 2018, 10:00AM -- DC 3126
Artificial Intelligence Lab Master's Thesis Presentation -- Computer Science
Speaker: Amir-Hossein Karimi, David R. Cheriton School of Computer Science
Title: "Exploring New Forms of Random Projections for Prediction and Dimensionality Reduction in Big-Data Regimes"
Abstract: The story of this work is dimensionality reduction. Dimensionality reduction is a method that takes as input a point-set P of n points in R^d where d is typically large and attempts to find a lower-dimensional representation of that dataset, in order to ease the burden of processing for down-stream algorithms. In today’s landscape of machine learning, researchers and practitioners work with datasets that either have a very large number of samples and/or include high-dimensional samples. Therefore, dimensionality reduction is applied as a pre-processing technique primarily to overcome the curse of dimensionality.

Generally, dimensionality reduction improves time and storage space required for processing the point-set, removes multi-collinearity and redundancies in the dataset where different features may depend on one another, and may enable simple visualizations of the dataset in 2-D and 3-D, making the relationships in the data easy for humans to comprehend. Dimensionality reduction methods come in many shapes and sizes. Methods such as Principal Component Analysis (PCA), Multi-dimensional Scaling, IsoMaps, and Locally Linear Embeddings are amongst the most commonly used method of this family of algorithms. However, the choice of dimensionality reduction method proves critical in many applications as there is no one-size-fits-all solution, and special care must be considered for different datasets and tasks.

Furthermore, the aforementioned popular methods are data-dependent, and commonly rely on computing either the Kernel / Gram matrix or the covariance matrix of the dataset. These matrices scale with increasing number of samples and increasing number of data dimensions, respectively, and are consequently poor choices in today’s landscape of big-data applications. Therefore, it is pertinent to develop new dimensionality reduction methods that can be efficiently applied to large and high-dimensional datasets, by either reducing the dependency on the data, or side-stepping it altogether. Furthermore, such new dimensionality reduction methods should be able to perform on par with, or better than, traditional methods such as PCA. To achieve this goal, we turn to a simple and powerful method called random projections.

Random projections are a simple, efficient, and data-independent method for stably embedding a point-set P of n points in R^d to R^k where d is typically large and k is on the order of log n. Random projections have a long history of use in dimensionality reduction literature with great success. In this work, we are inspired to build on the ideas of random projection theory, and extend the framework and build a powerful new setup of random projections for large high-dimensional datasets, with comparable performance to state-of-the-art data-dependent and nonlinear methods. Furthermore, we study the use of random projections in domains other than dimensionality reduction, including prediction, and show the competitive performance of such methods for processing small dataset regimes.

Thursday, 26 April 2018, 10:30AM -- MC 6334
Comprehensive Exam -- Applied Mathematics
Speaker: Nicholas Funai, Department of Applied Mathematics, University of Waterloo
Title: "Light matter interaction and their consequences in relativistic theory"
Abstract: Light matter interaction is modelled in several different ways, ranging from the exact minimal model for EM interactions to the Unruh-DeWitt interaction for scalar fields. My research has had two main objectives, one being how exploiting the Unruh-DeWitt interaction can lead to violations of classical energy conditions, which leads to exotic behaviour in the spacetime metric; the second being how valid the common approximations made to the exact minimal model for EM interactions are and what are the consequences of these approximations with regards to causality. In particular we focus on approximations such as the dipole approximation and the rotating wave approximations.

Thursday, 26 April 2018, 10:30AM -- DC 1304 true
Data Systems Group Seminar -- Computer Science
Speaker: Rachel Pottinger, Department of Computer Science, University of British Columbia
Title: "Improving Understanding and Exploration of Data by Non-Database Experts"
Abstract: Users are faced with an increasing onslaught of data, whether it's in their choices of movies to watch, assimilating data from multiple sources, or finding information relevant to their lives on open data registries. In this talk I discuss some of the recent and ongoing work about how to improve understanding and exploration of such data, particularly by users with little database background.

• • • • •

Bio: Rachel Pottinger is an Associate Professor in Computer Science at the University of British Columbia. She received her PhD in computer science from the University of Washington in 2004. Her main research interest is data management, particularly semantic data integration, how to manage metadata, how to manage data that is currently not well supported by databases, and how to make data easier to understand and explore.

Friday, 27 April 2018, 9:30AM -- DC 3317
Human-Computer Interaction Master's Thesis Presentation -- Computer Science
Speaker: Lisa Elkin, David R. Cheriton School of Computer Science
Title: "Contact-sensing Input Device Manipulation and Recall"
Abstract: We study a cuboid tangible pen-like input device similar to Vogel and Casiez’s Conte. A conductive 3D-printed Conte device enables touch sensing on a capacitive display and orientation data from an enclosed IMU reliably distinguishes all 26 corners, edges, and sides. The device’s size is constrained by hardware required for sensing. We evaluate the impact of size form-factor on manipulation times for contact-to-contact transitions. A controlled experiment logs manipulation times performed with three sizes of 3D printed mock-ups of the device. Computer vision techniques reliably distinguish between all 26 possible contacts, and a resistive touch sensor provides accurate timing information. In addition, a transition to touch input is tested, and a mock-up of a digital pen is included as a baseline comparison.

Results show larger devices are faster, contact-to-contact transition time increases with distance between contacts, but transitions to barrel edges can be slower than some end-over-end transitions. A comparison with a pen-shaped baseline indicates no loss in transition speed for most equivalent transitions.

Based on our results, we discuss ideal device sizes and improvements to the simple extruded-rectangle form-factor. Subsequently, we evaluate learning and recall of commands located on physical landmarks on the exterior of a 3D tangible input device in comparison with a 2D spatial interface. Each of the 26 contacts is a physical spatial landmark on the exterior of Conte. A pilot study compares command learning and recall for Conte with a 2D grid interface, using small and large commands sets. To facilitate novice learning, an on-screen model of Conte replicates the physical device’s orientation and displays icons representing commands on the corresponding landmarks.

Results show there is likely no difference between 2D and 3D spatial interface recall for a small command set and high recall is possible with large command sets. Applications illustrating possible use cases are discussed as well as possible improvements to the on-screen guide based on our results.

Friday, 27 April 2018, 10:00AM -- M3 4206
Comprehensive Exam -- Applied Mathematics
Speaker: Hanzhe (Tom) Chen, Department of Mathematics, University of Waterloo
Title: "Two and Three Dimensional Floating Objects with Surface Tension"
Abstract: The study of floating objects can be traced back to Archimedes’ time. With the consideration of surface tension, the ability and stability of flotation gets complicated but more interesting. We propose two basic problems: the infinity long horizontal floating cylinder and the floating ball on an unbounded reservoir. For the floating cylinder problem (two-dimensional), circular and strictly convex cross-sections are both considered. The circular floating cylinder has a symmetric configuration. As the solution of one-dimensional capillary equation can be translated horizontally, there is a possibility that the fluid interfaces intersect. We apply both the force and the energy approaches, at most two equilibrium configurations can be obtained, one is stable, the other is not, in consideration of the possible of intersection of interfaces. Unlike the circular cylinder, the configuration of strictly convex body usually admits asymmetric configurations. Conditions are imposed to guarantee a unique configuration for a fixed position. An example of an ellipse with rotation will be given. For the floating ball problem (three-dimensional), we assume the floating configuration is radially symmetric. The fluid interface has to be solved numerically. An example with two force balanced points will be given, we will show both of them are stable. More examples and applications are anticipated.

Friday, 27 April 2018, 11:30AM -- DC 3126 true
Software Engineering Research Group PhD Seminar -- Computer Science
Speaker: Rafael Olaechea Velazco, David R. Cheriton School of Computer Science
Title: "Learning Software Behavioral Models from Execution Traces"
Abstract: Software behavioural models, such as finite state machines, are used as an input to model checking tools to verify that software satisfies its requirements. As constructing such models by hand is time-consuming and error-prone, researchers have developed tools to automatically extract such models from systems’ execution traces.

In this seminar I will present GK-Tail+, which is an existing state-of-the-art tool that analyzes execution traces that consist of method calls annotated with values for their parameters. I discuss how effective the extracted models are in precisely representing the set of execution traces that the software can generate. Finally, I discuss the challenges associated with evaluating the quality of the extracted models.

Friday, 27 April 2018, 1:30PM -- DC 1304
Networks and Distributed Systems Seminar -- Computer Science
Speaker: Milan Jain, PhD Scholar in Computer Science, Indraprastha Institute of Information Technology Delhi
Title: "Role of Thermostats — Beyond Control and Feedback"
Abstract: Over the years, researchers have spent a significant amount of time in optimizing the energy consumption of heating, ventilation, and air conditioning (HVAC) units while ensuring user comfort. Consequently, since the advent of programmable thermostats in 1885, today's thermostats are better in design, smarter in controlling the HVAC system, and able to suggest optimal HVAC settings. However, throughout this journey, we have limited the goal of thermostat optimization to develop better control strategies for the HVAC — with or without involving the human.

In this talk — Beyond Control and Feedback — I will discuss the role of thermostats in (1) sensor minimization, (2) comfort localization, and (3) predictive maintenance. Sensor minimization focuses on reducing the necessary instrumentation in buildings, localization assures personalized and targeted thermal comfort for occupants, and predictive maintenance relates to fault detection & diagnosis in HVAC units. Using three different applications, I will demonstrate the ability of the technology behind existing thermostats in achieving these objectives, and associated challenges.

• • • • •

Bio: Milan Jain is a Ph.D. Scholar in Computer Science at the Indraprastha Institute of Information Technology Delhi (IIITD), under the supervision of Dr. Amarjeet Singh and Dr. Vikas Chandan in the Mobile and Ubiquitous Computing Group. He is also a part of Energy Group of IIITD, where he is focused on minimizing energy consumption by HVAC systems, a major contributor towards electricity consumption. In 2014, he completed his Master's in Computer Science from IIITD with specialization in Mobile and Ubiquitous Computing. He received a B.Tech in Information Technology (IT) from NIT Patna in 2012, and visited U. Waterloo for four months in 2016.

Webpage: www.milanjain.com LinkedIn: https://www.linkedin.com/in/milanjainr

Friday, 27 April 2018, 3:30PM -- MC 5501
Tutte Colloquium Seminar -- Combinatorics and Optimization
Speaker: Luc Vinet, Université de Montréal
Title: "Spins Lattices, Graphs and Quantum State Revivals"
Abstract: This talk will describe how certain features of quantum transport along spin chains can be enabled. With an eye to extension on higher dimensional lattices, it will also discuss connections with quantum walks on graphs of the Hamming scheme and one of its generalizations. Some univariate and multivariate orthogonal polynomials will be seen to play a central role.

...... WebNotice