Logic Seminar

Logic Seminar

Title: Coarse Computability

Speaker: Timothy McNicholl, Iowa State University

https://sites.google.com/site/timothymcnicholl/

Abstract: It is well known that many algorithms that have very bad worst-case behavior work well in practice.  This has lead to the consideration of average-case behavior.  However, average-case behavior is often very difficult to calculate.  This has led to the consideration of efficient algorithms that fail only on a set of asymptotic density 0; such an algorithm is said to compute coarsely.  Recently, coarse computability has been a topic of study in computability theory, and a number of interesting connections to important computability-theoretic concepts such as algorithmic randomness and genericity have been discovered.  I will discuss the basic definitions and results as well as some open problems.