Faculty of Mathematics, University of Waterloo

WebNotice Postings: 05-Oct-2015 through 11-Oct-2015

Postings for all Departments

Monday, 5 October 2015, 11:00AM *** CANCELLED ***
Database Research Group Master's Research Paper Presentation -- Computer Science
Hella-Fraziska Hoffmann, graduate student, David R. Cheriton School of Comp. Sci., Univ. Waterloo
"Holistic Cleaning of Heterogeneous Datasets using Conditional Denial Constraints"

Monday, 5 October 2015, 3:30PM - ** Time Change ** - now at 4:00PM
** See updated entry for additional event information **
Speaker: Michael Monagan, Dept. Math., Simon Fraser Unviersity
Title: "Computing multivariate polynomial GCDs using sparse interpolation:the problem of unlucky evaluations points and the cost of evaluations."

Monday, 5 October 2015, 4:00PM -- DC 1304 true
Symbolic Computation Group Seminar -- Computer Science
Speaker: Michael Monagan, Dept. Math., Simon Fraser Unviersity
Title: "Computing multivariate polynomial GCDs using sparse interpolation:the problem of unlucky evaluations points and the cost of evaluations."
Abstract: The original Ben-Or/Tiwari sparse interpolation method interpolates a polynomial in Z[x1,x2,...,xn] using evaluation points

(2^j,3^j,5^j,...,pn^j) for j=0,1,2,...,2t-1

where pn is the n'th prime and t is the number of terms of the polynomial. To make the method efficient one runs it modulo a sufficiently large prime p. If d is the degree of the polynomial then we need p of size O( d log n ) bits which can be very big.

Another choice is to pick a prime p of a certain form, pick elements w1,w2,...,wn of relatively prime order in GF(p) evaluate at

(w1^j,w2^j,...,wn^j) for j=0,1,2,...,2t-1.

This approach leads to computing discrete logarithms in GF(p) which is feasible because p is constructed so that p-1 has small factors. The advantage of this approach is that the size of the prime p needed is O( n log d ) bits.

For the polynomial GCD problem, however, we have to deal with unlucky evaluation points. They break the point sequence. In the talk we will present some ideas for how to fix the methods. We give some results for the distribution of unlucky evaluation points. We have implemented a multivariate GCD code in Cilk C using the discrete logarithm approach to investigate it's power. We present benchmarks comparing our code with Zippel's GCD algorithm in Maple and the Hensel lifting GCD algorithm in Magma.

This is joint work with Adriano Aarce, Lucas Hu, and Hao Zhuang.

Tuesday, 6 October 2015, 10:00AM -- DC 2310
Database Research Group Master's Research Paper Presentation -- Computer Science
Speaker: Hella-Fraziska Hoffmann, graduate student, David R. Cheriton School of Comp. Sci., Univ. Waterloo
Title: "Holistic Cleaning of Heterogeneous Datasets using Conditional Denial Constraints"
Abstract: In this work we present a system capable of performing constraint--based holistic cleaning of heterogeneous data sets. Denial Constraints (DCs) are a useful formalism for describing quality constraints on relational tables. We introduce Conditional Denial Constraints (CDCs), an extension to the DC formalism capturing constraints over data in the absence of a relational schema. Our data-cleaning system applies CDCs over the data to discover inconsistencies, stores the discovered rule violations in a common conflict data structure, and accumulates the information to identify potential errors in the source data set. We present a preliminary implementation of the system using RDF data as input and identify important challenges and interesting directions for future research.

Tuesday, 6 October 2015, 10:30AM -- MC 6486
Matroid Seminar Seminar -- Combinatorics and Optimization
Speaker: Benson Joeris, University of Waterloo
Title: "Tangles and tree-decompositions"
Abstract: A $k$-tangle is an abstract structure representing a '$k$-connected component' of a graph or matroid -- e.g., each biconnected component of a graph corresponds to a distinct 2-tangle. A $k$-tree-decomposition constructs a graph or matroid by combining smaller pieces in such a way that the connectivity between pieces is limited -- e.g., a clique-sum construction of a graph, using clique-sums with at most $k$ vertices. Robertson and Seymour showed that a graph or matroid has no $k$-tangle if and only if it can be constructed from pieces of bounded size using a $(k-1)$-tree-decomposition. I will discuss this duality and other related properties of tangles and tree-decompositions.

Wednesday, 7 October 2015, 2:30PM -- MC 5403
Seminar -- Pure Mathematics
Speaker: Kevin Matthews, University of Waterloo
Title: "Local Dimensions of Measures of Finite Type"
Abstract: This talk will examine the multifractal analysis of a particular class of equicontractive self-similar measures. We will begin by reviewing known results in the area. Our focus will be on the set of attainable local dimensions of these measures and a systematic way of computing them. Several examples will be discussed.

