Faculty of Mathematics, University of Waterloo

WebNotice Postings: 27-Jul-2015 through 02-Aug-2015

Postings for all Departments

Monday, 27 July 2015, 1:30PM -- MC 5479
Algebra Learning Seminar Seminar -- Pure Mathematics
Speaker: Ehsaan Hossain, Pure Mathematics, University of Waterloo
Title: "The Invariant Basis Number Property"
Abstract: In linear algebra, the "dimension" of a vector space can be defined uniquely --- every vector space has a basis, and all bases have the same cardinality. But this is a special advantage of working over a field. What about modules over a general ring $R$? It's possible that an $R$-module does not possess a basis, and even if it does, there may be bases of different cardinalities. In fact there is an easy example of a module possessing a basis is of cardinality $n$, for all $n\in \mathbf{N}$. Can we find an example of an $R$-module with bases of cardinality 2 and 3, but not 5? How far can we push this? We will see a group, called $K_0(R)$, which encodes this information (at least partially). I also hope to convince you that this investigation leads inevitably to the invention of Leavitt path algebras.

Monday, 27 July 2015, 2:30PM -- DC 1304
Cryptography, Security, and Privacy (CrySP) Group Seminar -- Computer Science
Speaker: Amir Herzberg, Tenured Professor, Dept. Comp. Sci., Bar Ilan University
Title: "Cross-site Search is Practical: Privacy Attacks on Webservice Users"
Abstract: Cross-site search (XS-search) attacks circumvent the same-origin policy and extract sensitive information, by using the time it takes for the browser to receive responses to search queries. This side-channel is usually considered impractical, due to the limited attack duration and high variability of delays. This may be true for naive XS-search attacks; however, we show that the use of better tools facilitates effective XS-search attacks, exposing information efficiently and precisely.

We present and evaluate three types of tools: (1) appropriate statistical tests, (2) amplification of the timing side-channel, by `inflating' communication or computation, and (3) optimized, tailored divide-and-conquer algorithms, to identify terms from large `dictionaries'. These techniques may be applicable in other scenarios.

We implemented and evaluated the attacks against the popular Gmail and Bing services, in several environments and ethical experiments, taking careful, IRB-approved measures to avoid exposure of personal information. Try a demo of the attack that efficiently extracts the name of authenticated Gmail user online in http://xssearch.weebly.com/.

Joint work with Nethanel Gelernter.

Bio: Prof. Amir Herzberg is a tenured professor in the department of computer science, Bar Ilan university. He received B.Sc. (1982, Computer Engineering), M.Sc. (1987, Electrical Engineering) and D.Sc. (1991, Computer Science), all from the Technion, Israel. His current research interests include Network security, Applied cryptography, Privacy, anonymity and covert communication, Cyber-security, Usable security and social-engineering attacks, Financial cryptography, Trust management, Network protocols and distributed algorithms, Security of and using new network paradigms.

He filled research and management positions in IBM Research, Israeli Defense Forces and several companies, and is consulting when time allows.

Monday, 27 July 2015, 4:15PM -- MC 6486
Seminar -- Combinatorics and Optimization
Speaker: Hao Sun, University of Waterloo
Title: "Separating Maximally Violated Comb Inequalities in Planar Graphs"
Abstract: In this paper, we consider the problem of finding violated comb inequalities. If there are no violated subtour constraints in a fractional solution of the TSP, a comb inequality may not be violated by more than 1. Given a fractional solution in the subtour elimination polytope whose graph is planar, we either find a violated comb inequality or determine that there are no comb inequalities violated by 1. Our algorithm runs in O(n / MC(n) ) time, where MC(n) is the time to compute a cactus representation of all minimum cuts of a weighted planar graph on n vertices.

The presentation will be based on the following manuscript: http://www.jstor.org/stable/3690533

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

Tuesday, 28 July 2015, 10:30AM -- MC 5479
PhD Defence -- Pure Mathematics
Speaker: Shuntaro Yamagishi, Pure Mathematics, University of Waterloo
Title: "Some additive results in $\mathbb{F}_q[t]$"
Abstract: We collected several results in $\mathbb{Z}$ of additive number theory and translated to results in $\mathbb{F}_q[t]$. The results we collected are related to slim exceptional sets and the asymptotic formula in Waring's problem, diophantine approximation of polynomials over $\mathbb{Z}$ satisfying divisibility conditions, and the problem of Sidon regarding existence of certain thin sequences.

