Can we speed safely?

Often, algorithmic tasks can be greatly sped up for inputs that are promised to have certain structural properties, such as inputs that are assumed to be random, or to come from restricted classes of graphs. However, in practice, we rarely know if these promises hold, and verifying them can cost more than using a worst case algorithm. 

This talk surveys emerging lines of work that build trustworthy fast algorithms, by pairing speedups with weaker notions of testability. Our new algorithms, which either give an answer that is certified to be correct, or flag the input as one that does not satisfy the promised conditions, have complexities that are significantly faster than that of algorithms that do not rely on promises. 

This talk will discuss works that are joint with Arsen Vasilyan, Talya Eden, Cassandra Marcussen, and Madhu Sudan.