Faculty of Mathematics, University of Waterloo

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

Postings for all Departments

Monday, 20 March 2017, 10:30AM -- DC 1304
Seminar -- Computer Science
Speaker: Ali Mashtizadeh, PhD candidate, Stanford University
Title: "Systems and Tools for Reliable Software: Replication, Reproducibility, and Security"
Remarks: SACA Seminar
Abstract: The past decade has seen a rapid acceleration in the development of new and transformative applications in many areas including transportation, medicine, finance, and communication. Most of these applications are made possible by the increasing diversity and scale of hardware and software systems.

While this brings unprecedented opportunity, it also increases the probability of failures and the difficulty of diagnosing them. Increased scale and transience has also made management increasingly challenging. Devices can come and go for a variety of reasons including mobility, failure and recovery, and scaling capacity to meet demand.

In this talk, I will be presenting several systems that I built to address the resulting challenges to reliability, management, and security.

Ori is a reliable distributed file system for devices at the network edge. Ori automates many of the tasks of storage reliability and recovery through replication, taking advantage of fast LANs and low cost local storage in edge networks.

Castor is record/replay system for multi-core applications with predictable and consistently low overheads. This makes it practical to leave record/replay on in production systems, to reproduce difficult bugs when they occur, and to support recovering from hardware failures through fault tolerance.

Cryptographic CFI (CCFI) is a dynamic approach to control flow integrity. Unlike previous CFI systems that rely purely on static analysis, CCFI can classify pointers based on dynamic and runtime characteristics. This limits the attacks to only actively used code paths, resulting in a substantially smaller attack surface.

• • • • •

Bio: Ali is currently completing his PhD at Stanford University where he is advised by Prof. David Mazičres. His work focuses on improving reliability, ease of management and security in operating systems and distributed systems. Previously, he was a Staff Engineer at VMware, Inc. where he was the technical lead for the live migration products. Ali received an M.Eng. in electrical engineering and computer science and a B.S. in electrical engineering from the Massachusetts Institute of Technology.

Monday, 20 March 2017, 11:30AM -- MC 5413
Seminar -- Pure Mathematics
Speaker: Levon Haykazyan, Department of Pure Mathematics, University of Waterloo
Title: "NIP, Keisler Measures and Combinatorics"
Abstract: We continue with Starchenkoąs Bourbaki paper, beginning now to look at the application to combinatorics.

Monday, 20 March 2017, 11:30AM -- MC 5403
Seminar -- Pure Mathematics
Speaker: Cam Marcott, Department of Combinatorics & Optimization, University of Waterloo
Title: "."
Abstract: We define matroidal flips, which will be the primary inductive tool for proving the Hodge-Riemann relations and the Hard Lefschetz Theorem for matroids. Time permitting, we will begin to prove these things.

Monday, 20 March 2017, 4:00PM -- MC 5479
Graduate Student Seminar Seminar -- Combinatorics and Optimization
Speaker: Speaker #1: Shenghao Yang, Speaker #2: Sophia Park, Speaker #3: Priya Soundararajan, University of Waterloo
Title: "Speaker #1: Cutting Planes for Mixed Integer Programming, Speaker #2: The Dinitz Problem, Speaker #3: Whether factoring reduces the RSA problem or not."
Abstract: Speaker #1: Polyhedral approach and cutting plane methods have proven successful in practice in solving integer and mixed integer optimization problems. I will first talk about an interesting classical example where a cutting plane algorithm based on split cuts does not converge finitely. Then we will see how a two-row cut – a valid inequality that is derived from two rows of the optimal simplex tableau of LP relaxation – helps to yield immediate termination. This will motivate us to look at the ideas of multi-row cut, an area of research that attracts much attention in the recent 10 years.

