Faculty of Mathematics, University of Waterloo

WebNotice Postings: 30-Nov-2015 through 06-Dec-2015

Postings for all Departments

Monday, 30 November 2015, 2:30PM -- QNC 0101
Colloquium -- Institute for Quantum Computing
Speaker: Karsten Flensberg, Niels Bohr Institute
Title: "Towards demonstration of Majorana-based topological qubits"
Abstract: The first part of the talk presents recent progress in the search for condensed matter systems hosting Majorana bound state in semiconductor-superconductor nanowire-based heterostructures. In the second part a proposal for the next steps towards manipulation of quantum information stored in topological qubits is presented. The proposal uses a scheme for preparation, manipulation, and readout of Majorana zero modes in mesoscopic wires and it is based on tools commonly used in quantum-dot experiments. The first goal would be to detection of the so-called fusion rules of non-Abelian anyons.

Monday, 30 November 2015, 4:15PM -- MC 6486
Seminar -- Combinatorics and Optimization
Speaker: Fernando Afonso, Federal University of Itajuba
Title: "A branch-and-cut-and-price algorithm for the pollution routing problem"
Abstract: A classical combinatorial optimization problem is the Vehicle Routing Problem with Time-windows (VRPTW). In such problem, a fleet of identical vehicles must visit customers to deliver goods such that the total amount of delivered goods is not more than the truck's capacity and each customer is served within its pre-specified time-window. The aim is to minimize the cost of visiting all customers exactly once.The Pollution Routing Problem (PRP) is a variant of the VRPTW where in addition to the routes, the speeds with which the vehicle will travel can also be determined. The main motivation in the PRP is that speeds will affect the amount of pollution that is generated. In fact, several models have been proposed to translate speeds into greenhouse gas emissions and further into dollar amounts. Using those models, the goal of the PRP then is to minimize the total dollar amount as a (nonlinear) function of the speeds and the routes. The goal of this talk is to introduce a Branch-and-cut-and-price algorithm for the PRP. We propose a dynamic programming algorithm to price out negative reduced cost routes that derives novel dominance rules in order to prune out unpromising labels and perform faster. Extensive computational experiments are conducted to assess the performance of the proposed algorithm.

For more information about our reading group, please visit our webpage http://www.math.uwaterloo.ca/~deolivei/reading.htm

Tuesday, 1 December 2015, 10:30AM -- MC 6486
Matroid Theory Seminar Seminar -- Combinatorics and Optimization
Speaker: Peter Nelson, University of Waterloo
Title: "Matroids with a spanning clique"
Abstract: I will discuss a recent result on the structure of matroids that are spanned by the cycle matroid of a complete graph, and also put the result in the wider context of matroid structure theory for minor-closed classes.

Wednesday, 2 December 2015, 4:30AM - ** Time Change ** - now at 3:30PM
** See updated entry for additional event information **
Speaker: George Labahn, David R. Cheriton School of Computer Science
Title: "Experiments in Developing Pen Math Systems"

Wednesday, 2 December 2015, 12:30PM -- DC 2310
Algorithms and Complexity Group PhD Seminar -- Computer Science
Speaker: Hicham El-Zein, David R. Cheriton School of Computer Science
Title: "On the Succinct Representation of Unlabeled Permutations"
Abstract: We investigate the problem of succinctly representing an arbitrary unlabeled permutation, so that power queries can be computed quickly. -Labeling schemes where we assign labels to elements and the query is to be answered by just examining the labels of the queried elements: we show that a label space of: sum (i=1 to n) of (floor(n/i).i) is necessary and sufficient. In other words, 2lg(n) bits of space are necessary and sufficient for representing each of the labels. -Succinct data structures for the problem where we assign labels to the n elements from the label set {1,...,cn} where c >= 1: we show that O(n^(1/2)) bits are necessary and sufficient to represent the permutation. Moreover, we support queries in such a structure in O(1) time in the standard word-RAM model. -Succinct data structures for the problem where we assign labels to the n elements from the label set {1,...,cn^1+epsilon} where c is a constant and 0 < epsilon < 1: we show that O(n^(1-epsilon)/2) bits are necessary and sufficient to represent the permutation. We can also support queries in such a structure in O(1) time in the standard word-RAM model.