Tuesday, 28 July 2015, 10:30AM -- M3-2134
Seminar -- Applied Mathematics
Speaker: Daniel Otero, PhD Candidate, Department of Applied Mathematics, University of Waterloo
Title: "Function-valued mappings and SSIM-based optimization: two alternative approaches to imaging"
Abstract: In this talk we present two novel approaches to carry out image processing tasks, namely, function-valued mappings (FVMs) and structural similarity index measure (SSIM)-based optimization. With FVMs, also known as Banach-valued functions in the literature, we propose a different way of representing complex datasets, e.g., hyperspectral and diffusion magnetic resonance images, which are usually represented as vector-valued functions. The infinite dimensionality of the range of FVMs offers interesting possibilities for modelling different kinds of datasets, as well as making possible the generalization of the classical fractal and Fourier transforms. As for SSIM-based optimization, we present a general framework for solving optimization problems in which the SSIM is employed as a fidelity term. This framework allows us to solve optimization problems involving the SSIM that had not been addressed before, and also provides an alternative way of performing some of the well known Euclidian-based image processing tasks: e.g., sparse reconstruction, denoising, zooming, etc.. Potential and current developed applications of these two approaches to imaging are also discussed.

Tuesday, 28 July 2015, 2:30PM -- M3-2134
Number Theory Seminar Seminar -- Pure Mathematics
Speaker: Chantal David, Concordia University
Title: "“Averages of Euler products and statistics of elliptic curves Joint work with D. Koukoulopoulos and E. Smith.”"
Abstract: We present in this talk several results related to statistics of elliptic curves over a finite field Fp, which follow from a general theorem about averages of Euler products. In this general framework, we can reprove known results as the vertical Lang-Trotter conjecture, the vertical Koblitz conjecture, and the vertical Sato-Tate conjecture (for very short intervals). We can also compute statistics for new questions as the problem of amicable pairs and aliquot cycles, First introduced by Silverman and Stange. Our technique is broad and general, and easily appli- cable to other distribution questions. The starting point of our results is a theorem of Gekeler which gives a reinterpretation of Deuring’s theorem in terms of random matrix theory, making a direct con- nection between the (conjectural) horizontal distributions and the vertical distributions. A key step of our results is to control the stabilization of the Euler factors appearing in Gekeler’s theorem: for each ‘, the Euler factor related to random matrix theory is defined as the r-limit of a matrix count modulo ‘r, which stabilizes for some r depending on ‘ and p. Our main result shows that under cer- tain conditions for this stabilization, a weighted average of Euler products is asymptotic to the Euler product of the average factors (which are stable for r = 1).

Tuesday, 28 July 2015, 2:30PM - ** Date Change ** - now Thursday, 30 July 2015, 2:30PM
** See updated entry for additional event information **
Speaker: Christoph Simon, University of Calgary
Title: "Extending the quantum domain with quantum optics"

Wednesday, 29 July 2015, 10:00AM -- MC 6496
Master's Thesis Presentation -- Applied Mathematics
Speaker: Tawsif Khan, MMath candidate, Applied Mathematics
Title: "Optimal Sensor Location for the Estimation of a Linear Dispersive Wave Equation"
Abstract: The problem of optimal sensor location for the estimation of a linear dispersive wave equation is considered in this work. A steady-state Kalman filter was used as an optimal state observer with localized velocity information as the measurement. Since the main model is a partial differential equation, the states evolve in infinite-dimensional spaces, and hence an approximation (finite representation) was required to design the observer. Three different approximation methods were compared - eigenfunctions and finite element methods using a linear and a high-order polynomial basis. The latter two methods are the more common choice of approximation schemes for systems with a complex geometry. It was found that the eigenfunctions perform much better as expected. The finite element methods require larger matrices to approximate the system with reasonable accuracy and hence calls for numerical methods to solve the Algebraic Riccati Equation efficiently. The optimal sensor location was considered for three different noise models - a localized noise, a more distributed nature of noise and finally an one-dimensional turbulence model. It was seen that the optimal location tend to be closer to the point where the physical shape of the noise reaches its maximum. Placing the sensor in the optimal location showed significant improvement in the estimation process.