Speaker #2: Consider $n^2$ cells arranged in an $(n \times n)$-square, and let $(i,j)$ denote the cell in row $i$ and column $j$. Suppose that for every cell $(i,j)$ we are given a set $C(i,j)$ of $n$ colours. Is it then possible to colour the whole array by picking for each cell $(i,j)$ a colour from its set $C(i,j)$ such that the colours in each row and each column are distinct? This colouring problem was first raised by Jeff Dinitz in 1978 and went unsolved for fifteen years. We will discuss some previous results and then show how they imply a delightfully simple solution to the Dinitz problem.

Speaker #3: RSA is one of the first practical public-key cryptosystems designed, and is widely used to secure communications. It can be easily shown that one can solve the RSA problem, given an oracle for factoring, i.e RSA reduces to factoring. An important question regarding the security of RSA is whether factoring reduces to the RSA problem or not, and this remains open. A result published by Boneh & Venkatesan in 1998 hints that RSA may not be equivalent to factoring. There are results in the literature that seem to hint otherwise. In this talk, we will present a brief overview of the problem, discuss the intuition behind the result in the above paper, as well as understand how the different results relate to each other.

Monday, 20 March 2017, 4:00PM -- MC 5501
Colloquium -- Pure Mathematics
Speaker: Jesse Peterson, Vanderbilt University
Title: "Connes’ character rigidity conjecture for lattices in higher rank groups"
Remarks: Refreshments will be served in MC 5403 at 3:30 pm. All are welcome!
Abstract: A character on a group is a class function of positive type. For finite groups, the classification of characters is closely related to the representation theory of the group and plays a key role in the classification of finite simple groups. Based on the rigidity results of Mostow, Margulis, and Zimmer, it was conjectured by Connes that for lattices in higher rank simple Lie groups, the space of characters should be completely determined by their finite dimensional representations. In this talk, I will discuss the solution to this conjecture, and I will discuss its relationship to ergodic theory, invariant random subgroups, and von Neumann algebras.

Tuesday, 21 March 2017, 10:30AM -- DC 2585 true
Bioinformatics Group Seminar -- Computer Science
Speaker: Hosna Jabbari, Ingenuity Lab, University of Alberta
Title: "Computational Informatics for Improving Efficacy of Gene Therapy"
Abstract: With the amount of genomic data produced every day, advances in medical sciences and development of new gene modification tools, a revolution in medicine is expected. Recent approval of the first gene therapies by FDA is a leap towards this revolution. Computational methods provide unique opportunities to realize this revolution by providing both an inexpensive framework (in terms of cost, time and safety) to explore the complex biological systems of diseases, and a reduced search space for treatment options. In this talk, I will describe an example of such framework for treatment of Duchenne muscular dystrophy through gene therapy, and highlight some of the challenges and future opportunities.

• • • • •

Bio: Dr. Hosna Jabbari is a postdoctoral fellow at the Ingenuity Lab, a multidisciplinary research laboratory at the University of Alberta. Her main research goal is to help diagnose and cure human diseases by developing novel diagnostics and therapeutics through research using techniques from (algorithmic) bioinformatics, data science and computational genomics. She obtained a PhD in 2015, in computer science – bioinformatics, from the University of British Columbia, advised by Anne Condon and supported by NSERC.

Tuesday, 21 March 2017, 3:00PM -- MC 5403
Seminar -- Pure Mathematics
Speaker: Jonny Stephenson, Department of Pure Mathematics, University of Waterloo
Title: "1-generic presentations and r.i.c.e. sets"
Abstract: We will conclude our study of 1-generic presentations by showing that there is a strong link between 1-genericity and r.i.c.e sets. In particular, we will see that if A is a 1-generic presentation, then the sets which are c.e. in D(A) are precisely those which are r.i.c.e.

