Faculty of Mathematics, University of Waterloo

WebNotice Postings: 27-Jun-2016 through 03-Jul-2016

Postings for all Departments


Monday, 27 June 2016, 10:30AM -- DC 1304
Artificial Intelligence Lab Seminar -- Computer Science
Speaker: Michael Wellman, University of Michigan
Title: "Putting the Agent in Agent-Based Modeling"
Abstract: Agent-based modeling (ABM) is a general approach to understanding social systems through simulation of interacting agents. Typical ABM studies adopt simple heuristic agent behaviors, both on the principle of avoiding an assumption of excess competence, and in order to facilitate experimentation and analysis. This runs counter to the goal of agent design in Artificial Intelligence, which seeks maximally capable agents and willingly accepts complexity in architecture, reasoning methods, and decision technique in pursuit of that end. I argue that ABM can be reconciled with sophistication in agent design, and suggest a methodology for principled selection of agent behaviors. Points are illustrated with examples from some of our recent work in decision cascades, credit networks, and financial trading.

Monday, 27 June 2016, 2:30PM -- QNC 0101
Colloquium -- Institute for Quantum Computing
Speaker: Robert Myers, Perimeter Institute
Title: "Information, Holography & Gravity"
Abstract: In science, new advances and insights often emerge from the confluence of different ideas coming from what appeared to be disconnected research areas. The theme of my talk will review an ongoing collision between the three topics listed in my title which has been generating interesting new insights about the nature of quantum gravity, as well as variety of other fields, such as condensed matter physics and quantum field theory.

Tuesday, 28 June 2016, 10:30AM -- DC 2310
Artificial Intelligence Lab Master's Thesis Presentation -- Computer Science
Speaker: Vijay Menon, David R. Cheriton School of Computer Science
Title: "Computational Aspects of Strategic Behavior in Elections with Top-Truncated Ballots"
Abstract: Understanding when and how computational complexity can be used to protect elections against different manipulative actions has been a highly active research area over the past two decades. Much of this literature, however, makes the assumption that the voters or agents specify a complete preference ordering over the set of candidates. There are many multiagent systems applications, and even real-world elections, where this assumption is not warranted, and this in turn raises a series of questions on the impact of partial voting on the complexity of manipulative actions. In this thesis, we focus on two of these questions. First, we address the question of how hard it is to manipulate elections when the agents specify only top-truncated ballots. Here, in particular, we look at the weighted manipulation problem---both constructive and destructive manipulation---when the voters are allowed to specify top-truncated ballots, and we provide general results for all scoring rules, for elimination versions of all scoring rules, for the plurality with runoff rule, for a family of election systems known as Copeland^{alpha}, and for the maximin protocol. Subsequently, we also look at the impact on complexity of manipulation when there is uncertainty about the non-manipulators' votes. The second question we address is the question on what the impact of top-truncated voting is on the complexity of manipulative actions in electorates with structured preference profiles. In particular, we consider electorates that are single-peaked or nearly single-peaked and we show how, for many voting protocols, allowing top-truncated voting reimposes the NP-hardness shields that normally vanish in such electorates.

Tuesday, 28 June 2016, 1:30PM -- QNC 0101
Seminar -- Institute for Quantum Computing
Speaker: Tom Stace, University of Queensland, Australia
Title: "Correlated decay in driven quantum systems"
Abstract: Gate defined quantum dots are "artificial atoms", with well defined energy levels. They interact strongly with microwave resonators, and with the solid-state environment in which they live. These systems can exhibit population inversion, single-atom masing and other phenomena familiar to the quantum optics community. The environment also produces higher-order correlated decay processes, which are typically not included in quantum-optical Lindblad master equations. I will describe how we systematically derive such correlated decay terms using Keldysh diagrammatic perturbation theory, leading to higher-order Lindblad master equations. These new terms are very general, and account for discrepancies between current theory and experiment.

Tuesday, 28 June 2016, 2:30PM -- Math & Computer, Room 6486
Combinatorial Optimization Seminar -- Combinatorics and Optimization
Speaker: Ray Liu, Combinatorics & Optimization and Institute for Quantum Computing
Title: "Quantum Walk based Algorithms"
Abstract: Quantum algorithms achieve speed-up in evaluating many functions that can never be achieved by classical ones; for instance, the famous Shor’s Algorithm and Grover’s Search. In recent years, quantum walk based algorithms were heavily studied. By adding a coin register, we can turn discrete-time random walk into discrete-time quantum walk, which in general achieves a quadratic speed-up. In this talk, we will see how we can evaluate functions by analyzing the spectrum of the quantum walk. No prior knowledge of quantum computing is assumed.

