Faculty of Mathematics, University of Waterloo

WebNotice Postings: 20-Nov-2017 through 26-Nov-2017

Postings for all Departments

Monday, 20 November 2017, 9:00AM - ** Date Change ** - now Friday, 17 November 2017, 9:00AM
** See updated entry for additional event information **
Speaker: Xuan Bi, Yale University
Title: "A Group-Specific Recommender System"

Monday, 20 November 2017, 9:00AM -- M3-3127 true
Seminar -- Statistics & Actuarial Science
Speaker: Tianxi Li, University of Michigan
Title: "Statistical tools for analyzing network-linked data"
Remarks: Refreshments will be provided.
Abstract: While classic statistical tools such as regression and graphical models have been well studied, they are no longer applicable when the observations are connected by a network, an increasingly common situation in modern complex datasets. We develop the analogue of loss-based prediction models and graphical models for such network-linked data, by a network-based penalty that can be combined with any number of existing techniques. We show, both empirically and theoretically, that incorporating network information improves performance on a variety of tasks under the assumption of network cohesion, the empirically observed phenomenon of linked nodes acting similarly. Computationally efficient algorithms are developed as well for implementing our proposal. We also consider the general question of how to perform cross-validation and bootstrapping on networks, a long-standing open problem in network analysis. Model selection and tuning for many tasks can be performed through cross-validation, but splitting network data is non-trivial, since removing links leads to a potential change in network structure. We propose a new general cross-validation strategy for networks, based on repeatedly removing edge values at random and then applying matrix completion to reconstruct the full network. We obtain theoretical guarantees for this method under a low rank assumption on the underlying edge probability matrix, and show that the method is computationally efficient and performs well for a wide range of network tasks, in contrast to previously developed approaches that only apply under specific models. Several real-world examples will be discussed throughout the talk, including the effect of friendship networks on adolescent marijuana usage, phrases that can be learned with the help of a collaboration network of statisticians as well as statistician communities extracted from a citation network.

Monday, 20 November 2017, 4:00PM -- MC 5501
Colloquium -- Pure Mathematics
Speaker: Alexei Oblomkov, University of Massachusetts
Title: "Planar curve singularities, knot invariants and representation theory"
Remarks: Refreshments will be served in MC 5403 at 3:30pm.
Abstract: The natural topological object attached to the planar curve singularity is its link, which is the intersection of a small three-sphere around the singularity and the curve. It turns out that the HOMFLY-PT invariant (and its categorification) of the link has a geometric interpretation in terms of topology of the compactified Jacobian of the curve and in terms of Hilbert scheme of points on the curve. When the curve in the question has $\mathbb{C}^*$ symmetry, the HOMFLY-PT polynomial has an interpretation as a character of the degenerate Double Affine Hecke Algebra. The talk is based on the joint results with Eugene Gorsky, Jake Rasmussen, Lev Rozansky, Vivek Shende and Zhiwei Yun.

Tuesday, 21 November 2017, 1:30PM -- MC 5413
Seminar -- Pure Mathematics
Speaker: Parham Hamidi, Department of Pure Mathematics, University of Waterloo
Title: "Integral advice on going up in the world!"
Abstract: Now that we are done with definitions and a few boring results about integral homomorphisms, we can prove the Lying over and Going up Theorems. I will prove Nakayama’s Lemma using a simple trick and talk about some of its applications. Finally we would see how the Lying over and Going up Theorems can be interpreted geometrically in number theory in the theory of ramifications.

(Note: Once again thanks to Nick Rollick for the title.)

Tuesday, 21 November 2017, 2:30PM -- MC 5413
Computability Learning Seminar -- Pure Mathematics
Speaker: Michael Deveau, Department of Pure Mathematics, University of Waterloo
Title: "Isomorphisms that cannot be coded by computable relations -- Part 2"
Abstract: Last time, we saw why it is so useful to code an isomorphism by the image of a computable relation and also explored some cases where this is always possible. We now turn to constructing a pair of structures where this is not possible. That is, we construct two structures -- isomorphic to $(\omega, <)$ -- where this method of establishing the degree of the isomorphism between them will not work.

