## Speaker:

## Organisers:

## Time:

## Venue:

## Webpage:

Valiant (1979) showed that unless $P = NP$, there is no polynomial-time algorithm to compute the number of perfect matchings of a given graph --- even if the input graph is bipartite.

Nishad Kothari

Friday, 22 September 2017,

16:00 to 17:00

Valiant (1979) showed that unless $P = NP$, there is no polynomial-time algorithm to compute the number of perfect matchings of a given graph --- even if the input graph is bipartite.

Speaker:

Kshitij Gajjar, TIFR

Tuesday, 22 August 2017,

16:00 to 17:00

In this talk, we will be introducing the topic of distance-preserving subgraphs, and presenting some of our own results on distance-preserving subgraphs for interval graphs (joint work with Jaikumar).

Krishnamurthy Iyer

Friday, 11 August 2017,

16:00 to 17:00

We consider the problem of optimal information sharing in the context of a service system. In particular, we consider an unobservable single server queue offering service at a fixed price to a Poisson arrival of delay-sensitive customers.

Madhu Sudan

Wednesday, 9 August 2017,

14:30 to 15:30

A martingale is a sequence of random variables that maintain their future expected value conditioned on the past. A $[0,1]$-bounded martingale is said to polarize if it converges in the limit to either $0$ or $1$ with probability $1$. A martinga

Arindam Khan

Thursday, 24 August 2017,

16:00 to 17:00

We study the two-dimensional geometric knapsack problem (2DK), a geometric variant of the classical knapsack problem.

Rahul Jain

Monday, 14 August 2017,

16:00 to 17:00

Compression of a message up to the information it carries is key to many tasks involved in classical and quantum information theory.

Rajesh Sundaresan

Thursday, 27 July 2017,

11:00 to 12:00

The talk will be on load balancing on a large graph. A unit of load on each edge of a graph is to be distributed between its nodes in a balanced way. On infinite graphs, it is known that the problem exhibits nonuniqueness.

Arijit Ghosh

Wednesday, 26 July 2017,

16:00 to 17:00

The packing lemma of Haussler (J. of Comb. Theory, Ser. A, 1995) states that given a set system with bounded VC dimension, if every pair of sets in the set system have large symmetric difference, then the set system cannot contain too many sets.

Rohit Gurjar

Tuesday, 1 August 2017,

16:00 to 17:00

We present a geometric approach towards derandomizing the Isolation lemma for a given family, i.e., deterministically constructing a weight assingnment which ensures a unique minimum weight set in the family.

Mayank Bakshi

Wednesday, 19 July 2017,

11:00 to 12:00

Modern communication networks present both significant challenges as well as opportunities that are distinct from traditional networks.