Penn Arts & Sciences Logo

Applied Topology Seminar

Monday, March 13, 2017 - 3:00pm

Blair Sullivan

North Carolina State University


University of Pennsylvania


Note unusual day and room.

Rumor has it that one of the big challenges facing topological data analysis is the high computational complexity (and associated lack of scalability) of key methods. This talk will introduce the toolkit of parameterized algorithms for efficiently solving NP-hard problems, with examples drawn from network science. We will discuss how these approaches can exploit properties of the desired solution, structural features of the input, or even knowledge about solutions to other problems on the same network. Given the venue, we will go out of our way to define structural sparsity using topological minors and highlight some of our group's recent work on applications in computational biology. No background in parameterized complexity (or topology) will be assumed; bring your algorithmic challenges and come see if tractability is just a parameter away.