**Monday, 25 May 2015, 10:30AM**-- DC 1304*Seminar*-- Computer Science*Speaker:*Dr. Dana Moshkovitz, Computer Science, MIT, Computer Science, MIT*Title:**"Hard Problems in Hardness of Approximation: Sharp Thresholds, Parallel Repetition and Unique Games"*

*Abstract:*Many of the optimization problems of interest to humanity are NP-hard, and most computer scientists believe that they have no efficient algorithms. Focusing on approximation rather than exact optimization might extend the reach of algorithmic technique into the intractable. However, for many NP-hard problems approximating them better than a problem-dependent threshold turns out to be NP-hard as well. Proving so rigorously is a difficult task, which -- by a leap of thought -- leads to fundamental questions about the nature of proofs and their verification.In this talk I'll discuss the phenomenon of sharp thresholds in approximability, namely how many approximation problems transform instantly from efficiently solvable to exponentially hard as one focuses on a better approximation (joint work with Ran Raz). I'll discuss two prover games and a new, incredibly simple, method ("fortification") for analyzing their parallel repetition. Finally, I'll discuss a recent candidate hard instance for unique games, which might lead to progress on the Unique Games Conjecture - one of the biggest open problems in approximability (joint work with Subhash Khot).

BIO

Dana Moshkovitz is an assistant professor of Computer Science at MIT. Her research is in Theoretical Computer Science, and much of it focuses on the limitations of approximation algorithms and probabilistic checking of proofs.

Dana did her PhD at the Weizmann Institute in Israel. Her thesis co-won the Nessyahu Prize for best math PhD thesis in Israel in 2009, and part of this work was awarded the FOCS 2008 Best paper.

Dana went on to spend a couple of years at Princeton University and the Institute of Advanced Study before joining MIT in the end of 2010. She is the recipient of MIT's Jerome Saltzer teaching award.

**Monday, 25 May 2015, 1:30PM**-- DC 2314*Database Research Group PhD Seminar*-- Computer Science*Speaker:*Ahmed El-Roby, PhD candidate, David R. Cheriton School of Comp. Sci., Univ. Waterloo*Title:**"ALEX: Automatic Link Exploration in Linked Data"*

*Abstract:*There has recently been an increase in the number of RDF knowledge bases published on the Internet. These rich RDF data sets can be useful in answering many queries, but much more interesting queries can be answered by integrating information from different data sets. This has given rise to research on automatically linking different RDF data sets representing different knowledge bases. This is challenging due to their scale and semantic heterogeneity. Various approaches have been proposed, but there is room for improving the quality of the generated links.In this paper, we present ALEX, a system that aims at improving the quality of links between RDF data sets by using feedback provided by users on the answers to linked data queries. ALEX starts with a set of candidate links obtained using any automatic linking algorithm. ALEX utilizes user feedback to discover new links that did not exist in the set of candidate links while preserving link precision. ALEX discovers these new links by finding links that are similar to a link approved by the user through feedback on queries. ALEX uses a Monte-Carlo reinforcement learning method to learn how to explore in the space of possible links around a given link. Our experiments on real-world data sets show that ALEX is efficient and significantly improves the quality of links.

**Tuesday, 26 May 2015, 10:00AM**-- MC 6496*Comprehensive Exam*-- Applied Mathematics*Speaker:*Alex Howse, Applied Mathematics, University of Waterloo*Title:**"Optimization Methods for Tensor Decompositions"*

*Abstract:*Tensors, numerical multilinear arrays, are commonly used to organize and analyze data in applications throughout the sciences. Many of these applications make use of tensor decompositions, which express tensors as sums or products of several components, and can be used to obtain approximations in convenient formats. We consider the higher order singular value decomposition (HOSVD), which expresses a tensor as the multilinear product of a tensor with typically smaller dimensions and a set of matrices with useful orthonormality properties.We present two optimization algorithms for computing HOSVD tensor approximations in a matrix manifold context: a nonlinearly preconditioned conjugate gradient (NPCG) iteration and a nonlinear GMRES iteration. In NPCG, a vector generated by a nonlinear preconditioner replaces the gradient in standard nonlinear conjugate gradient; and in nonlinear GMRES, a linear combination of past iterates and a tentative new iterate, generated by a nonlinear preconditioner, is minimized to produce an improved search direction. Numerical results show that these methods can significantly accelerate the standard iteration for computing HOSVD approximations.