Tuesday, 21 November 2017, 4:00PM -- MC 5403
Model Theory Seminar -- Pure Mathematics
Speaker: Deirdre Haskell, McMaster University
Title: "Residue field domination in theories of valued fields"
Abstract: The fundamental intuition in the model theory of valued fields is that a valued field with appropriate closure properties is controlled in some sense by its value group and residue field. The classical theorem of Ax-Kochen and Ersov states a version of this at the level of the theory of a henselian valued field of characteristic (0,0). In this talk, I will discuss some further theorems on henselian valued fields which give conditions on the value group and residue field for the isomorphism type of the field itself to be fixed. This is joint work with Clifton Ealy, Jana Marikova and Pierre Simon.

Wednesday, 22 November 2017, 9:00AM -- M3-3127
Seminar -- Statistics & Actuarial Science
Speaker: Yang Ni, Rice University
Title: "Integrative Reciprocal Graphical Models with Heterogeneous Samples"
Remarks: Refreshments will be provided
Abstract: In this talk, I will introduce novel hierarchical reciprocal graphical models to infer gene networks by integrating genomic data across platforms and across diseases. The proposed model takes into account tumor heterogeneity. In the case of data that can be naturally divided into known groups, we propose to connect graphs by introducing a hierarchical prior across group-specific graphs, including a correlation on edge strengths across graphs. Thresholding priors are applied to induce sparsity of the estimated networks. In the case of unknown groups, we cluster subjects into subpopulations and jointly estimate cluster-specific gene networks, again using similar hierarchical priors across clusters. Two applications with multiplatform genomic data for multiple cancers will be presented to illustrate the utility of our model. I will also briefly discuss my other work and future directions.

Wednesday, 22 November 2017, 10:00AM -- DC 2310 true
Scientific Computation Group PhD Defence -- Computer Science
Speaker: Parsiad Azimzadeh, PhD candidate, David R. Cheriton School of Computer Science
Title: "Impulse Control in Finance: Numerical Methods and Viscosity Solutions"
Abstract: The goal of this thesis is to provide efficient and provably convergent numerical methods for solving partial differential equations (PDEs) coming from impulse control problems motivated by finance. Impulses, which are controlled jumps in a stochastic process, are used to model realistic features in financial problems that cannot be captured by ordinary stochastic controls. In this thesis, we consider two distinct cases of impulse control: one in which impulses can occur at any time and one in which they occur only at “fixed” (i.e., nonrandom and noncontrollable) times.

The first case is used to model features in finance such as fixed transaction costs, liquidity risk, execution delay, etc. In this case, the corresponding PDEs are Hamilton-Jacobi-Bellman quasi-variational inequalities (HJBQVIs). Other than in certain special cases, the numerical schemes that come from the discretization of HJBQVIs take the form of complicated nonlinear matrix equations also known as Bellman problems. We prove that a policy iteration algorithm can be used to compute their solutions. In order to do so, we employ the theory of weakly chained diagonally dominant (w.c.d.d.) matrices. As a by-product of our analysis, we obtain some new results regarding the relationship between w.c.d.d. matrices and M-matrices and a particular family of Markov decision processes, which can be thought of as impulse control problems on a discrete state space. Since HJBQVIs are nonlocal PDEs, we are unable to directly use the seminal result of Barles and Souganidis (concerning the convergence of monotone, stable, and consistent numerical schemes to the viscosity solution) to prove the convergence of our schemes. We address this issue by extending the work of Barles and Souganidis to nonlocal PDEs. We apply our schemes to compute the solutions of various classical problems from finance concerning optimal control of the exchange rate, optimal consumption with fixed and proportional transaction costs, and guaranteed minimum withdrawal benefits in variable annuities.

The second case of impulse control, involving impulses occurring at fixed times, is frequently used in pricing and hedging insurance contracts. In this case, the impulses correspond to regular anniversaries (e.g., monthly, yearly, etc.) at which the holder of the contract can perform certain actions (e.g., lapse the contract). The corresponding pricing equations are a sequence of linear PDEs coupled by nonlinear constraints corresponding to the impulses. For these problems, our focus is on speeding up the computation associated with the nonlinear constraints by means of a control reduction. We apply our results to price guaranteed lifelong withdrawal benefits in variable annuities.