Wednesday, 7 October 2015, 3:30PM -- MC 5479
Geometry Working Seminar -- Pure Mathematics
Speaker: Raymond Cheng, Pure Mathematics, University of Waterloo
Title: "Hodge Decomposition and Kahler Manifolds"
Abstract: After a spring of bundles, the autumn will be a study of forms, punctuated with periods of complex manifolds. Before navigating the deep theory of Hodge structures and their variations, however, we should get familiar with the classical theorems which started off the subject: the Hodge decomposition of de Rham cohomology; the hard Lefschetz Theorem; the Riemann bilinear relations; and the various consequences of these results on Kahler manifolds. This talk will be primarily focused on a discussion of the Hodge decomposition theorem and its immediate consequences for Kahler manifolds.

Wednesday, 7 October 2015, 3:30PM -- Math & Computer, Room 5403
Seminar -- Pure Mathematics
Speaker: Mohammad Mahmoud, Department of Pure Mathematics, University of Waterloo
Title: "Algorithmic Randomness: Introduction to Kolmogorov Complexity"
Abstract: After we have established the machine existence (Kraft-Chaitin Theorem), this time we are going to give the proofs for the following "desirable" facts about $K$ which we stated before: (a) Incompressible (in the sense of $K$) strings have only short runs of zeros (i.e. blocks only consisting of zeros), and (b) Zeros and ones occur balancedly.

Wednesday, 7 October 2015, 3:30PM -- DC 1302
Distinguished Lecture Series Seminar -- Computer Science
Speaker:  Prof. Tony F. Chan,, President, The Hong Kong University of Science and Technology (HKUST)
Title: "Image Processing and Computational Mathematics"
Abstract: Image processing has traditionally been studied as a form of signal processing, and a subfield of electrical engineering. Recently, with the advent of inexpensive and integrated image capturing devices, leading to massive data and novel applications, the field has seen tremendous growth. Within computational mathematics, image processing has emerged not only as an application domain where computational mathematics provide ideas and solutions, but also in spurring new research directions (a “new Computational Fluid Dynamics”) in geometry (Total Variation regularization and Level Set methods), optimization (primal-dual, Bregman and Augmented Lagrangian methods, L1 convexification), inverse problems (inpainting, compressive sensing), and graph algorithms (high-dimensional data analysis). This talk gives an overview of these developments.

BIO:  Professor Tony F Chan assumed the presidency of HKUST on 1 September 2009.   Professor Chan’s scientific background is in Mathematics, Computer Science and Engineering. He received his PhD in Computer Science from Stanford University. He taught at Yale University before joining UCLA as Professor of Mathematics in 1986. He was appointed Chair of the Department of Mathematics in 1997 and served as Dean of Physical Sciences from 2001 to 2006. From 2006 to 2009, Professor Chan was Assistant Director of the Mathematical and Physical Sciences Directorate at the U.S. National Science Foundation (NSF).   Professor Chan is an elected member of the US National Academy of Engineering (NAE), a senior member of the Institute of Electrical and Electronic Engineers (IEEE) and an elected fellow of both the Society for Industrial and Applied Mathematics (SIAM) and the American Association for the Advancement of Science.  Professor Chan was one of the world’s most cited mathematicians.   Professor Chan is currently a member of the Board of Trustees of the King Abdullah University of Science and Technology (KAUST) in Saudi Arabia, President’s Advisory Council of the Korea Advanced Institute of Science and Technology (KAIST), Scientific Advisory Board of the University of Vienna, and the United States Committee of 100. Professor Chan is also a member of the Advisory Committee on Innovation and Technology of the Hong Kong Government.  He was a member of the Selection Committee for the Shaw Prize in Mathematical Sciences in 2012 and 2013.

Wednesday, 7 October 2015, 3:30PM -- MC 6486
Algebraic Graph Theory Seminar -- Combinatorics and Optimization
Speaker: Chris Godsil, University of Waterloo
Title: "Quantum walks"
Abstract: We will introduce basic ideas in the application of spectral graph theory to quantum walks.

Thursday, 8 October 2015, 2:30PM -- MC 5417
Seminar -- Applied Mathematics
Speaker: Mercedes Perez Millan, University of Buenos Aires
Title: "Steady States of MESSI biological systems"
Abstract: Many processes within cells involve some kind of post-translational modification of proteins. We introduce here a general framework for biological systems that describe Modifications of type Enzyme-Substrate or Swap with Intermediates, which we call MESSI systems. There are many relevant examples of these systems in nature. Assuming mass-action kinetics, we simplify the study of steady states and conservation laws (inspired by [Feliu and Wiuf 2013, Thomson and Gunawardena 2009]). We also describe an important subclass of MESSI systems with toric steady states, that enables an algorithmic criterion for determining the capacity for multistationarity. This is joint work with Alicia Dickenstein.