**Tuesday, 26 May 2015, 10:30AM**-- DC 1304*Seminar*-- Computer Science*Speaker:*Dr. Scott Aaronson, MIT*Title:**"Exploring the Limits of the Efficiently Computable"*

*Abstract:*I'll give a broad overview of my research over the last decade aimed at understanding the relationship between computational complexity and physics; and in particular, the capabilities and limitations of quantum computers. Possible topics, depending on time, will include the BosonSampling model of quantum computing, creating unforgeable 'quantum money' using hidden subspaces, quantum computing versus the polynomial-time hierarchy, maximal separations between classical and quantum query complexity, the need for structure in quantum speedups, and the computational complexity of decoding Hawking radiation.BIO

Scott Aaronson is an Associate Professor of Electrical Engineering and Computer Science at MIT. He studied at Cornell and UC Berkeley, and did postdocs at the Institute for Advanced Study as well as the University of Waterloo. His research focuses on the capabilities and limitsof quantum computers, and more generally on computational complexity and its relationship to physics. His first book, Quantum Computing Since Democritus, was published in 2013 by Cambridge University Press. Aaronson has written about quantum computing for Scientific American and the New York Times, and writes a popular blog. He’s received the National Science Foundation’s Alan T. Waterman Award, the United States PECASE Award, and MIT's Junior Bose Award for Excellence in Teaching.

**Tuesday, 26 May 2015, 1:30PM**-- MC 5479 true*Geometry Working Seminar*-- Pure Mathematics*Speaker:*Spiro Karigiannis, Pure Mathematics Department University of Waterloo*Title:**"“Differential Analysis III: The Kuranishi Model and the Sard-Smale Theorem”"*

*Abstract:*This is the third in a series of talks on various aspects of differential analysis, including Fredholm theory and the index of Fredholm operators, the infinite-dimensional implicit func- tion theorem and its applications to moduli spaces, elliptic regularity, and more. This week, we finish the proof of the implicit function theorem, discuss the Kuranishi model (a local de- scription for the zero set of a smooth map between Banach spaces) and begin to discuss the infinite-dimensional version of Sard’s Theorem due to Smale. Everyone is welcome to attend.

**Tuesday, 26 May 2015, 4:00PM**-- M3 3127*Seminar*-- Statistics & Actuarial Science*Speaker:*Jaideep Oberoi, University of Kent*Title:**"An Alternative Structure for Home Equity Release"*

*Abstract:*I will present joint work with Doug Andrews on an alternative financial structure for home equity release, involving the creation of new securities by one or more central counterparties. Such a structure holds the possibility of improving risk allocation across the economy, leading to overall welfare gains. In ongoing work we have considered the pricing of the re-allocated (or unbundled) risks in home equity release, using a sample of actual home sales. We find that the alternative structure offers the possibility of significantly higher loan to value ratios for borrowers. At the same time, we argue that the securities created would be appealing to a large group of investors that seek exposure to residential real estate as an asset class for their portfolios. I will present some of our findings on the relevant risks and their impact on the pricing of home equity release. Comments and suggestions are especially welcome and solicited.

**Wednesday, 27 May 2015, 3:00PM**-- MC 6486*Seminar*-- Combinatorics and Optimization*Speaker:*Chris Godsil, University of Waterloo*Title:**"URA Seminar: Representations of graphs"*

**Thursday, 28 May 2015, 1:30PM**-- MC 5479*Number Theory Seminar Seminar*-- Pure Mathematics*Speaker:*Igor Shparlinski, University of New South Wales*Title:**"“Effective Hilbert’s Nullstellensatz and Finite Fields”"*

*Abstract:*We give an overview of recent applications of effective versions of Hilbert’s Nullstellensatz to various problems in the theory of finite fields. In particular, we resent some results about the size of the set generated by s-fold products of some rational fractions in a finite field. This result has some algorithmic applications. We also show that almost all points on algebraic varieties over finite fields avoid Cartesian products of small order groups. This result is a step towards Poonen’s conjecture. We finish with an outline of some open problems.

**Thursday, 28 May 2015, 2:00PM**-- M3-4206*Computability Learning Seminar*-- Pure Mathematics*Speaker:*Mohammad Mahmoud, Department of Pure Mathematics University of Waterloo*Title:**"“Ramsey’s Theorem”"*