Wednesday, 29 July 2015, 10:00AM -- M3-3103
PhD Defence -- Applied Mathematics
Speaker: Puneet Sharma, Applied Math, University of Waterloo
Title: "Modeling Interactions of Graphene with Electrolyte"
Abstract: Understanding interactions of graphene with an electrolyte is fundamental to its applications for chemical and biological sensors, where graphene operates in the configuration of a field-effect transistor with its surface exposed to liquid containing mobile ions. By applying a gate potential through an electrolyte one may achieve a control of graphene's conductivity that is extremely sensitive to the presence of adsorbed molecules, ion concentration, or the pH in an aqueous solution. In addition, charged impurities in the oxide layer underneath graphene also affect its conductivity by causing fluctuations of the scattering potential for charge carriers in graphene. Since the gate potential used for graphene doping in such applications is usually large, it is necessary to consider nonlinear effects in the equilibrium doping of graphene using a full density of states for its pi electron bands, while in the electrolyte it is necessary to assess the effects due to finite size of ions and dielectric saturation of water near highly doped graphene. We first explore the capacitance of a graphene-electrolyte interface using well established continuum models from electrochemistry that generalize the Poisson-Boltzmann (PB) theory: the Bikerman model for steric effects due to ion size and the Booth model for dielectric saturation. Next, we develop a model to describe the screening of the electrostatic potential that arises in the plane of graphene due charged impurities in the oxide. For the polarizability of charge carriers in graphene we explore two models, one based on the Thomas-Fermi approximation and the other based on the Random Phase approximation for graphene's pi electron bands in the Dirac cone approximation. On the other hand, the ion distribution in the electrolyte is described by a fully linearized PB model, which is suitable for a low gating potential, as well as by a partially linearized PB model, which contains full information on the equilibrium gating conditions of graphene. The screened potential due to charged impurities is described by a dielectric response formulation of the problem, which is derived from the Green's function for the Poisson equation for the entire structure containing graphene. Statistical properties of the fluctuations in the potential are analyzed by means of its auto-correlation function, which is expressed in terms of a structure factor for the geometric positions of charged impurities in the oxide. We conclude with a discussion of the roles played by the external parameters, such as the gate potential, ion concentration and the density of charged impurities in the doping and screening properties of electrolytically gated graphene.

Wednesday, 29 July 2015, 11:30AM -- QNC 1201
Institute for Quantum Computing PhD Seminar -- Computer Science
Speaker: Alessandro Cosentino, PhD candidate, David R. Cheriton School of Comp. Sci., University of Waterloo
Title: "Query/witness trade-offs for quantum computations"
Abstract: As separate topics, quantum query complexity and the power of quantum witnesses (central to the definition of the complexity class QMA) have been studied extensively by researchers in quantum computing. In this talk I will present some results we have obtained (in a joint work with Robin Kothari and John Watrous) by merging these two topics and looking at the power of quantum witnesses in quantum query complexity. First I will show some trade-offs between the number of queries and the size of a quantum witness for the task of computing the functions OR and PARITY in a worst-case scenario. The second part of the talk will concern again a query/witness trade-off for the PARITY function, but this time in an average-case scenario. Implications of the latter result to the power of random oracles for QMA will be discussed.

Wednesday, 29 July 2015, 1:30PM -- M3 2134
Geometry Working Seminar -- Pure Mathematics
Speaker: Raymond Cheng, Pure Mathematics, University of Waterloo
Title: "Gutting Bundles on Tori"
Abstract: Remember the beginning of the term when I was talking about vector bundles over complex tori? Well, I shall be talking about such objects again, except in far less grandeur; I will humbly discuss line bundles on tori and perhaps venture forth into the frightful realm of rank two vector bundles on two dimensional tori. For my own sadistic pleasure, the audience may be subjected to a painfully explicit exposition on the inner workings of these bundles: present may be a macabre scene of matrices and forms. Hopefully, such a gruesome display will not leave the listener too morose, and that he or she may learn a useful trick or two for flaying his or her own geometric problems.

Thursday, 30 July 2015, 10:30AM -- M3-2134
Seminar -- Applied Mathematics
Speaker: Daniel Otero, PhD Candidate, Department of Applied Mathematics, University of Waterloo
Title: "Function-valued mappings in imaging"
Abstract: The concept of a function whose range is infinite dimensional has been studied by mathematicians since the third decade of the last century. Given this, nowadays there is a vast literature on how the classical results of real-valued functions carry over functions that assume values in a Banach space. Several fields have benefited from these contributions, among them partial differential equations, statistics and harmonic analysis. Surprisingly, the image processing community has barely explored the potential of these mathematical objects. In this talk we discuss how this type of functions, which we call function-valued mappings (FVMs), can be employed in an image processing context. In particular, we present a Fourier transform and a new class of fractal transforms for FVMs. Practical applications are also discussed.

Thursday, 30 July 2015, 10:30AM -- DC 2585
Bioinformatics Group Seminar -- Computer Science
Speaker: Guohui Lin, Professor, University of Alberta
Title: "A PTAS for the multiple parallel identical multi-stage flowshops to minimize the makespan"
Abstract: In the parallel k-stage flowshops problem, we are given m identical k-stage flowshops and a set of jobs. Each job can be processed by any one of the flowshops but switching between flowshops is not allowed. The objective is to minimize the makespan, which is the finishing time of the last job. This problem generalizes the classical parallel identical machine scheduling and the classical flowshop scheduling problems, and thus it is NP-hard. We present a polynomial-time approximation scheme for the problem, when m and k are fixed constants.