Thursday, 8 October 2015, 3:00PM -- DC 2310
Software Engineering Research Group Master's Thesis Presentation -- Computer Science
Speaker: Xiao Ye Lan, graduate student, David R. Cheriton School of Comp. Sci., Univ. Waterloo
Title: "An Experimental Study towards Achieving 100% Recall of Synonyms in Software Requirements Documents, with Selected Method"
Abstract: Software requirements documents written in natural language need to avoid the use of synonyms to reduce unnecessary confusion and ambiguity. In practice, synonyms are still common and are widely used in requirements documents. Lots of tools to identify synonyms have been developed. To evaluate these tools, two metrics are often used: recall and precision. Recall is the ratio of the number of relevant records retrieved to the total number of relevant records in the document. Precision is the fraction of retrieved records that are relevant. Industry practice leads us to believe that 100% recall is preferred over 100% precision for such tools. Available tools never actually achieve 100% recall. The goal of this thesis is to explore computational methods that could reach 100% recall in extracting synonyms from software requirements documents.

This thesis compares six WordNet-based methods and two context-based algorithmic approaches to extract synonyms from two different types of requirement documents. The eight methods were compared by their recall. The experiments results showed that the word co-occurrence-based method achieved the best recall in identifying synonyms of the software requirements documents. Further experiments showed that setting the parameters of the word co-occurrence-based method impacts the results of the experiments as well. The thesis also discusses potential issues of the word co-occurrence-based method in the design of the experiments. The document author's personal factors could influence the experiment results, but this influence can be avoided with careful design.

Thursday, 8 October 2015, 4:00PM -- M3 3127
Seminar -- Statistics & Actuarial Science
Speaker: David Hunter, Pennsylvania State University
Title: "Maximum Smoothed Likelihood for Multivariate Mixtures"
Abstract: This talk discusses nonparametric finite mixture models, beginning with an introduction of several basic ideas such as finite mixture models and the EM algorithms often used to fit them. We then introduce an algorithm for estimating the parameters in a finite mixture of completely unspecified multivariate components in at least three dimensions under the assumption of conditionally independent coordinate dimensions. We prove that this algorithm, based on a majorization-minimization idea, possesses a desirable descent property just as any EM algorithm does. We also demonstrate via simulation studies that the new algorithm gives very similar results to another algorithm that does not satisfy any descent algorithm. We provide and demonstrate code for implementing the new algorithm in a publicly-available R package. Finally, we discuss recent extensions of this work.

Friday, 9 October 2015, 3:30PM -- MC 5417
Analysis Seminar Seminar -- Pure Mathematics
Speaker: Javad Mashreghi, Laval University
Title: "The Halmos Conjecture on the Numerical Range"
Abstract: Let $T$ be an operator on a Hilbert space $H$ with numerical radius $w(T) \leq 1$. Halmos conjectured that $w(T^n) \leq 1$, $n \geq 1$. After several partial results, it was finally settled by Berger using dilation theory. The Berger--Stampfli theorem, a generalization of the conjecture, says that if $f$ is a function in the disk algebra such that $f(0)=0$, then $w(f(T))\leq \|f\|_\infty$. We give an elementary proof of this result using finite Blaschke products.

Joint work with H. Klaja and T. Ransford.

Friday, 9 October 2015, 3:30PM -- MC 5501
Tutte Colloquium Colloquium -- Combinatorics and Optimization
Speaker: Levent Tuncel, University of Waterloo
Title: "Coffman-Sethi conjecture in multiprocessor scheduling"
Abstract: Ron Graham's work, during the late 1960s, on proving that LPT (Longest Processing Time) list scheduling algorithm has the worst-case approximation ratio of precisely $4/3 -1/(3m)$ (where $m$ is the number of machines) has been inspirational in the areas of approximation algorithms as well as in scheduling theory. Inspired by this work, Coffman and Sethi proposed an extension of this algorithm for a refinement of the underlying problem and a conjecture on its worst-case approximation ratio: $(5m-2)/(4m-1)$, in 1976. This conjecture stayed open for 39 years. In this talk, I will discuss a proof of this conjecture. Our proof of the conjecture designs and uses techniques somewhat analogous to those used in (graph minors based) structural graph theory.

This talk is based on two joint papers: one with M. Huang and P. Ravi (2013)and the other with P. Ravi (2015).

...... WebNotice