## 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:

Tulasi mohan Molli, TIFR

Friday, 15 September 2017, 17:15 to 18:15

A boolean circuit is a natural model of computation for Boolean functions. Size and Depth of a circuit are two measures of complexity of the circuit.

Praneeth Netrapalli

Tuesday, 19 September 2017, 16:00 to 17:00

There is widespread sentiment that it is not possible to effectively utilize fast gradient methods (e.g.

Speaker:

Gunjan Kumar, TIFR

Friday, 8 September 2017, 17:15 to 18:15

We initiate the study of property testing of submodularity on the boolean hypercube. Submodular functions come up in a variety of applications in combinatorial optimization.

Chiranjib Mukherjee

Tuesday, 3 October 2017, 16:00 to 17:00

In a reasonable topological space, large deviation estimates essentially deal with probabilities of events that are asymptotically (exponentially) small, and in a certain sense, quantify the rate of these decaying probabilities.

Speaker:

Kavitha Telikepalli, TIFR

Tuesday, 5 September 2017, 16:00 to 17:00

The stable marriage problem consists of a bipartite graph $G = (A \cup B,E)$ where every vertex has a ranking of its neighbours in a strict order of preference. Every stable matching matches the same subset of vertices.

Speaker:

Gowtham Raghunath Kurri, TIFR

Friday, 1 September 2017, 17:15 to 18:15

Suppose we want to transmit messages across a noisy channel to a receiver. The maximum rate of transmission such that the receiver may recover the original message without errors (i.e., zero error) is called zero error capacity of the channel.

Speaker:

Neha ., TIFR

Friday, 18 August 2017, 17:15 to 18:15

In this talk, we will study the PhD-work of Risi Kondor in which he demonstrates how bispectrum invariants can be used to classify translated and rotated images.

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.