Faculty of Mathematics, University of Waterloo

WebNotice Postings: 23-May-2016 through 29-May-2016

Postings for all Departments


Tuesday, 24 May 2016, 10:30AM -- DC 1304
Symbolic Computation Group PhD Seminar -- Computer Science
Speaker: Albert Heinle, David R. Cheriton School of Computer Science
Title: "Studying Factorization in Non-Commutative Rings"
Abstract: In this talk, we will present the latest work on factorization in non-commutative rings.

For commutative integral domains, ring-theoretic properties with respect to factorization of their elements have been extensively studied in the past. For non-commutative integral domains, far less is known. We generalize the notion "finite factorization domain" to non-commutative algebras, and provide conditions to identify such domains.

One class of non-commutative algebras that are finite factorization domains are the so called G-algebras. Many practical rings, like the polynomial Weyl and shift algebras, are included in this class. We present an algorithm that finds all factorizations of a given element in a G-algebra, with minor assumptions on the underlying field. Furthermore, we utilize this algorithm to generalize the factorized Groebner basis algorithm, coming from commutative algebra, to G-Algebras.

Tuesday, 24 May 2016, 11:30AM -- DC 1302
Human-Computer Interaction Seminar -- Computer Science
Speaker: Dr. Christian Hansen, University of Magdeburg
Title: "Human-Computer Interaction in the Operating Room"
Abstract: The interaction with medical software within a sterile environment is a challenging task for physicians. Direct interaction is rather limited because of sterility and workspace restrictions. In this talk, new concepts for human-computer interaction and medical visualization are proposed, including gesture interaction techniques, illustrative rendering techniques, auditory displays and user studies in this field. In addition, relevant projects at the Computer-Assisted-Surgery Group at Otto-von-Guericke University Magdeburg are presented.

Mini Bio: Dr. Christian Hansen is Junior-Professor at the University of Magdeburg, where he heads the Computer-Assisted Surgery research group. His research is focused on Computer-Assisted Radiology and Surgery, Medical Image Processing and Visualization, Medical Augmented Reality, and Human-Computer Interaction. Before starting his own research group, Dr. Hansen was a research scientist at Fraunhofer Institute for Medical Image Computing (MEVIS) in Bremen and received a Ph.D. from the Jacobs University in Bremen in the field of Medical Informatics.

Tuesday, 24 May 2016, 1:30PM -- DC 1304 true
Symbolic Computation Group Seminar -- Computer Science
Speaker: Pierre-Jean Spaenlehauer, Inria Nancy Grand-Est, France
Title: "Sparse polynomial systems with many positive solutions from bipartite simplicial complexes"
Abstract: Positive solutions of polynomial systems are of special interest in several applications of mathematics, for instance when the variables represent physical quantities (e.g. in robotics). We consider the problem of constructing multivariate polynomial systems with real coefficients, prescribed monomial support and many non-degenerate real solutions with positive coordinates. For some families of monomial supports, we use a version of Viro's method to construct polynomial systems all complex solutions of which are real and positive. We also use this construction to investigate special cases of the following problem: how many solutions in the positive orthant can a system of n equations in n variables involving at most t distinct monomials have? In particular, we study a family of fewnomial systems obtained by considering a simplicial complex contained in a regular triangulation of the cyclic polytope: using a symbolic-numeric approach to a matrix completion problem, we will present a method to construct a system of 5 equations in 5 variables, involving only 11 distinct monomials and having 38 positive solutions.

Joint work with Frédéric Bihan.

Tuesday, 24 May 2016, 2:30PM -- MC 6486
Undergraduate Research Seminar -- Combinatorics and Optimization
Speaker: Kevin Purbhoo, University of Waterloo
Title: "Catalan numbers and critical points"
Abstract: The Catalan numbers are famously the answer to a long list of different problems in enumerative combinatorics (binary trees, plane planted trees, non-crossing chord diagrams, 123-avoiding permutations, ... the list goes on and on). After reviewing some of the standard combinatorial examples, we will consider an algebraic one: counting rational functions with prescribed critical points. We will then look at some interesting connections between this algebraic example and the combinatorial ones.

This is more than just a pleasant collection of interconnected examples. Putting everything together establishes the simplest case of a deep theorem (due to Mukhin, Tarasov and Varchenko) about real solutions to certain systems of equations.

