Title: Analysis and Complexity Theory
Date/Time: November 7th, 2016 @ 2:30 PM
Place: 223 Atanasoff Hall
Major Professor: Jack Lutz
Abstract:
Computer Science is typically associated with discrete mathematics. However, there has been great advancements in developing a theory of computation over continuous domains. In this talk I will present two research projects in this field. The first concerns continuous chemical reaction networks, a new model of chemical kinetics developed by Chen, Doty and Soloveichik. We prove that the reachability problem for this model can be determined in polynomial time. The second project studies the connection between classical theorems from analysis and algorithmic randomness. We first give a new notion of polynomial space randomness. We then show that the Lebesgue Differentiation Theorem characterizes this notion. Future directions will also be discussed.