## Speaker:

## Time:

## Venue:

Suppose Prof. N is giving Mr. M an exam, and Mr. M doubts that a question on the exam paper is wrong. Mr. M asks Prof. N about it. Naturally Prof.

Girish Varma
School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road
<br

Friday, 10 July 2009 (All day)

Suppose Prof. N is giving Mr. M an exam, and Mr. M doubts that a question on the exam paper is wrong. Mr. M asks Prof. N about it. Naturally Prof.

Ajesh Babu
School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road

Friday, 3 July 2009 (All day)

The notion of communication complexity (CC) was introduced by Yao in 1979, who investigated the following problem involving two separated parties (Alice and Bob).

Dharma P. Agrawal
Department of Computer Science and Engineering
University of Cincinnati
United States of America

Thursday, 25 June 2009 (All day)

Mesh networks have become increasingly important because they can be easily implemented without much infrastructure and can support adequate bandwidth with a flexible multi-hop wireless communication among their routers serving the clients.

Satyadev Nandakumar
Iowa State University
USA
http://www.cs.iastate.edu/~satyadev

Friday, 12 June 2009 (All day)

Using Kolmogorob Complexity, we will prove that there exist an oracle with respect to which $P$ not equal to $NP$.

Benny George K.
School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road

Friday, 19 June 2009 (All day)

XZ=ZY is called the conjugacy equation. Given languages X and Y we are interested in knowing if there exists a non empty language Z which makes this equation true. This problem is undecidable in the general setting.

Kavita Ramanan
Department of Mathematical Sciences
Carnegie Mellon University
United States of America
h

Tuesday, 2 June 2009 (All day)

Many stochastic systems are governed by events that, though they have a small probability of occurrence, are crucial to performance.

Large deviations is an asymptotic theory that allows

Satyadev Nandakumar
Department of Computer Science
Iowa State University
United States of America
http://www.c

Thursday, 11 June 2009 (All day)

My talk focuses on two aspects of my thesis, in the theory of algorithmic randomness.

Raghav Kulkarni
University of Chicago
1100 E 58th Street
Chicago, IL 60637
United States of America
http:

Thursday, 17 September 2009 (All day)

A boolean function f on N variables is called evasive if its decision tree complexity is N, i.e., one must query *all* the variables (in worst case) in order to decide if f(X) = 1.

Pranab Sen
School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhaba Road
<

Tuesday, 16 June 2009 (All day)

Suppose we have a polynomial $P$ in variables $X_1, \\ldots, X_n$ with coefficients from a field $F$, with total degree at most $d$. The polynomial $P$ is given in terms of some algebraic expression involving $X_1, \\ldots, X_n$.