- Monday, 8 February 2016, 9:00AM -- MC 5417
- Seminar -- Combinatorics and Optimization
- Speaker: Michaela Rombach, University of California
Title: "Graph representatives of positroid strata (juggling meets quantum physics)"
Abstract: In 2013 Knutson, Lam and Speyer showed that the poset of bounded juggling patterns is isomorphic to the poset of positroids. Bounded juggling patterns are affine permutations that satisfy , for all . Positroids are a class of matroids, introduced by Alexander Postnikov, that arise from matrices of rank with real entries such that all maximal minors are nonnegative. Positroids have many nice properties. For example, they are closed under restriction, contraction, and duality. There is a map from graphs to matroids that is not onto, creating the class of so-called graphic matroids, where the independent sets of the matroid are the forests in the graph. We show that every juggling pattern and therefore positroid stratum in the Grassmannian has a planar graph representative, using planar bicolored (plabic) graphs. These diagrams are at the heart of a recent breakthrough in particle physics as they present a new type of Feynman diagram that computes scattering amplitudes.
Joint work with Allen Knutson.
- Monday, 8 February 2016, 10:30AM -- DC 1304 true
- Seminar -- Computer Science
- Speaker: Matthew Kay, University of Washington
Title: "Designing for user-facing uncertainty in everyday sensing and prediction"
Abstract: We are increasingly exposed to sensing and prediction in our daily lives (“how many steps did I take today?”, “how long until my bus shows up?”, “how much do I weigh?”). Uncertainty is both inherent to these systems and usually poorly communicated—or not communicated at all. However, understanding uncertainty is necessary to make informed decisions from data: if my scale says I am a pound heavier today than yesterday, how does that compare to the expected variance of my weight? If my bus is predicted to arrive 10 minutes from now, what is the chance the bus instead shows up early, in 5 minutes—and therefore, do I have time to get a coffee? In this talk, I overview several projects I have undertaken to investigate how people deal with uncertainty in their everyday data and how we can build systems that convey uncertainty in a way they can understand. I will touch upon several domains, including weight tracking, sleep quality, and realtime transit prediction. I argue that how people interpret their data and what goals they have should inform the way that we communicate results from our models, which in turn determines what models we must develop and use in the first place. As we push more sensing and prediction into people’s everyday lives, we must consider carefully how to communicate estimates that people can actually use to make informed decisions.
Matthew Kay is a PhD Candidate in Computer Science & Engineering at the University of Washington. His research in human-computer interaction (HCI) spans many application domains, from personal health informatics, to communicating uncertainty in everyday sensing and prediction, to advancing the state of statistical methods in HCI. He draws upon qualitative and quantitative methods across HCI, information visualization, and statistics. He holds a Master's and a Bachelor's in Computer Science (minor in Fine Art) from the University of Waterloo.
- Tuesday, 9 February 2016, 1:00PM -- MC 5479
- Geometry Working Seminar -- Pure Mathematics
- Speaker: Spiro Karigiannis, Department of Pure Mathematics University of Waterloo
Title: "“Weyl curvature, conformal geometry, and uniformization: Part III”"
Abstract: We complete our introduction to conformal geometry this week. We start by completing the proof that, if (M,g) is a compact Riemannian manifold with strictly negative scalar cur- vature, then there exists a conformal metric with constant negative scalar curvature, using the maximum principle, the basic estimates of elliptic regularity, and the continuity method. These are all basic important tools in geometric analysis. Then we use this result to establish the Yamabe theorem in dimension n = 2 for genus k 1. The case k = 0 is slightly different, and we discuss this as well. Finally, we relate these results in dimension n = 2 to the classical uniformization theorem of complex analysis.
- Tuesday, 9 February 2016, 3:00PM -- MC 6486
- Graduate Student Seminar Seminar -- Combinatorics and Optimization
- Speaker: Speaker #1: Christopher van Bommel, Speaker #2 Vishnu Narayan, University of Waterloo
Title: "Speaker #1: Mutually Orthogonal Latin Squares with Large Holes, Speaker #2 On the extreme points of the subtour LP for TSP"
Abstract: Speaker #1 Abstract:
Euler's 36 Officers Problem looks for orthogonal Latin squares of order 6. Such squares do not exist; however, a pair of incomplete orthogonal Latin squares of order 6 does exist. Such squares result if we allow a common 22 empty subarray of each square. We then avoid using a common two symbols in any row or column with an empty cell and make a natural extension to orthogonality. In general, this definition of incomplete mutually orthogonal Latin squares further extends to any order v, any hole size n, and any number of squares t, denoted t?IMOLS(v;n). While such sets of squares have been previously explored for small values of t, we demonstrate an asymptotic result for the existence of t?IMOLS(v;n) for general t requiring large holes, which we develop from our results on incomplete pairwise balanced designs.
Speaker #2 Abstract:
We consider structural properties of the extreme points of the subtour-elimination linear program relaxation for the travelling salesman problem, by presenting a recent proof by Nagarajan, Ravi and Singh (O.R.Letters 2010), of a known result due to Boyd and Pulleyblank: Every extreme point x of the LP has an edge of x-value one. The technique used
in this proof is due to Jain (2001) and has led to many new results in the last few years.
- Tuesday, 9 February 2016, 3:30PM -- MC 5403
- Berkovich Spaces Seminar -- Pure Mathematics
- Speaker: Jason Bell, Department of Pure Mathematics University of Waterloo
Abstract: We start chapter 2 of Ducros’ Bourbaki paper.
- Wednesday, 10 February 2016, 3:30AM -- MC 5403
- Computability Learning Seminar -- Pure Mathematics
- Speaker: Michael Deveau, Department of Pure Mathematics University of Waterloo
Title: "“Bases for ML-Randomness”"
Abstract: We briefly recall the definition of a base for ML-randomness presented last time. The remaining portion of the talk will be spent stating and proving an important result about such sets, namely that every base for ML-randomness is low for K.
- Wednesday, 10 February 2016, 9:00AM -- MC 5417
- Seminar -- Combinatorics and Optimization
- Speaker: Karen Yeats, Simon Fraser University
Title: "Trees, chord diagrams, and the renormalization group equation"
Abstract: How far can we get in understanding perturbative expansions in quantum field theory combinatorially?
This understanding begins with a connection between classes of rooted trees and Dyson-Schwinger equations in physics. Then I will discuss a family of such equations where we understand the perturbative expansion precisely via an expansion indexed by chord diagrams. The renormalization group equation of physics corresponds in this context to a classical recurrence of chord diagrams. Finally, looking more generally, we lose precise control on the whole expansion but retain a combinatorial understanding of the renormalization group equation by returning to rooted trees.
- Wednesday, 10 February 2016, 1:30PM -- DC 1304
- Algorithms and Complexity Group PhD Seminar -- Computer Science
- Speaker: Hamideh Vosoughpour Yazdchi, David R. Cheriton School of Computer Science
Title: "Straight-line Morphing"
Abstract: "Morphing" is the standard term used since the 80s to address the
continuous transformation between shapes while some properties are
maintained all the time during this transformation. Morphing is used
in computer graphics and animation, and also includes reconfiguration
problems such as linkage unfolding, and morphing between two different
graph drawings or triangulations. In this talk I will review some of
these morphing problems and will focus on "straight-line morphing".
Straight-line morphing is a continuous transformation of a planar
graph drawing from an initial straight-line drawing to a final
straight-line drawing in which planarity is preserved, and each vertex
moves on the straight-line segment connecting its initial position to
its final position without backtracking. There is freedom to move the
vertices at different speeds along their straight-line segments. We
will give some algorithms and some NP-hardness results on
straight-line morphing of disjoint segments.
This is a joint work with Anna Lubiw.
- Wednesday, 10 February 2016, 2:30PM -- MC 5403
- Algebra Seminar -- Pure Mathematics
- Speaker: Tyrone Ghaswala, Department of Pure Mathematics, University of Waterloo
Title: "“The Superelliptic Covers and the Lifting Mapping Class Group”"
Abstract: Given a finite sheeted (possibly branched) covering space over a surface, one can ask the following question: Which homeomorphisms of the base space lift to homeomorphisms of the total space? If we take the quotient of this question by isotopy, it becomes a much more interesting one: What can we say about the subgroup of the mapping class group of the base space that consists of isotopy classes of homeomorphisms that lift to the total space? This subgroup is the lifting mapping class group.
This question was completely answered by Birman and Hilden when the deck group is the two element group generated by a fixed hyperelliptic involution. In this case, everything lifts. Interestingly, this does not happen in general.
This talk will focus on the superelliptic covers, which are n-sheeted generalisations of the 2-sheeted covering spaces studied by Birman and Hilden. In particular, a technique for computing presentations and the index of the lifting mapping class group will be developed. These have a large potential to be applied to many more families of covering spaces.
No familiarity with the mapping class group of a surface will be assumed. This is joint work with Rebecca Winarski.
- Wednesday, 10 February 2016, 2:30PM -- MC 5479
- Fractal Geometry Seminar -- Pure Mathematics
- Speaker: Dr. Jozsef Vass, York University
Title: "“A Constructive Approach to the Convex Hull of IFS Fractals in the Plane, and its Generalization”"
Abstract: Determining the extremal points of IFS fractals, is both an intriguing theoretical problem which may serve the resolution of other theoretical questions, as well as a practical tool for computational geometric algorithms. Former results address the special case of self-affine tiles via eigenvectors of powers of the scaling matrix, however an alternate novel approach is necessary for the broader class of similitude IFS fractals. We show the finiteness of extrema for the special though quite general planar subclass of ”fractals of unity”, along with the constructive determination of their convex hull. The overall technique, as well as the steps to be overcome in the generalization of this convex hull determination method beyond the plane, will be hereby addressed. The method builds upon the work of Wang, Kirat, and Mandelbrot et al. The latter’s work on self-contacting fractal trees highlights the relevance of the loci of extrema to the much-researched problem of connectedness.
- Thursday, 11 February 2016, 10:30AM -- DC 1304
- Seminar -- Computer Science
- Speaker: Dr. Chen Qian, University of Kentucky
Title: "Networking the Internet and Things"
Abstract: The Internet of Things (IoT) is a new computing paradigm in which massive uniquely addressable objects are connected to the Internet using sensing devices such as RFID tags. IoT enables numerous innovations and new applications in big data, logistics, warehousing, smart cities, healthcare, etc. In this seminar, I will introduce our research that focuses on the networking problems of IoT, including data collection and exchange. We develop secure and trustworthy sensing systems with RFID and WiFi. In particular I will present the design and implementation of a physical layer identification system, GenePrint, that solves a fundamental security problem of RFID: how to defend against ID spoofing. In addition, our research on scalable and reliable Internet and Cloud networks enhances the infrastructure of IoT. I will introduce our recent work about a memory-efficient and fast forwarding information base that supports a huge amount of networked devices with location-independent identifiers. Our so10lution uses the smallest memory and achieves fastest query speed compared to existing methods, providing an important basis for many new network architectures. I also show how our research improves other aspects of IoT.
Chen Qian is an Assistant Professor in the Department of Computer Science at University of Kentucky. He received his Ph.D from the University of Texas at Austin in 2013, M.Phil. from Hong Kong University of Science and Technology in 2008, and B.Sc. from Nanjing University in 2006, all in Computer Science. He has served in the organizing committees and technical program committees of a number of conferences, including the TPC co-chair of ACM CSAR (with SenSys'16), TPC track chair of ICCCN'16, TPC co-chair of ICNP student workshop 2013, and TPC member of ICNP, INFOCOM, ICDCS, IWQoS, etc. He is an editor of the Cyber-Physical Systems Journal. He received the Best Paper Award of ACM MSCC 2015, the National Science Foundation CISE Research Initiation Initiative Award in 2015, and the James Browne Fellowship in 2012. His research interests are in a wide range of topics of networked systems, including Internet of Things, Software Defined Networking, Network Functions Virtualization, mobile computing, and cloud computing.
- Thursday, 11 February 2016, 12:30PM -- DC 1304
- Database Research Group Seminar -- Computer Science
- Speaker: Philipp Unterbrunner, Snowflake Computing
Title: "The Snowflake Elastic Data Warehouse"
Abstract: Snowflake is building a next-generation data processing solution which combines cutting-edge database technology with software-as-a-service aspects. We’re a young company with an already-proven track record: multiple production customers, industry awards, and several successful rounds of funding.
Snowflake offers an opportunity to work on challenging problems ranging from data storage and processing, through distributed systems running on hundreds of machines to a large-scale, always-on SaaS platform with modern user interfaces. We manage petabytes of data and run millions of analytical queries every day. With Snowflake's ease of use, rich functionality, high performance and enterprise-grade stability and security, we provide our users with a product they love.
Snowflake’s all-star technical team works closely with a highly experienced business organization, supported by top venture capital firms in Silicon Valley. Our (beautiful!) office is located in San Mateo, California. We blend a lot of hard work with a culture that thrives on its diverse people and opinions, while making sure we also have fun. Learn more at http://snowflake.net
- Thursday, 11 February 2016, 3:30PM -- MC 6486
- Algebraic Graph Theory Seminar -- Combinatorics and Optimization
- Speaker: Harmony Zhan, University of Waterloo
Title: "Quantum walks and graph embeddings"
Abstract: A discrete-time quantum walk is a walk on the arcs of a
graph. Along with the graph structure, additional information is needed to define a discrete walk. We will study one of the four models where the additional information is related to an embedding of the graph, and see how properties of quantum walks reflect properties of graph embeddings.
- Thursday, 11 February 2016, 4:30PM -- MC 5417
- Graph Theory Seminar -- Combinatorics and Optimization
- Speaker: Luke Postle, University of Waterloo
Title: "Claw decompositions of random 4-regular graphs"
Abstract: In 2005, Barat and Thomassen conjectured that the edges of every planar 4-regular 4-edge-connected graph can be decomposed into claws; shortly afterwards, Lai constructed a counterexample to this conjecture. Using the small subgraph conditioning method of Wormald, we show that a.a.s. a random 4-regular graph has such a claw decomposition. Joint work with Michelle Delcourt.
- Friday, 12 February 2016, 3:30PM -- MC 5417
- Analysis Seminar Seminar -- Pure Mathematics
- Speaker: Adam Dor On, Department of Pure Mathematics, University of Waterloo
Title: "“Matrix convex sets: Inclusions, dilations and completely positive interpolation”"
Abstract: A matrix convex set is a stratified set of the form S = ∪n≥1Sn, where each Sn is comprised of d-tuples of n × n matrices, and is closed under application of unital completely positive maps from Mn to Mk. Our main tools are polar duality in the sense of Effros and Winkler, and constructions of commuting normal dilations in the sense of Helton, Klep, McCullough and Schweighofer.
Given two matrix convex sets S and T , we find geometric conditions on S or on T , to ensurethatS1 ⊂T1 impliesS⊂C·T forsomeconstantC>0.
Under various symmetry conditions on S we can guarantee that C = d, the number of variables. We show that d is sharp for the maximal matrix ball Wmax(B ). We then find an
Our results have implications to spectrahedral inclusion problems studied by Helton, Klep, McCullough and Schweighofer, and to existence of interpolating unital completely positive
The first 20 minutes of this talk should be accessible to graduate students outside of
This is joint work with Ken Davidson, Orr Shalit and Baruch Solel.