Fall 2020
Why are p-adic numbers useful for fast linear algebra algorithms?
Speaker: Silvia Casacuberta Puig
Abstract: p-Adic numbers have always been primarily associated with pure Mathematics, and have become especially relevant in algebra and modern number theory. But why did Computer Scientists become interested in them? In this talk we will introduce p-adic numbers and survey their main properties. We will then introduce Dixon’s algorithm, which is the first algorithm that used p-adic numbers to compute the exact rational solution to an integer linear system of equations. We will also explore the latest runtime improvements in p-adic linear algebra algorithms, and discuss whether we can solve linear equation systems faster than matrix multiplication.
Graduate School Panel
Abstract: Come learn about graduate school in Math, Physics, and Economics from former math concentrators.
The IO Monad
Speaker: Vinh-Kha Le
Abstract: The purest forms of functional programming use monads to define computations that happen within contexts. For instance, the IO monad, which is a standard object in Haskell as well as languages inspired by Haskell, is used to handle processes that require interaction with the outside world. Monads are the dread of many fledgling programmers learning functional programming for the first time, but they are actually familiar constructions from category theory. This talk will discuss the definitions of monad in functional programming and category theory and describe how they are manifested in the context of a Haskell program that reads in and prints an integer.
Superpowers and relativization in the theory of computational complexity
Speaker: Noah Singer
Abstract: Proving a result that’s more general than intended can often be a cause to celebrate! But it can also be a red flag, indicating that a particular technique is not incisive enough to tackle more advanced problems. In this talk, we’ll see one such situation, the notion of relativization in the theory of computational complexity. We’ll define what it means for a theorem to relativize — hold true even if computers are given superpowers — and describe the famous P vs. NP problem and why it cannot be resolved by relativizing techniques. If we have time, we’ll sketch a proof of the time hierarchy theorem, a nice example of a relativizing theorem.
The Combinatorics of Rhombic Polygon Tilings
Speaker: Hanna Mularczyk
Abstract: