Please register for the event here.

Mina Dalirrooyfard

Fine-grained complexity: why we are stuck at certain running times

We measure the running time of problems as a function of the size of their input. On many problems such as finding the diameter of the graphs, we can achieve polynomial running time, and on many problems, such as various graph partitioning problems, the best algorithms run in exponential time. Through traditional complexity theory, for many problems, it is known whether the problem is polynomially solvable or it is NP-complete, hence unlikely to have a polynomial time algorithm. However, for problems with known polynomial-time algorithms, in many applications, it is important to know whether there might exist faster algorithms for the problem. For example, finding the diameter of the graph can be done in quadratic time via a simple algorithm. However, can one find a linear time algorithm for it? If not, why?
These types of questions are answered by “fine-grained complexity theory”. I will give an introduction to what fine-grained complexity is, what it has achieved and what techniques are mostly used. I will also introduce average-case fine-grained complexity, which aims to find the hardness of problems where the input comes from a random distribution, which is the more realistic use case of many problems. Finally, I will talk a bit about my research after grad school.

Tina Torkaman

TBC

June Barrow-Green

Ronald Ross and Hilda Hudson: A collaboration on the mathematical theory of epidemics

In 1916 the physician Ronald Ross published the first of three papers on the mathematical study of epidemiology or, as he called it, ‘pathometry’. The second and third of these papers appeared the following year co-authored with the mathematician Hilda Hudson.   At the time Hudson, who had ranked equivalent to the 7th wrangler in the 1903 Cambridge Mathematical Tripos, was known for her work on Cremona Transformations. So how and why did Hudson, a geometer, end up collaborating with Ross on the theory of epidemics? And what role did she play? In my talk, I shall discuss the nature and extent of their collaboration, as well as the genesis, content, and significance of their work.