Tuesday, 28 June 2016, 2:30PM -- Math & Computer, Room 6486
Combinatorial Optimization Seminar -- Combinatorics and Optimization
Speaker: Xinrui Jia, Combinatorics & Optimization
Title: "Public Key Exchange using Semidirect Products"
Abstract: A recent paper by Delaram Kahrobaei and Vladimir Shpilrain describes a key exchange protocol using a semidirect product of groups/semigroups. We present the general protocol and the Diffie-Hellman key exchange as a special case of this protocol. When implemented with a non-commutative group/semigroup, this key exchange by Kahrobaei and Shpilrain can have advantages over Diffie-Hellman but care must be taken to avoid linear algebra attacks. Time permitting, we discuss the analysis of the security of the protocol under certain semigroups and our approach to finding new suitable semigroups. The authors suggest using a free nilpotent p-group to avoid these attacks.

Wednesday, 29 June 2016, 10:00AM -- M3-3103
Computability Learning Seminar -- Pure Mathematics
Speaker: Michael Deveau, Department of Pure Mathematics University of Waterloo
Title: "“The Golden Run Construction - Part 2”"
Remarks: **Please note room**
Abstract: Now that we have gained some conceptual understanding of the construction and have explored the new difficulty of showing that our set is low for K compared to the earlier con- structions, we now turn to describing the procedures P and Q that were identified last time. Formally describing their actions and verifying that they behave correctly and respect their goal and garbage quotas will take some time, and this will be our focus for the immediate future.

Wednesday, 29 June 2016, 1:30PM -- MC 5501
Special Presentation Lecture -- Pure Mathematics
Speaker: Luca Di Cerbo, ICTP - Trieste, Italy
Title: "Geometry Summer School - Lecture 1"
Abstract: The study of volumes in hyperbolic geometry, real & complex, is a classical topic in differential geometry which is beautifully interconnected with many other parts of mathematics such as geometric topology, algebraic geometry, group theory and even computational mathematics. In this first lecture, I will introduce this fascinating subject through the study of volumes of hyperbolic Riemann surfaces via the classical Gauss-Bonnet theorem. Then, I will give an overview of some modern works on hyperbolic 3-manifolds due to Thurston and his school. Finally, I will recall the necessary background for the study of volumes in higher dimensional complex hyperbolic geometry such as the Chern-Gauss-Bonnet theorem. The last part of this lecture is preparatory for the second lecture, which will be exclusively on complex hyperbolic geometry.

Thursday, 30 June 2016, 1:30PM -- MC 5501
Special Presentation Lecture -- Pure Mathematics
Speaker: Luca Di Cerbo, ICTP - Trieste, Italy
Title: "Geometry Summer School - Lecture 2"
Abstract: In this lecture, I will focus on the study of complex hyperbolic surfaces and their volume spectrum. Recall that a complex hyperbolic surface is a complete finite volume complex surface (a manifold of real dimension four) which admits a metric of negative constant holomorphic sectional curvature. In the compact case, a problem which has attracted considerable attention is the classification of all complex hyperbolic surfaces with minimal volume. This intriguing problem, originally proposed by Mumford in the 70's, has a long and rich history which I will briefly recall. The analogous problem in the non-compact finite volume case has an interesting history as well. In fact, Hirzebruch in the 80's constructed the first example of a non-compact complex hyperbolic surface with minimal volume. After reviewing Hirzebruch's example, I will construct a new example, recently discovered in collaboration with M. Stover, and address the classification problem of all such surfaces. Finally, I will explicitly construct a tower of examples which saturates the whole admissible volume spectrum of complex hyperbolic surfaces. This is again joint with M. Stover.

Thursday, 30 June 2016, 3:30PM -- MC 5417
Graph Theory Seminar -- Combinatorics and Optimization
Speaker: Matthew Sullivan, University of Waterloo
Title: "Abstract: We know that not all planar graphs are 3-choosable (as seen by $K_4$), but it is still interesting to find out what types of planar graphs are. I will go into detail about some results on the 3-choosability of planar graphs with 3-cycles far apart using discharging. As well, I will talk about an inductive proof for a more general theorem of Thomassens planar graphs with girth 5 are 3-choosable."
Abstract: We know that not all planar graphs are 3-choosable (as seen by $K_4$), but it is still interesting to find out what types of planar graphs are. I will go into detail about some results on the 3-choosability of planar graphs with 3-cycles far apart using discharging. As well, I will talk about an inductive proof for a more general theorem of Thomassens planar graphs with girth 5 are 3-choosable.


...... WebNotice