karen lange

Title:  Climbing (or Finding Paths) through Trees: Computing the difficulty of mathematical problems

Time:  Friday,  8:00 PM - 9:00 PM

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.

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 undergraduate mathematics education and teaches a seminar on writing for the public about mathematics.  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.  She loves biking, hiking, cooking, and generally goofing off with her 9 year old and 5 year old kids (while her dog lounges on the couch).