*Abstract:*We have seen with Sam two proofs of Ramsey’s Theorem. This time we give a third proof of that uses Konig’s Lemma but can be carried out in RCA0.

**Thursday, 28 May 2015, 4:00PM**-- MC 6486*Graph Theory Seminar*-- Combinatorics and Optimization*Speaker:*Nishad Kothari, University of Waterloo*Title:**"A generation theorem for near-bipartite bricks"*

*Abstract:*It is well-known that all 3-connected graphs may be generated from K4 by means of two operations: "edge addition" and "vertex expansion". (However, to do so, one must allow parallel edges.) We will discuss similar results for a special class of 3-connected graphs called 'bricks', which play a central role in matching theory.A 3-connected graph G is a brick if G - {u,v} has a perfect matching for each pair of vertices u and v. It was shown by Carvalho, Lucchesi and Murty that all bricks may be generated from K4, the triangular prism and the Petersen graph by means of four operations.

We prove a generation theorem for a special class of bricks; a brick G is near-bipartite if it has two edges e and f such that G - {e,f} is bipartite and matching covered. In particular, we show that all near-bipartite bricks may be generated from K4 and the triangular prism by means of three operations.

**Thursday, 28 May 2015, 4:00PM**-- M3 3127*Seminar*-- Statistics & Actuarial Science*Speaker:*Runhuan Feng, University of Illinois at Urba, University of Illinois at Urbana– Champaign*Title:**"Conditional Asian Options"*

*Abstract:*Conditional Asian options are recent market innovations, which offer cheaper and long-dated alternatives to regular Asian options. In contrast with payoffs from regular Asian options which are based on average asset prices, the payoffs from conditional Asian options are determined only by average prices above certain threshold. Due to the limited inclusion of prices, conditional Asian options further reduces the volatility in the payoffs than their regular counterparts and have been promoted in the market as viable hedging and risk management instruments for equity-linked life insurance products. There has been no previous academic literature on this subject and practitioners have only been known to price these products by simulations. We propose the first analytical approach to computing prices and deltas of conditional Asian options in comparison with regular Asian options. In the numerical examples, we put to the test some cost-benefit claims by practitioners. As a by-product, the work also presents some distributional properties of the occupation time and the time-integral of geometric Brownian motion during the occupation time.

**Friday, 29 May 2015, 1:00PM**-- DC 2314*Symbolic Computation Group PhD Seminar*-- Computer Science*Speaker:*Andrew Arnold, PhD candidate, David R. Cheriton School of Comp. Sci., Univ. Waterloo*Title:**"Algorithms for Sparse Polynomial Interpolation"*

*Abstract:*We consider the algebraic problem of polynomial interpolation: learning a representation of a polynomial from a set of evaluations. Interpolation is a fundamental tool of symbolic computation, and lends itself to fast polynomial arithmetic. We will focus our attention to the interpolation of sparse polynomials, i.e., polynomials which admit a concise representation. The aim of sparse interpolation is to reconstruct such a polynomial with cost measured in terms of the size of this concise representation. We present probabilistic techniques for sparse interpolation over a variety of evaluation models. As an application of these techniques, we give an asymptotically fast method for sparse polynomial multiplication.

**Friday, 29 May 2015, 3:30PM**-- MC 5501 true*Tutte Colloquium Seminar*-- Combinatorics and Optimization*Speaker:*Alexander Yong, University Illinois, Urbana-Champaign*Title:**"Eigenvalues of Hermitian matrices and Schubert calculus"*

*Abstract:*In the late 1990's the following old problem was solved: how does the condition A+B=C on triples of Hermitian matrices constrain their eigenvalues? Through the work of A. Klyachko, A. Knutson-T. Tao, K. Purbhoo-F. Sottile and many others, a connection was made and deepened between this problem and classical Schubert calculus. I will present a particular extension, relating an eigenvalue problem of S. Friedland to equivariant Schubert calculus. This is joint work with D. Anderson (Ohio State U.) and E. Richmond (Oklahoma State U).The proof is based on a factorial Schur function analogue of M.-P. Schutzenberger's theory of jeu de taquin, developed with H. Thomas (U. New Brunswick). In current work, with O. Pechenik (U. Illinois), we give a generalization to obtain a Littlewood-Richardson rule for the equivariant K-theory of Grassmannians.

* ...... WebNotice*