## Organisers:

## Time:

## Venue:

## Webpage:

We consider the unbounded error communication complexity of XOR functions, i.e. those of the form f of XOR, where f is an arbitrary boolean function on n bits.

Speaker:

Nikhil S Mande, TIFR

Friday, 21 October 2016, 16:00 to 17:30

We consider the unbounded error communication complexity of XOR functions, i.e. those of the form f of XOR, where f is an arbitrary boolean function on n bits.

Speaker:

Varun Narayanan, TIFR

Friday, 14 October 2016, 16:00 to 17:30

DNA sequencing is the basic workhorse of modern day biology and medicine.

Speaker:

Gunjan Kumar, TIFR

Friday, 7 October 2016, 16:00 to 17:30

We present algorithmic applications of an approximate version of Caratheodory's theorem.

Vijay G. Subramanian

Thursday, 24 November 2016, 14:00 to 15:00

The threshold model is widely used to study the propagation of opinions and technologies in social networks. In this model individuals adopt the new behavior based on how many neighbors have already chosen it.

Andrew Thangaraj

Tuesday, 29 November 2016, 16:00 to 17:00

Characterising the capacity of channels with memory is a challenging and interesting problem in information theory. One example is a channel with an input runlength constraint.

Sandeep Sen

Tuesday, 22 November 2016, 16:00 to 17:00

We develop new techniques for rounding packing integer programs using iterative randomized rounding. It is based on a novel application of multidimensional Brownian motion in $\mathbb{R}^n$.

Speaker:

Anamay Tengse, TIFR

Friday, 30 September 2016, 16:00 to 17:30

The max-coloring problem is to compute a legal coloring of the vertices of a graph $G=(V,E)$ with vertex weights $w$ such that $sum^k_{i=1} max_{v \in C_i} w(v_i)$ is minimized, where $C_1, \ldots ,C_k$ are the various color classes.

Manoj M. Prabhakaran

Tuesday, 18 October 2016, 16:00 to 17:00

We introduce a new information-theoretic complexity measure IC∞ for 2-party functions which is a lower-bound on communication complexity, and has the two leading lower-bounds on communication complexity as its natural relaxations: (external) infor

Speaker:

Sarat Babu Moka, TIFR

Wednesday, 21 September 2016, 11:30 to 12:30

As is well known, Monte Carlo methods are ubiquitous in many applied domains. One of the main uses of these methods is to study the long-time behavior of stochastic systems of interest.

Speaker:

Sagnik Mukhopadhyay, TIFR

Friday, 16 September 2016, 16:00 to 17:30

One of the basic questions in complexity theory is how the complexity of computing $k$ instances of a function relates to the complexity of computing a single instance.