Karen Lange (Wellesley College)
Bio: Karen Lange is the Theresa Mall Mullarkey Associate Professor of Mathematics at Wellesley College. In her research, she studies the “balance scales” used to calibrate computational information and applies these tools to measure the difficulty of algebraic problems. She’s also passionate about community-building and inclusion in mathematics, and she teaches a seminar on writing about mathematics for the public. She earned her undergraduate degree at Swarthmore College and her doctoral degree at the University of Chicago, and she completed an NSF Postdoctoral Fellowship at the University of Notre Dame.
Topic:
Title: Climbing (or Finding Paths) through Trees: Computing the difficulty of mathematical problems
Abstract: You can make a simple family tree by starting with a person at the root and then adding two branches for her parents, and then adding two branches for the parents of each of her two parents, and so on. Such a family tree is an example of a binary tree because each level of the tree has at most two branches. We’ll see that every binary tree with infinitely many nodes has an infinite path; this result is called Weak Kőnig’s Lemma. But just because we know a path exists, doesn’t mean we can find it. Given Weak Kőnig’s Lemma, it’s natural to ask whether we can compute a path through a given binary tree with infinitely many nodes. It turns out the answer to this “Path Problem” is “no”, so we say that the problem is not “computable”. But then what exactly is the computational power of this Path Problem?
Using the Path Problem as a test case, we will explore the key ideas behind taking a “computable” perspective on mathematics (over an “existence” one) and describe an approach for measuring the computational power of mathematical problems. We’ll see that the computational power of problems varies widely and studying problems’ power helps to illuminate what really makes problems “tick”.
This talk will highlight ideas from graph theory, theoretical computer science, and logic, but no background in any of these subjects is necessary.