Wednesday, 22 March 2017, 12:00PM -- DC 1304
Algorithms and Complexity Group Seminar -- Computer Science
Speaker: Tim Smith, David R. Cheriton School of Computer Science
Title: "Undecidability and Finite Automata"
Abstract: Using a novel rewriting problem, we show that two natural decision problems about finite automata are undecidable (i.e., recursively unsolvable). The problems involve cyclic shifts over a two-track input alphabet — i.e., an alphabet consisting of pairs of letters. One of the problems asks whether a finite automaton accepts any input of the form uv × vu, and the other asks about the restricted case in which v consists of repetitions of a single letter not in u.

In contrast, we prove that several related problems are decidable. We also apply one result to prove the undecidability of a problem about k-automatic sets of rational numbers.

Wednesday, 22 March 2017, 2:30PM - ** Date Change ** - now Monday, 3 April 2017, 2:30PM
** See updated entry for additional event information **
Speaker: Prof. Anita T. Layton, Duke University
Title: "Understanding Kidney Physiology: A Modeling Approach"

Wednesday, 22 March 2017, 4:00PM -- MC 5501
Colloquium -- Computational Mathematics
Speaker: David Correa, Assistant Professor, School of Architecture, University of Waterloo
Title: "Material Informed Computational Design in Architecture"
Remarks: Refreshments at 3:45pm
Abstract: No longer bound by the production line, designers, engineers and computer scientists have moved to the development of adaptive construction processes capable of autonomous sensing, simulation and response. The integration of computational design and simulation tools, in the form of customized software and hardware, has provided designers with new access to material properties resulting on unprecedented levels of performance complexity. This talk will present an overview of robotically enabled and digital fabrication projects developed at the Institute of Computational Design and Construction (ICD) in Germany.

David Correa is an Assistant Professor at the University of Waterloo and Doctoral Candidate at the Institute for Computational Design (ICD) at the University of Stuttgart. At the ICD, David initiated and lead the research field of Bio-inspired 3D Printed Programmable Material Systems. His Doctoral research investigates the reciprocal relationship between material design and fabrication from a multi-scalar perspective. With a focus on climate responsive materials for the built environment, the research integrates computational tools, simulation and digital fabrication with bio-inspired design strategies for material architectures. As a designer in architecture, product design and commercial digital media, David’s professional work engages multiple disciplines and environments – from dense urban settings to remote northern regions.

Wednesday, 22 March 2017, 4:00PM -- Math & Computer, Room 6486
Seminar -- Combinatorics and Optimization
Speaker: Charupriya Sharma, Dept. of Combinatorics & Optimization; University of Waterloo
Title: "Technology Diffusion on Spiders"
Abstract: In the rich literature on diffusion and cascade effects in social networks, a node’s actions are assumed to be influenced only by its neighbours. This highly-localized view of influence is not applicable in all contexts. The diffusion of technologies in communication networks is one important example; here, a node’s actions should also be influenced by remote nodes that it can communicate with. Motivated by such cascade effects arising in network technology upgrade processes in the Internet, Goldberg and Liu (2013) introduced the following technology diffusion problem. Given a graph, and a threshold function on all nodes, a vertex activates if it is adjacent to a connected component of active nodes of size at least its threshold value. The goal is to find a subset of nodes whose initial activation would trigger a cascade activating the entire graph. This talk will describe exact algorithms and polyhedral characterizations for both the seed minimization, and the influence maximization versions of the technology diffusion problem on spiders and cycles.

Joint work with Laura Sanita.