Wednesday, 2 December 2015, 2:00PM -- M3-4206
Geometry Working Seminar -- Pure Mathematics
Speaker: Raymond Cheng, Department of Pure Mathematics University of Waterloo
Title: "“Variations on a Theme of Hodge, Variation III: Periods, Infinitesimally”"
Remarks: **Please note Room and Time**
Abstract: We have endured a month of difficult study, and fatigued as one may be, time has come to rejoice: this abstract theory in hand may now be used to see geometry. Curves, as we have seen, are essentially determined by this theory. It turns out that (generic) hypersurfaces, too, are likewise determined. Our goal here is to codify the example of curves and see how and in what way that extends to hypersurfaces. If we have a few bars left, period maps will receive an encore.

Wednesday, 2 December 2015, 2:00PM -- DC 1302
Cryptography, Security, and Privacy (CrySP) Group Lecture -- Computer Science
Speaker: Matthew Wright, University of Texas at Arlington
Title: "Teaching Users Random System-Assigned Passwords"
Abstract: Today, users are being asked to perform a complex and difficult task--composing a secure and memorable password--with incomplete and sometimes incorrect information about what makes passwords secure, what makes them memorable, and how to memorize this specially crafted information. And the results aren't pretty: many user-selected passwords are easy to guess, despite strength requirements that mostly just make passwords harder to remember, and many people reuse passwords even for important accounts. We propose the use of random system-assigned passwords, which provide guarantees on guessing resistance. Unfortunately, such passwords are hard to remember. In this talk, I will discuss two approaches that we have explored for making them more memorable: CuedR and the Memory Palace. In CuedR, we provide the user with graphical, verbal, and spatial cues at both registration and login to recognize a set of system-assigned keywords. The login success rate after one week in one of our studies (N=37) was 100%. The Memory Palace is a technique used by "memory champions" in which the user links a sequence of objects with a sequence of rooms in a house. We generate and show users a Memory Palace video that teaches users their random password. The login success rate was somewhat lower than for CuedR (86%), but the technique offers fast login times and shows promise for recall of 56-bit password strings.

Bio: Matthew Wright is an associate professor at the University of Texas at Arlington. He graduated with his Ph.D from the Department of Computer Science at the University of Massachusetts in May 2005, where he earned his M.S. in 2002. His dissertation work addresses the robustness of anonymous communications. His other interests include usable authentication systems and secure and sybil-resistant P2P systems. Previously, he earned his B.S. degree in Computer Science at Harvey Mudd College. He is a recipient of the NSF CAREER Award and the Outstanding Paper Award at NDSS 2002.

Wednesday, 2 December 2015, 2:30PM -- MC 5479
Fractal Geometry Seminar -- Pure Mathematics
Speaker: Erik Maki, University of Waterloo
Title: "“Iterated Function Systems and the Inverse Problem”"
Remarks: **Please Note Room**
Abstract: We introduce iterated function systems, a subset of discrete dynamical systems. A few examples of self similar sets generated by such systems and motivation for the inverse problem of approximation are given. We show some work towards a practical solution of the inverse problem, speci cally, approximation by moment-matching. Finally, we develop an approach involving iterated function systems with probabilities and place dependent probabilities.

Wednesday, 2 December 2015, 3:30PM -- DC 1301 true
Computer Science Colloquium -- Computer Science
Speaker: George Labahn, David R. Cheriton School of Computer Science
Title: "Experiments in Developing Pen Math Systems"
Abstract: In this talk we give details into our development of the MathBrush Pen-Math system. MathBrush is a system for doing mathematics on pen based devices. Initially developed for TabletPCs the system now runs on Surface Pro and iPad devices connecting to both Maple and Sage for doing their mathematical manipulations. We discuss the algorithms developed for recognizing handwritten mathematics along with the various trade-offs encountered while designing interfaces for doing math on pen-based devices.

About the Cheriton School of Computer Science Colloquium Series: The SCS Colloquium Series hosts lectures aimed at a broad Computer Science audience of graduate students, faculty, and anyone interested in a great talk by our leading researchers. The goal is to foster discussion and collaboration around active topics of research in the School.

Wednesday, 2 December 2015, 3:30PM -- MC 6486
Algebraic Graph Theory Seminar -- Combinatorics and Optimization
Speaker: Krystal Guo, University of Waterloo
Title: "Generalized quadrangles V: GQs and quantum walks"
Abstract: We will give another classical construction for generalized quadrangles. We will then explain a connection between quantum walks and generalized quadrangles.