Wednesday, 25 May 2016, 12:30PM -- MC 6496
Comprehensive Exam -- Applied Mathematics
Speaker: Lindsey Daniels, Applied Mathematics, University of Waterloo
Title: "Modeling the Interaction of Graphene with a Liquid Electrolyte"
Abstract: Graphene is a two dimensional sheet of hexagonally bonded carbon atoms with remarkable electronic properties. One of the applications of graphene is in an electrolytically gated field effect transistor, where the surface of graphene is in contact with a liquid electrolyte. These transistors can be used as biological and chemical sensors, with sensitivity to pH and ion concentration arising from the adsorption of ions to the graphene-electrolyte interface. There is a significant amount of experimental work measuring the capacitance and conductivity of these transistors, with very little theoretical background. This work first proposes a model for the capacitance, while taking into account the finite size of ions, dielectric saturation, and ionic polarization. This work next proposes a site-binding model, which will account for the bonding of protons (H+) and hydroxyl (OH-) groups, as well as salt ions, to the graphene interface. The site-binding model will give the sensitivity of the configuration to pH and ion concentration.

Thursday, 26 May 2016, 3:30AM - ** Time Change ** - now at 3:30PM
** See updated entry for additional event information **
Speaker: Mahi R. Singh, Department of Physics and Astronomy | Western University
Title: "Switching and sensing mechanism in graphene nanocomposites"

Thursday, 26 May 2016, 9:00AM -- DC 2310
Artificial Intelligence Lab PhD Defence -- Computer Science
Speaker: John A. Doucette, David R. Cheriton School of Computer Science
Title: "Social Choice for Partial Preferences Using Imputation"
Abstract: Within the field of multiagent systems, the area of computational social choice considers the problems arising when decisions must be made collectively by a group of agents. Usually such systems collect a ranking of the alternatives from each member of the group in turn, and aggregate these individual rankings to arrive at a collective decision. However, when there are many alternatives to consider, individual agents may be unwilling, or unable, to rank all of them, leading to decisions that must be made on the basis of incomplete information. While earlier approaches attempt to work with the provided rankings by making assumptions about the nature of the missing information, this can lead to undesirable outcomes when the assumptions do not hold, and is ill-suited to certain problem domains. In this thesis, we propose a new approach that uses machine learning algorithms (both conventional and purpose-built) to generate plausible completions of each agent’s rankings on the basis of the partial rankings the agent provided (imputations), in a way that reflects the agents’ true preferences. We show that the combination of existing social choice functions with certain classes of imputation algorithms, which forms the core of our proposed solution, is equivalent to a form of social choice. Our system then undergoes an extensive empirical validation under 40 different test conditions, involving more than 50,000 group decision problems generated from real-world electoral data, and is found to outperform existing competitors significantly, leading to better group decisions overall. Detailed empirical findings are also used to characterize the behaviour of the system, and illustrate the circumstances in which it is most advantageous. A general testbed for comparing solutions using real-world and artificial data (Prefmine) is then described, in conjunction with results that justify its design decisions. We move on to propose a new machine learning algorithm intended specifically to learn and impute the preferences of agents, and validate its effectiveness. This Markov-Tree approach is demonstrated to be superior to imputation using conventional machine learning, and has a simple interpretation that characterizes the problems on which it will perform well. Later chapters contain an axiomatic validation of both of our new approaches, as well as techniques for mitigating their manipulability. The thesis concludes with a discussion of the applicability of its contributions, both for multiagent systems and for settings involving human elections. In all, we reveal an interesting connection between machine learning and computational social choice, and introduce a testbed which facilitates future research efforts on computational social choice for partial preferences, by allowing empirical comparisons between competing approaches to be conducted easily, accurately, and quickly. Perhaps most importantly, we offer an important and effective new direction for enabling group decision making when preferences are not completely specified, using imputation methods.

Thursday, 26 May 2016, 3:30PM -- MC 5417
Graph Theory Seminar -- Combinatorics and Optimization
Speaker: Luke Postle, University of Waterloo
Title: "Canvases and Colouring"
Abstract: In 1994, Thomassen proved that every plane graph G is 5-choosable by proving a stronger statement, namely that if vertices in the interior have lists of size 5 and the vertices on the outer face have lists of size 3 except for two adjacent vertices on the outer face which are precoloured, then G has an colouring from those lists. Let us say that, in the statement above, the lists of the outer face have been restricted. Here we outline the proof of a far reaching generalization of his result: there exists a D>0 such that if G is a plane graph and F is a set of faces, pairwise at least distance D apart, and L is a list assignment where only the faces of F are restricted, then G has an L-colouring. Joint work with Robin Thomas.

Thursday, 26 May 2016, 3:30PM -- QNC 1501 true
Seminar -- Applied Mathematics
Speaker: Mahi R. Singh, Department of Physics and Astronomy | Western University
Title: "Switching and sensing mechanism in graphene nanocomposites"
Abstract: In this talk both the one-photon and two-photon switching and sensing mechanisms in graphene hybrid nanocomposites will be discussed. Graphene was invented by a Canadian scientist Professor P. R. Wallace in 1947. It is a two-dimensional material where the carbon atoms are arranged in a honeycomb lattice. Hybrid nanomaterials are fabricated by combining two or more semiconductor, metallic, or biological nanostructures with graphene. By using various combinations of these nanostructures one can create enormous numbers of graphene hybrid nanocomposites. The switching and sensing mechanisms in nanocomposites can be controlled by the shape, size and distance between constituent nanostructures. It is expected that this research will provide a basic physical understanding and development of new types of nano-devices including optical sensors and optical switches.