Thursday, 23 March 2017, 10:30AM -- DC 1304 true
Seminar -- Computer Science
Speaker: Carsten Eickhoff, Researcher and Lecturer, ETH Zurich, Switzerland
Title: "Clinical Text Understanding and Decision Support"
Abstract: Clinical research has never been more active and diverse than it is at this moment. Research efforts span national and cultural borders and broad online dissemination makes insights available at a global scale with ever decreasing latency. In the face of these developments, individual researchers and practitioners are confronted with a seemingly intractable amount of material (approximately 1 Million scholarly articles are newly published in the life sciences each year). While highly trained human experts excel at making precision diagnoses, coverage, especially for uncommon conditions could be greatly improved. In this talk, we will discuss a range of (deep) machine learning techniques that provide automatic clinical decision support on the basis of large-scale data collections. Concretely, I will present early and ongoing work on a) Patient-centric clinical literature retrieval, automatically identifying research papers, clinical trials and case reports that are relevant given the case at hand. b) Predictive assistants in post-operative care of cardiac surgery patients, that serve as early warning systems in case of undesirable and dangerous complications. c) Data-driven diagnosis of rare diseases that individually occur too infrequently to allow clinical specialists to establish the necessary routine and experience. To close, I will give a brief outlook on a wider range of future directions towards providing medical professionals with powerful aggregates of their large-scale clinical information resources. In this way, our work facilitates everyday medical practice as well as clinical research beyond their current, perceived limitations, leading to the development of new treatments, and, ultimately, improved patient well-being.

Bio: Carsten is a researcher and lecturer at ETH Zurich, Switzerland, specializing in clinical data science and information retrieval. He obtained his Ph.D. in computer science from the Technical University of Delft in the Netherlands and an M.Sc. in artificial intelligence from the University of Edinburgh in Scotland. He has authored more than 50 conference and journal articles on topics pertaining to automatic large-scale text processing and retrieval as well as information extraction from unstructured natural language resources.

Thursday, 23 March 2017, 12:30PM -- MC 5479
Seminar -- Pure Mathematics
Speaker: Nickolas Rollick, Department of Pure Mathematics, University of Waterloo
Title: "A quasi-separated talk"
Abstract: This week's talk will blur the lines between last week's discussion of projective schemes and our upcoming goal of discussing properties of schemes. So blurred, in fact, that the two are only quasi-separated! We start by formally defining projective and quasiprojective schemes over a ring, and we look at "closed subsets of projective space over a field". This segues nicely into a discussion of topological properties of schemes in general, when we prove that projective space over a field is irreducible. What follows is a gallery of observations about various types of schemes, with the apex being the introduction of quasi-separated schemes. We will characterize the so-called qcqs (quasi-compact and quasi-separated) schemes, and we will notice in particular that projective schemes over a ring are qcqs.

Thursday, 23 March 2017, 1:30PM -- M3 3103
Number Theory Seminar Seminar -- Pure Mathematics
Speaker: Roger Baker, Brigham Young University
Title: "Quadratics over the primes"
Abstract: Let ||...|| denote distance from the nearest integer. Let f be a quadratic polynomial with irrational leading coefficient. We give a new result on small values of ||f(p)|| for infinitely many primes p. One technique that is used involves a lemma of Birch and Davenport on a real number with many rational approximations, and I will try to explain the role of this lemma in the work.

Thursday, 23 March 2017, 2:00PM -- Math & Computer, Room 2009 true
Seminar -- Combinatorics and Optimization
Speaker: David Jao, University of Waterloo
Title: "Efficient Compression of SIDH Public Keys"
Abstract: Supersingular isogeny Diffie-Hellman (SIDH) is an attractive candidate for post-quantum key exchange, in large part due to its relatively small public key sizes. In this work we develop methods to reduce the size of public keys in isogeny-based cryptosystems by more than a factor of two, with performance cost comparable to that of a round of standalone SIDH key exchange, using a combination of techniques from the theory of elliptic curve descent, faster bilinear pairings, and windowed Pohlig-Hellman for discrete logarithms. Our results provide SIDH public keys of 330 bytes for the 128-bit quantum security level, far smaller than any other available alternative, and further strengthen the case for SIDH as a promising post-quantum primitive.

Joint work with Craig Costello, Patrick Longa, Micahel Naehrig, Joost Renes, and David Urbanik.

