## Speaker:

## Organisers:

## Time:

## Venue:

## Webpage:

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

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.

Nutan Limaye

Tuesday, 28 November 2017, 16:00 to 17:00

The complexity of Iterated Matrix Multiplication is a central theme in Computational Complexity theory, as the problem is closely related to the problem of separating various complexity classes within $P$.

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

Speaker:

Sayantan Chakraborty, TIFR

Friday, 24 November 2017, 17:15 to 18:15

Entanglement is an important resource in quantum communication protocols and as such the problem of turning a preshared entangled state between two parties Alice and Bob into a Bell state has been studied extensively.

Speaker:

Marc Vinyals, TIFR

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

Propositional proof complexity is the study of the resources that are needed to prove formulas in propositional logic.

Speaker:

Varun Narayanan, TIFR

Friday, 10 November 2017, 17:15 to 18:15

We would discuss the lower bound on the joint entropy of pairwise independent random variables (X_1, ... , X_n) by Lazlo Babai (2013).

Sagnik Mukhopadhyay

Thursday, 9 November 2017, 14:30 to 15:30

Speaker:

Anand Deo, TIFR

Friday, 3 November 2017, 17:15 to 18:15

The notion of control can be thought of as the process of selection of a policy to influence the dynamics of a system in order to achieve a desired objective.

Speaker:

Sumedh Vinod Tirodkar, TIFR

Friday, 27 October 2017, 17:15 to 18:15

We consider the maximum matching problem in the semi-streaming model formalized by Feigenbaum et al.

Dr. Ramprasad Saptharishi joins the School of Technology and Computer Science as a Reader. Ramprasad's research interests include Arithmetic complexity, pseudorandomness and derandomization.

Dr. Umang Bhaskar joins the School of Technology and Computer Science as a Reader.

- ‹ previous
- 4 of 15
- next ›