Wednesday, 22 November 2017, 11:00AM -- DC 2314 true
Data Systems Group Master's Thesis Presentation -- Computer Science
Speaker: Yan Zhang, David R. Cheriton School of Computer Science
Title: "Efficient Structure-aware OLAP Query Processing over Large Property Graphs"
Abstract: Property graph model is a semantically rich model for real-world applications that represent their data as graphs, e.g., communication networks, social networks, financial transaction networks. On-Line Analytical Processing (OLAP) provides an important tool for data analysis by allowing users to perform data aggregation through different combinations of dimensions. For example, given a Q&A forum dataset, in order to study if there is a correlation between a poster's age and his or her post quality, one may ask what is the average age of users grouped by the post score. Another example is that, in the field of music industry, it may be interesting to ask what total sales of records are with respect to different music companies and years so as to conduct a market activity analysis.

Surprisingly, current graph databases do not efficiently support OLAP aggregation queries. In most cases, such queries are transformed to a sequence of join operations, and the system computes everything from scratch. For example, Neo4j, a state-of-art graph database system, processes each OLAP query in two steps. First, it expands the nodes and edges that satisfy the given query constraint. Then it performs the aggregation over all the valid substructures returned from the first step. However, in data warehousing workloads, it is common to have repeated queries from time to time. Computing everything from scratch would be highly inefficient.

Materialization and view maintenance techniques developed in traditional RDBMS have proved to be efficient for processing OLAP workloads. Following the generic materialization methodology, in this thesis we develop a structure-aware cuboid caching solution to efficiently support OLAP aggregation queries over property graphs. The essential idea is to precompute and materialize some views based on statistics of history workload, such that future query processing can be accelerated.

We implement a prototype system on top of Neo4j. Empirical studies over real-world property graphs show that, with a reasonable space cost constraint, our solution on average achieves 15–30x speedup over native Neo4j in time efficiency.

Wednesday, 22 November 2017, 2:30PM -- DC 1304
Algorithms and Complexity Group Seminar -- Computer Science
Speaker: Vedat Levi Alev, David R. Cheriton School of Computer Science
Title: "Graph Clustering Using Effective Resistance"
Abstract: We show a new connection between graph expansion and effective resistance distance — the effective resistance between two vertices when we interpret the graph as an electrical network — by showing that in a graph where every set exhibits a mild expansion property, the effective resistance between every pair of vertices is small. We use this connection to design an efficient algorithm to partition a graph into components with small effective resistance diameters. In particular, we show that it is always possible to delete a constant fraction of the edges of a graph, so that each remaining component is an "electrical expander" — a graph where the resistance distance between any two vertices is smallest possible.

No background will be assumed from the audience. We will start the talk by surveying the known results about effective resistance, and we will explain the motivation of the decomposition by comparing it to the well-known low diameter graph decomposition and expander decomposition.

Joint work with Nima Anari, Lap Chi Lau and Shayan Oveis Gharan

Wednesday, 22 November 2017, 4:00PM -- MC 5479
Continuous Optimization Seminar -- Combinatorics and Optimization
Speaker: Henry Wolkowicz, University of Waterloo
Title: "Alternating Direction Method of Multipliers for the SDP Relaxation of the Quadratic Assignment Problem"
Abstract: The semidefinite programming (SDP) relaxation has proven to be extremely strong for many hard discrete optimization problems. This is in particular true for the quadratic assignment problem (QAP), arguably one of the hardest NP-hard discrete optimization problems. There are several difficulties that arise in efficiently solving the SDP relaxation, e.g., increased dimension; inefficiency of the current primal-dual interior point solvers in terms of both time and accuracy; and difficulty and high expense in adding cutting plane constraints. We propose using the alternating direction method of multipliers (ADMM) to solve the SDP relaxation. This first order approach allows for inexpensive iterations, a method of cheaply obtaining low rank solutions, as well a trivial way of adding cutting plane inequalities. When compared to current approaches and current best available bounds we obtain remarkable robustness, efficiency and improved bounds.

