## Organisers:

## Time:

## Venue:

**Abstract:** Given a graph $G$ with one source vertex $s$ and several target vertices, a shortest path tree rooted at $s$ is a subgraph of $G$ that preserves distances from $s$ to each of the target vertices.

Speaker:

Kshitij Gajjar, TIFR

Friday, 14 June 2019, 17:15 to 18:15

**Abstract:** Given a graph $G$ with one source vertex $s$ and several target vertices, a shortest path tree rooted at $s$ is a subgraph of $G$ that preserves distances from $s$ to each of the target vertices.

Speaker:

Anamay Tengse, TIFR

Friday, 7 June 2019, 17:15

A tree is said to be n-universal if it "contains" all binary trees with at most n leaves. A result of Chung, Graham and Coppersmith from 1981 shows that when this containment is via sub-graphs, an n-universal tree requires size n^Omega(log(n)).

Speaker:

Aditya Nema, TIFR

Friday, 31 May 2019, 17:15 to 18:15

**Abstract:** In a breakthrough, Hastings(2009) showed that there exists quantum channels whose classical Holevo capacity is superadditive i.e.

Speaker:

Suhail Sherif, TIFR

Friday, 24 May 2019, 17:15 to 18:15

**Abstract: **The first observation that one makes when analyzing communication protocols between Alice and Bob is that a cost c protocol partitions the input space into 2^c combinatorial rectangles.

Speaker:

Suhail Sherif, TIFR

Friday, 10 May 2019, 17:15 to 18:15

**Abstract:** In December 2001, David Moews held a programming contest to see whose short C program would return the largest number on a theoretical computer where the int datatype has no bounds.

Speaker:

Neha Sangwan, TIFR

Friday, 3 May 2019, 17:15 to 18:15

**Abstract:** A famous result of Ahlswede in the theory of Arbitrarily Varying Channels (AVCs) stated that the deterministic coding capacity of an AVC is either zero or is equal to its random coding capacity.

Abhishek Khetan

Friday, 19 April 2019, 16:00 to 17:00

**Abstract: **In this talk, we will state an prove the Minkowski's convex body theorem and see how it can be applied to prove Dirichlet's theorem on (simultaneous) diophantine approximation and to prove the fact that if p is prime wit

Speaker:

Suhail Sherif, TIFR

Friday, 12 April 2019, 17:15 to 18:15

**Abstract: **In a recent breakthrough work Kasper Green Larsen, Omri Weinstein and Huacheng Yu [1] proved the first superlogartithmic lowerbound for a dynamic data structure problem.

Speaker:

Prerona Chatterjee, TIFR

Friday, 5 April 2019, 17:15 to 18:15

**Abstract:** In the 1980s, Kaltofen proved one of the most remarkable results in algebraic complexity theory.

Speaker:

Prerona Chatterjee, TIFR

Friday, 15 March 2019, 17:15 to 18:15

**Abstract: **The best known lower bound for general algebraic circuits was given by Baur and Strassen [BS83].