Wednesday, 2 December 2015, 3:30PM -- MC 5479
Computability Learning Seminar -- Pure Mathematics
Speaker: Mohammad Mahmoud, Department of Pure Mathematics University of Waterloo
Title: "“Schnorr Randomness”"
Remarks: **Please Note Room**
Abstract: We will show that the notion of Schnorr randomness is consistent with intuition and leads to the desired statistical properties of random sets. Also we will prove the nice facts we have stated about the Schnorr test.

Thursday, 3 December 2015, 3:00PM -- DC 1331
Symbolic Computation Group Seminar -- Computer Science
Speaker: Simone Naldi, University of Toulouse, France
Title: "Exact algorithms for semidefinite programming"
Abstract: Semidefinite programming (SDP) is the natural extension of linear programming to the convex cone of positive semidefinite matrices. It consists in minimizing a linear function over the convex set, called spectrahedron, defined by a linear matrix inequality. While a numerical solution of a semidefinite program can be computed efficiently by interior-point algorithms, neither efficient exact algorithms for SDP are available, nor a complete understanding of its theoretical complexity has been achieved. I will present some recent result and some work in progress.

This is based on joint work with Didier Henrion and Mohab Safey El Din

Thursday, 3 December 2015, 4:00PM -- M3 3127
Seminar -- Statistics & Actuarial Science
Speaker: Jon Rao, Carleton University
Title: "Inferential Issues in the Presence of Imputation for Missing Survey Data"
Abstract: Item nonresponse occurs frequently in sample surveys collecting data on many items. It is customarily handled by some form of imputation to fill in the missing item values. However, imputation values are often treated as if there were true values in making inference form the imputed data sets. Imputed point estimators are often valid but the “naïve” variance estimates, treating the imputed values as true values, can lead to serious underestimation of the true variance even for large samples because the additional variability due to estimating the missing values is not taken into account. Impressive advances have been made on making efficient and asymptotically valid inferences from singly imputed data sets. The main purpose of this talk is to present an overview and appraisal of methods for variance estimation under single imputation. Fractional imputation and multiple imputation both use multiple imputed values for a missing item and reduce imputation variance relative to single imputation using only one randomly imputed value. Variance estimation under fractional and multiple imputation will also presented. Finally, the construction of reliable bootstrap confidence intervals under imputation will be examined.

This talk is sponsored by the CANSSI CRT Project “Statistical Inference for Complex Surveys with Missing Observations”.

Thursday, 3 December 2015, 4:00PM -- DC 1331
Symbolic Computation Group Seminar -- Computer Science
Speaker: Suzy S. Maddah, University of Limoges, France
Title: "Formal Solutions of a certain class of Pfaffian Systems"
Abstract: Pfaffian systems arise in many applications, including the studies of aerospace, celestial mechanics, and statistics. So far, the most important systems for applications are those with the so called normal crossings. The existence of a fundamental matrix of formal solutions and its general form were established in the seventies and eighties notably by Charri?ere, G?erard, Levelt, and van den Essen. The proofs, however, are not constructive. In this talk, we present an algorithm for constructing a fundamental matrix of formal solutions of such systems.

This is a joint work with Moulay A. Barkatou and Maximilian Jaroschek. 1

Friday, 4 December 2015, 3:30PM -- MC 5501
Tutte Colloquium Colloquium -- Combinatorics and Optimization
Speaker: Dave Touchette, University of Waterloo, IQC
Title: "The quantum information cost of forgetting classical information"
Abstract: In the basic communication complexity setup, Alice and Bob are given classical inputs x and y, respectively, and they want to compute a bipartite function f(x, y) while minimizing the amount of communication they must exchange. In the closely related information complexity setting, we are instead interested in the least amount of information that Alice and Bob must leak to each other about their respective inputs in order to compute the function f(x, y). This information complexity paradigm has proven to be a powerful tool for obtaining communication complexity lower bounds in both the classical and quantum settings.

In quantum protocols, it is possible for Alice and Bob to forget information they have learned about each other’s classical input. In this talk, we explore the many consequences of this ability of quantum protocols to forget information for defining a quantum notion of information cost.

...... WebNotice