Thursday, 23 March 2017, 3:30PM -- DC 1302
Seminar -- Computer Science
Speaker: Daniel Alan Spielman, the Henry Ford II Professor of Computer Science, Mathematics, and Applied Mathematics, Yale University
Title: "The Laplacian Matrices of Graphs: Algorithms and Applications"
Abstract: The Laplacian matrices of graphs arise in many fields, including Machine Learning, Computer Vision, Optimization, Computational Science, and of course Network Analysis.  We will explain what these matrices are and why they appear in so many applications.

We then survey recent ideas that allow us to solve systems of linear equations in Laplacian matrices in nearly linear time, emphasizing the utility of graph sparsification---the approximation of a graph by a sparser one---and a recent algorithm of Kyng and Sachdeva that uses random sampling to accelerate Gaussian Elimination.

BIO:  Daniel Alan Spielman received his B.A. in Mathematics and Computer Science from Yale in 1992, and his Ph.D in Applied Mathematics from M.I.T. in 1995. He spent a year as a NSF Mathematical Sciences Postdoc in the Computer Science Department at U.C. Berkeley, and then taught in the Applied Mathematics Department at M.I.T. until 2005.  Since 2006, he has been a Professor at Yale University.  He is presently the Henry Ford II Professor of Computer Science, Mathematics, and Applied Mathematics.  

He has received many awards, including the 1995 ACM Doctoral Dissertation Award, the 2002 IEEE Information Theory Paper Award, the 2008 and 2015 Godel Prize, the 2009 Fulkerson Prize, the 2010 Nevanlinna Prize, the 2014 Polya Prize, an inaugural Simons Investigator Award, and a MacArthur Fellowship.  He is a Fellow of the Association for Computing Machinery and a member of the Connecticut Academy of Science and Engineering.  His main research interests include the design and analysis of algorithms, network science, machine learning, digital communications and scientific computing.

Thursday, 23 March 2017, 4:00PM -- Math & Computer, Room 5479 true
Seminar -- Combinatorics and Optimization
Speaker: Ahmad Abdi, Dept. of Combinatorics & Optimization, University of Waterloo
Title: "The Sums of Circuits Property"
Abstract: A binary matroid has the sums of circuits property if the natural cut condition implies the existence of a fractional packing of circuits, for any positive weight function defined on the edges. This beautiful notion was introduced in 1979 by Paul Seymour, who classified the binary matroids with this property in 1981.

This rich notion is the beating heart of many amazing results in the field of Packing and Covering as well as several widely open questions in the field. Just to name a few, the characterization of graphs with the circuit cover property, of $k$-flowing binary matroids for $k\ge 2$, and of binary matroids with the max-flow min-cut property are amazing results that hover around the sums of circuits property. The cycle double cover conjecture, the $1$-flowing conjecture as well as the $f$-flowing conjecture are some of the biggest open questions in the field that come from the sums of circuits property.

I will do a survey of these results, and finish off by discussing yet another line of research inspired by the sums of circuits property.

Friday, 24 March 2017, 1:30PM -- DC 2585
Symbolic Computation Group PhD Seminar -- Computer Science
Speaker: Joseph Haraldson, David R. Cheriton School of Computer Science
Title: "Computing a Nearest Singular Matrix Polynomial"
Abstract: Low rank approximation of matrix polynomials consists of approximating a given matrix whose entries consist of polynomials by another matrix of lower rank whose entries consist of polynomials.

An important application is investigating the kernel of a matrix polynomial. Kernel basis computation of matrix polynomials is an essential step in several computer algebra problems; however, in an approximate setting almost all matrix polynomials are generically of full rank. The appropriate question to ask is not if a given matrix polynomial is rank deficient, but instead how far away is a given matrix polynomial from one that is rank deficient.

In this talk we discuss the geometry of the solution space and techniques for computing a nearest singular matrix polynomial using local optimization techniques.