Wednesday, 22 November 2017, 4:30PM -- MC 5501
Seminar -- Pure Mathematics
Speaker: Mehdi Karimi, Department of Combinatorics & Optimization, University of Waterloo
Title: "Joint Graduate Student Colloquium --- Sum-of-Squares Proofs in Optimization"
Abstract: The old concept of sum-of-squares found its way into optimization and even machine learning. I will talk about this quickly evolving research area known as convex algebraic geometry.

Wednesday, 22 November 2017, 7:30PM -- St. Jerome's University Vanstone Lecture Hall
Bridges Lecture Lecture -- Faculty of Mathematics
Speaker: Lucia Turin and Saskia Wilson-Brown, Alexander Fleming Institute and Institute for Art and Olfaction
Title: "Perfumery: the art and science of smell"
Remarks: Complimentary parking - accessible - refreshments served following the lecture.
Abstract: What, exactly, is fragrance? How might we discuss and theorize the sense of smell? Luca Turin and Saskia Wilson-Brown confront these surprisingly thorny questions and argue that fragrance is an autonomous art which must be dealt with on its own terms, a message in a bottle. As Igor Stravinsky said of music, fragrance may be "by its very nature, essentially powerless to express anything at all". Wilson-Brown’s fragrance awards have shown that there is the possibility for a blind consensus as to what makes a fragrance good or bad. Turin, in his research and writing, has been trying to figure out what that elusive thing may be.

Thursday, 23 November 2017, 1:30PM -- MC 6486
Special Seminar -- Combinatorics and Optimization
Speaker: Markus Blumenstock, University of Mainz, Germany
Title: "Orientations, Pseudoforests, Flows, and the Densest Subgraph"
Abstract: Given an undirected graph, consider the problem of nding an orientation such that the max- imum indegree is minimized. The Gabow-Westermann algorithm can solve it by exploiting the matroid structure of pseudoforests. I will show that its runtime can be improved to $\mathcal{O}(|E|^{1.5} \sqrt{\log \log |V|})$ by using Kowalik's approximation scheme, and better bounds can be given under certain conditions. In the process, we shall see and exploit the problem's relationship to the densest subgraph problem. I will then discuss some open questions, most notably whether an approximation ratio of less than 2 can be obtained in linear time. I will demonstrate two minor results in this direction: a small modifi cation of Kowalik's scheme yields a (1+ε)-approximation in time $\mathcal{O}(|E|\log |V|)$ for every fixed ε>0, and the 2-approximation algorithm of Asahiro et al. can be implemented in linear time.

Thursday, 23 November 2017, 1:30PM -- MC 5501
Number Theory Seminar Seminar -- Pure Mathematics
Speaker: Divyum Sharma, Department of Pure Mathematics, University of Waterloo
Title: "Joint distribution of the base-$q$ and Ostrowski digital sums"
Abstract: In 1922, A. Ostrowski introduced a numeration system based on the denominators of the convergents in the continued fraction expansion of a fixed irrational number $\alpha$. Coquet, Rhin and Toffin studied the joint distribution in residue classes of the base-$q$ sum-of-digits function $S_q$ and the Ostrowski sum-of-digits function $S_{\alpha}$. They gave certain sufficient conditions for the set \[ \{n\in\mathbb{N}: S_{q}(n)\equiv a_1\pmod{m_1},\ S_{\alpha}(n)\equiv a_2\pmod{m_2}\} \] to have asymptotic density $1/m_1m_2$. In this talk, we present a quantitative version of their result when \[ \alpha=[0;\overline{1,m}],\ m\geq 2. \]

Thursday, 23 November 2017, 3:30PM -- MC 5479
Graphs and Matroids Seminar Seminar -- Combinatorics and Optimization
Speaker: Peter Nelson, University of Waterloo
Title: "Ramsey theory for biased graphs"
Abstract: We discuss the unavoidable subgraphs of biased graphs whose underlying graph is a clique.

