## Organisers:

## Time:

## Venue:

## Webpage:

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.

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.

Swaprava Nath

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

How should a group of friends decide which movie to watch together or which restaurant to go for dinner? How should a municipal corporation decide which set of public projects to undertake?

Speaker:

Prerona Chatterjee, TIFR

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

The compactness theorem states that there is a model for an infinite set S of propositional formulas, if and only if, there is a model for every finite subset of S.

Speaker:

Anand Deo, TIFR

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

The Brownian motion is one of the most interesting and useful of all Stochastic Processes. It has an enormous range of applications ranging from physics (Einstein) to finance (starting with Bachelier).

Speaker:

Prahladh Harsha, TIFR

Tuesday, 30 August 2016, 16:30 to 17:30

In this talk, we will survey questions related to polynomial approximations of AC0.

Jenish Mehta

Friday, 12 August 2016, 16:00 to 17:30

Cheeger inequalities in spectral graph theory help to comment on the approximate connectivity or expansion of a graph (a combinatorial property) from the eigenvalues of the adjacency matrix of the graph (an algebraic property).

Mrinal Kumar

Tuesday, 23 August 2016, 16:00 to 17:00

We will show that there is a family of n- variate polynomials of degree d = O(log^2 n), which can be computed by linear sized homogeneous depth-5 arithmetic circuits, where as any homogeneous depth-4 circuit computing it must have size at least n^

Bruce Hajek

Thursday, 11 August 2016, 11:30 to 12:30

Detecting or estimating a dense community from a network graph offers a rich set of problems involving the interplay of algorithms, complexity, and information limits.

Animesh Kumar

Tuesday, 9 August 2016, 16:00 to 17:00

Remote sensing with a distributed array of stationary sensors or a mobile sensor has been of great interest.

Speaker:

Suhail Sherif, TIFR

Friday, 29 July 2016, 16:00 to 17:30

One of the famous open problems in randomized query complexity is the composition question: Is R(f o g) = Omega(R(f)R(g)) for all boolean functions f and g.