Thursday, 30 July 2015, 1:00PM -- DC 2310 true
Bioinformatics Group PhD Defence -- Computer Science
Speaker: Laleh Soltan Choraie, PhD candidate, David R. Cheriton School of Comp. Sci., Univ. Waterloo
Title: "New Algorithms for Predicting Conformational Polymorphism and Inferring Direct Couplings for Side Chains of Proteins"
Abstract: Protein crystals populate diverse conformational ensembles. Despite much evidence that there is widespread conformational polymorphism in protein side chains, most of the x-ray crystallography data are modelled by single conformations in the Protein Data Bank. The ability to extract or to predict these conformational polymorphisms is of crucial importance, as it facilitates deeper understanding of protein dynamics and functionality. This dissertation describes a computational strategy capable of predicting side-chain polymorphisms. The applied approach extends a particular class of algorithms for side-chain prediction by modelling the side-chain dihedral angles more appropriately as continuous rather than discrete variables. Employing a new inferential technique known as particle belief propagation (PBP), we predict residue-specific distributions that encode information about side-chain polymorphisms. The predicted polymorphisms are in relatively close agreement with results from a state-of-the-art approach based on x-ray crystallography data. This approach characterizes the conformational polymorphisms of side chains using electron density information, and has successfully discovered previously unmodelled conformations.

Furthermore, it is known that coupled fluctuations and concerted motions of residues can reveal pathways of communication used for information propagation in a molecule and hence, can help in understanding the "allostery" phenomenon in proteins. In order to characterize the coupled motions, most existing methods infer structural dependencies among a protein's residues. However, recent studies have highlighted the role of coupled side-chain fluctuations alone in the allosteric behaviour of proteins, in contrast to a common belief that the backbone motions play the main role in allostery. These studies and the aforementioned recent discoveries about prevalent alternate side-chain conformations (conformational polymorphism) accentuate the need to devise new computational approaches that acknowledge side chains' roles. As well, these approaches must consider the polymorphic nature of the side chains, and incorporate effects of this phenomenon (polymorphism) in the study of information transmission and functional interactions of residues in a molecule. Such frameworks can provide a more accurate understanding of the allosteric behaviour.

Hence, as a topic related to the conformational polymorphism, this dissertation addresses the problem of inferring directly coupled side chains, as well. First, we present a novel approach to generate an ensemble of conformations and an efficient computational method to extract direct couplings of side chains in allosteric proteins. These direct couplings are used to provide sparse network representations of the coupled side chains. The framework is based on a fairly new statistical method, named graphical lasso (GLASSO), devised for sparse graph estimation. In the proposed GLASSO-based framework, the side-chain conformational polymorphism is taken into account. It is shown that by studying the intrinsic dynamics of an inactive structure alone, we are able to construct a network of functionally crucial residues. Second, we show that the proposed method is capable of providing a magnified view of the coupled and conformationally polymorphic side chains. This model reveals couplings between the alternate conformations of a coupled residue pair. To the best of our knowledge, this is the first computational method for extracting networks of side chains' alternate conformations. Such networks help in providing a detailed image of side-chain dynamics in functionally important and conformationally polymorphic sites, such as binding and/or allosteric sites. This information may assist in new drug-design alternatives.

Side-chain conformations are commonly represented by multivariate angular variables. However, the GLASSO and other existing methods that can be applied to the aforementioned inference task are not capable of handling multivariate angular data. This dissertation further proposes a novel method to infer direct couplings from this type of data, and shows that this method is useful for identifying functional regions and their interactions in allosteric proteins. The proposed framework is a novel extension of canonical correlation analysis (CCA), which we call "kernelized partial CCA" (or simply KPCCA). Using the conformational information and fluctuations of the inactive structure alone for allosteric proteins in the Ras and other Ras-like families, the KPCCA method identified allosterically important residues not only as strongly coupled ones but also in densely connected regions of the interaction graph formed by the inferred couplings. The results were in good agreement with other empirical findings and outperformed those obtained by the GLASSO-based framework. By studying distinct members of the Ras, Rho, and Rab sub-families, we show further that KPCCA is capable of inferring common allosteric characteristics in the small G protein super-family.

Thursday, 30 July 2015, 2:30PM -- QNC 1201 true
Seminar -- Institute for Quantum Computing
Speaker: Christoph Simon, University of Calgary
Title: "Extending the quantum domain with quantum optics"
Abstract: Quantum optical systems are well suited for pushing the boundaries of quantum physics. Two big goals in this context are the creation of entanglement over long distances and the observation of quantum effects on macroscopic scales. I will describe various theoretical and some experimental work in these directions. In particular I am planning to discuss quantum repeaters with multimode quantum memories, the potential for global entanglement using satellite links and repeaters, work towards the quantum non-demolition detection of photonic qubits in rare-earth doped crystals, ideas on photon-photon gates based on Rydberg states, an experiment creating micro-macro entanglement of light, and a proposal for spin cat states in Bose-Einstein condensates.

...... WebNotice