Friday, 24 November 2017, 1:30PM -- DC 1304
ISS4E Seminar -- Computer Science
Speaker: Côme Carquex, Department of Electrical and Computer Engineering, University of Waterloo
Title: "State Estimation in Power Distribution Systems and its Application to Electricity Theft Detection"
Abstract: State estimation in power distribution systems is a key component for increased reliability and optimal system performance. Well understood in transmission systems, state estimation is now an area of active research in distribution networks. While several snapshot-based approaches have been used to solve this problem, few solutions have been proposed in a dynamic framework.

In this thesis, a Past-Aware State Estimation (PASE) method is proposed for distribution systems that takes previous estimates into account to improve the accuracy of the current one, using an Ensemble Kalman Filter. Fewer phasor measurements units (PMU) are needed to achieve the same estimation error target than snapshot-based methods. Contrary to current methods, the proposed solution does not embed power flow equations into the estimator. A theoretical formulation is presented to compute a priori the advantages of the proposed method vis-a-vis the state-of-the-art. The proposed approach is validated considering the 33-bus distribution system and using power consumption traces from real households.

State estimation is then applied to the problem of electricity theft detection. A method taking into account measurements across several time-steps is presented. The proposed method achieves better theft detection rates and lower false positive levels than currents state of the art methods. The limitations of voltage measurements for theft detection are also underlined. The proposed method is validated using the 33-bus distribution system.

Friday, 24 November 2017, 2:00PM -- M3-3127
Seminar -- Statistics & Actuarial Science
Speaker: Cosimo-Andrea Munari, University of Zurich
Title: "Comonotonic risk measures in a world without risk-free assets"
Remarks: Refreshments will be provided
Abstract: We focus on comonotonic risk measures from the point of view of the primitives of the theory as initially laid down by Artzner et al. (1999): acceptance sets and eligible assets. We show that comonotonicity cannot be characterized by the properties of the acceptance set alone and heavily depends on the choice of the eligible asset. In fact, in many important cases, comonotonicity is only compatible with risk-free eligible assets. These findings seem to question the assumption of comonotonicity in a world of ``discounted'' capital positions and call for a renewed assessment of the meaning and the role of comonotonicity within a capital adequacy framework. Time permitting, we will also discuss some implications for insurance pricing.

Friday, 24 November 2017, 2:30PM -- MC 5403
Geometry & Topology Seminar Seminar -- Pure Mathematics
Speaker: Xinliang An, University of Toronto
Title: "On Singularity Formation in General Relativity"
Abstract: In the process of gravitational collapse, singularities may form, which are either covered by trapped surfaces (black holes) or visible to faraway observers (naked singularities). In this talk, with three different approaches coming from hyperbolic PDE, quasilinear elliptic PDE and dynamical system, I will provide answers for four physical questions: i) Can “black holes” form dynamically in vacuum? ii) To form a “black hole”, what is the least size of initial data? iii) Can we find the boundary of a “black hole” region? Can we show that a “black hole region” is emerging from a point? iv) For Einstein vacuum equations, could singularities other than black hole type form in gravitational collapse?

Friday, 24 November 2017, 3:30PM -- MC 5501
Tutte Colloquium Seminar -- Combinatorics and Optimization
Speaker: Joseph Cheriyan, University of Waterloo
Title: "Nash-Williams"
Abstract: Crispin Nash-Williams was one of the founding professors of C&O. The talk will cover a small sample of his mathematical work,and also his association with C&O.

Friday, 24 November 2017, 3:30PM -- MC 5417
Analysis Seminar Seminar -- Pure Mathematics
Speaker: Arthur Mehta, Department of Pure Mathematics, University of Waterloo
Title: "Chromatic numbers and a Lovász type inequality for non-commutative graphs"
Abstract: Non-commutative graph theory is an operator space generalization of graph theory. Well known graph parameters such as the independence number and Lovász theta function were first generalized to this setting by Duan, Severini, and Winter. In this talk we will review some of the motivations for generalising classical graph parameters using operator systems. We look at several different attempts to generalize the chromatic number in a meaningful way.

We discuss a non-commutative graph complement that allows for a new generalisation of the famous Lovász inequality.

...... WebNotice