Liling Ko

My research is in computability theory, where I study the computational complexities of countable objects. I explore questions such as: If a set of natural numbers is random enough to avoid being estimated by computable functions that are adaptive and monotone increasing, must the set necessarily avoid being estimated by all non-adaptive computable functions? Is it more computationally expensive to identify infinite cliques/anticliques in countable triangle-free graphs than in general countable graphs? Is this question related to the time needed to find maximal cliques/anticliques in triangle-free finite graphs?