Friday, 27 May 2016, 1:00PM -- DC 2314
Programming Languages Lab PhD Seminar -- Computer Science
Speaker: Rei Thiessen, David R. Cheriton School of Computer Science
Title: "Logic Programming and Static Analyses"
Abstract: We explore logic programming and its relevance to static analysis. We demonstrate its conciseness in expressing an analysis formulation as a high-performance implementation. We present a bottom-up deductive database with a rich index specification language that transforms logic programs into native code using LLVM, resulting in performance that matches hand-written implementations of static analyses.

Friday, 27 May 2016, 3:20PM -- DC 1304
Scientific Computation Group PhD Seminar -- Computer Science
Speaker: Parsiad Azimzadeh, David R. Cheriton School of Computer Science
Title: "Weakly chained matrices, policy iteration, and impulse control"
Abstract: This work is motivated by numerical solutions to Hamilton-Jacobi-Bellman quasivariational inequalities (HJBQVIs) associated with combined stochastic and impulse control problems. A direct control scheme for such an HJBQVI takes the form of a Bellman problem (BP) involving an operator which is not necessarily contractive. We consider the well-posedness of the BP and give sufficient conditions for convergence of a policy iteration to its unique solution. In the event that these conditions do not hold, weaker conditions guarantee uniqueness, from which it is possible to salvage the convergence of policy iteration by (roughly speaking) pruning policies that render the operator appearing in the BP singular. These results are established using weakly chained diagonally dominant matrices, which give a graph-theoretic characterization of weakly diagonally dominant M-matrices. The BP also happens to be the dynamic programming equation associated with an infinite-horizon Markov decision process with vanishing discount factor (a generalization of reflecting boundaries), which is of independent interest. This work appears in Azimzadeh, P., and P. A. Forsyth. "Weakly Chained Matrices, Policy Iteration, and Impulse Control." SIAM Journal on Numerical Analysis 54.3 (2016): 1341-1364.

Friday, 27 May 2016, 3:20PM -- DC 1304
Scientific Computation Group PhD Seminar -- Computer Science
Speaker: Parsiad Azimzadeh, David R. Cheriton School of Computer Science
Title: "Weakly chained matrices, policy iteration, and impulse control"
Abstract: This work is motivated by numerical solutions to Hamilton-Jacobi-Bellman quasivariational inequalities (HJBQVIs) associated with combined stochastic and impulse control problems. A direct control scheme for such an HJBQVI takes the form of a Bellman problem (BP) involving an operator which is not necessarily contractive. We consider the well-posedness of the BP and give sufficient conditions for convergence of a policy iteration to its unique solution. In the event that these conditions do not hold, weaker conditions guarantee uniqueness, from which it is possible to salvage the convergence of policy iteration by (roughly speaking) pruning policies that render the operator appearing in the BP singular. These results are established using weakly chained diagonally dominant matrices, which give a graph-theoretic characterization of weakly diagonally dominant M-matrices. The BP also happens to be the dynamic programming equation associated with an infinite-horizon Markov decision process with vanishing discount factor (a generalization of reflecting boundaries), which is of independent interest. This work appears in Azimzadeh, P., and P. A. Forsyth. "Weakly Chained Matrices, Policy Iteration, and Impulse Control." SIAM Journal on Numerical Analysis 54.3 (2016): 1341-1364.

Friday, 27 May 2016, 3:30PM -- MC 5501
Tutte Colloquium Seminar -- Combinatorics and Optimization
Speaker: Nantel Bergeron, York University
Title: "Following Pipe Dreams"
Abstract: Together with Sara Billey in 1993, we have introduced combinatorial objects to encode monomials occurring in Schubert polynomials. At the time, we called them RC-diagrams as they encode some positioned reduced expressions for a given permutations. They were renamed Pipe Dreams by Knutson and Miller as their pictorial representation evoke the Pipe Dream game from the same era.

As it turn out, these combinatorial objects are interesting in many contexts. In our original work they were envisioned as a generalization of Young tableaux. Later they were used by Knutson and Miller to encode the toric degeneration of Schubert varieties. This naturally led them to introduce some simplicial complexes of subwords that are conjectured to be polytopal in many cases. The faces of the polytope would be indexed by certain pipe dreams.

Very recently, with Pilaud and Ceballos, we have introduced new algebraic operations on pipe dreams. By considering subalgebras, we exhibit very interesting families of pipe dreams that are enumerated by Catalan number $C_{rn+1}$ for a fix $r$. A well we have a family that is in bijection with certain lattice paths studied by Bousquet-melou and Mishna.


...... WebNotice