Friday, 24 March 2017, 2:30PM -- MC 5413
Geometry & Topology Seminar Seminar -- Pure Mathematics
Speaker: Charlotte Kirchoff-Lukat, University of Cambridge
Title: "Lagrangian branes with boundary in stable generalised complex manifolds"
Abstract: Generalised complex geometry interpolates between ordinary symplectic and complex manifolds. Stable generalised complex manifolds (first introduced by Cavalcanti, Gualtieri in 2015) carry a Poisson structure which is generically symplectic, but degenerates on a (real) codimension-2 submanifold. Half-dimensional generalised complex branes are distinguished submanifolds of generalised complex manifolds, and in a stable generalised complex manifold, they are generically Lagrangian. I will introduce a new type of generalised complex brane: Lagrangian branes with boundary. These branes do not intersect the degeneracy locus of the stable generalised complex structure transversely; instead the intersection is their boundary. This new type of generalised complex plane is thought to take the place of Lefschetz thimbles in the stable generalised complex analogue of Lefschetz fibrations, and would thus be needed to define their Fukaya category.

Friday, 24 March 2017, 3:30PM -- M3 3103
Seminar -- Pure Mathematics
Speaker: Diana Castaneda Santos, Department of Pure Mathematics, University of Waterloo
Title: "Affine and Projective Planes"
Abstract: As the basic ingredients of our discussion, we shall only require the notion of a set $\mathcal{P}$ of points, together with a collection $\mathcal{L}$ of subsets of $\mathcal{P}$, called lines, satisfying certain conditions. We will define and relate affine and projective planes and provide some numerical results in the finite case. We will show how a projective plane is constructed from a division ring and conclude that there exist finite projective planes of order $p^n$ for any prime $p$. Thanks to a result of Bruck-Ryser it is known that there are no projective planes of order $n$ if $n\equiv 1$ or $2$ mod $4$ and $n$ is not the sum of two squares. If time permits we will see another approach with Latin squares to find projective planes of order $n$.

Friday, 24 March 2017, 3:30PM -- MC 5417
Analysis Seminar Seminar -- Pure Mathematics
Speaker: Ali Kavruk, Virginia Commonwealth University
Title: "Christandl's Problem and Connes' Embedding Problem"
Abstract: In Quantum Information Theory Peres-Horodecki-Woronowicz's PPT (positive partial transpose) criterion is an effective method to identify separable states if the local dimensions are low ((2,2), (2,3) or (3,2)). M. Christandl then asks if bi-PPT cones can identify separable states on a quantum system with arbitrary local dimensions. Applicability in Quantum Entanglement we present general theory of symmetrization in the operator system category. We go through the stability properties of these functors under quotients, duality, tensor products, etc. We then express Christandl's Problem in this setting. We will see that this problem is connected with Connes' Embedding Problem and give various open problems which are implied by these two questions. This will be an introductory talk and accessible to grad students.

Friday, 24 March 2017, 3:30PM -- Math & Computer, Room 5501
Colloquium -- Combinatorics and Optimization
Speaker: Dr. Jochen Koenemann, Dept. of Combinatorics & Optimization, University of Waterloo
Title: "Improved Approximation for Tree Augmentation via Chvatal Gomory Cuts"
Abstract: In the weighted tree augmentation problem (WTAP) we are given a tree T in a graph G=(V,E). Edges in E\T are called links and carry a non-negative weight. The goal is to find a minimum-weight set L of links such that T+L is 2-edge-connected.

WTAP is a classical NP- and APX-hard network design problem (even when all links have weight 1; call this TAP). The best known approximation algorithm achieves a performance guarantee of 2 (due to Fredrickson & Jaja). Kortsarz and Nutov improved this to 3/2 in the special case of TAP. Very recently recently Adjashvili gave a 1.96-approximation for WTAP whenever link weights are bounded, and a 5/3-approximation for TAP.

We show how to improve the result of Adjashvili and obtain a 3/2-apx for both weighted and unweighted tree augmentation in the bounded link weight setting. The key ingredient is a strengthened linear programming formulation for WTAP.

Joint work with: M. Gross, S. Fiorini and L. Sanita

...... WebNotice