Speaker: |
Kshitij Gajjar (IIIT Delhi) and Prerona Chatterjee (STCS, TIFR) |

Date: |
Friday, 11 Oct 2019, 17:15 to 18:15 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

In the first part of this talk, Kshitij will show how the different shortest paths in such a graph (for different values of $\lambda_1, \lambda_2, \ldots, \lambda_d$) can be thought of as the extreme points of a polytope in $d$ dimensions.

In the second part of this talk, Prerona will explain how to upper bound the number of extreme points in such polytopes. If time permits, she will show that improving this result can help solve some questions in algebraic circuit complexity.

This is based on joint work with Jaikumar Radhakrishnan and Vaishali Surianarayanan.