## Speaker:

## Organisers:

## Time:

## Venue:

## Webpage:

Randomness plays an important role across scientific disciplines. In theoretical computer science, there is a large body of work trying to understand the role of randomness in computation.

Ankit Garg

Wednesday, 10 January 2018, 14:30 to 15:30

Randomness plays an important role across scientific disciplines. In theoretical computer science, there is a large body of work trying to understand the role of randomness in computation.

George Varghese

Thursday, 28 December 2017, 16:00 to 17:00

Surveys reveal that network outages are prevalent, and that many outages take hours to resolve, resulting in significant lost revenue.

Edith Elkind

Monday, 11 December 2017, 10:00 to 11:00

Arrow's famous impossibility theorem (1951) states that there is no perfect voting rule: for three or more candidates, no voting rule can satisfy a small set of very appealing axioms.

Irit Dinur

Tuesday, 5 December 2017, 11:30 to 12:30

Nisan and Szegedy showed that low degree Boolean functions are juntas, namely, they depend only on a constant number of their variables.

Speaker:

Prahladh Harsha, TIFR

Thursday, 30 November 2017, 11:30 to 12:30

Agreement tests are a generalization of low degree tests that capture a local-to-global phenomenon, which forms the combinatorial backbone of most PCP constructions. In an agreement test, a function is given by an ensemble of local restrictions.

Lalitha Sankar

Thursday, 21 December 2017, 11:00 to 12:00

Preserving the utility of published datasets while simultaneously providing provable privacy guarantees is a well-known challenge.

Kavita Ramanan

Thursday, 21 December 2017, 16:00 to 17:00

The standard hard-core model on a locally finite graph describes a family of Gibbs specifications, parameterized by the so-called activity parameter. An important problem is to determine when the model has a unique Gibbs measure and when it exhib

Anand Srivastav

Monday, 27 November 2017, 10:15 to 11:15

We study the problem of finding an Euler tour in an undirected graph $G$ in the W-Streaming model with $\mathcal{O}(n\,\textrm{polylog}(n))$ RAM, where $n$ resp.\ $m$ is the number of nodes resp.\ edges of $G$. Our main result is the first one pa

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).