## Time:

## Venue:

Around a week ago, a group of researchers* proved that the randomized query complexity of f composed with g is lower bounded by the product of the randomized query complexities of f and g, albeit with suboptimal parameters.

Speaker:

Suhail Sherif, TIFR

Friday, 9 June 2017, 17:15 to 18:15

Around a week ago, a group of researchers* proved that the randomized query complexity of f composed with g is lower bounded by the product of the randomized query complexities of f and g, albeit with suboptimal parameters.

Rakesh Pawar

Friday, 2 June 2017, 17:15 to 18:15

In this talk, we will see a proof of the snake lemma. The talk will assume a basic familiarity (group homomorphisms, kernels, cokernels, etc.) with group theory.

Speaker:

Sagnik Mukhopadhyay, TIFR

Thursday, 1 June 2017, 10:30 to 11:30

In the first part, we will consider the connection between two well-known complexity measures --- communication complexity and query complexity.

Speaker:

Ramprasad Saptharishi, TIFR

Friday, 26 May 2017, 17:15 to 18:15

During academic collaborations, we have different people working on a paper and the draft has a natural evolution. Most people are ok using a sync service like dropbox, or even just emailing tex sources to each other (gasp).

Speaker:

Siddharth Bhandari, TIFR

Tuesday, 13 June 2017, 11:00 to 12:00

Inclusion-Exclusion based methods will be presented for solving exactly some graph coloring and covering problems.

Speaker:

Prerona Chatterjee, TIFR

Friday, 19 May 2017, 17:15 to 18:15

In this talk, we look at a $n^1.6616$ lower bound for SAT on $n^{o(n)}$ space machines. The result is taken from the 2006 paper by Ryan Williams.

Shubhada Agrawal

Friday, 12 May 2017, 17:15 to 18:15

An individual is faced with several options while deciding to invest in a financial market. Some opportunities giving higher returns but carrying more risk while some being less risky and give lower returns.

Uma Girish

Friday, 5 May 2017, 17:15 to 18:45

The Van der Waerden Conjecture states that the permanent of a doubly stochastic matrix n x n matrix is at least n!/n^n, which is the case when each entry of the matrix is $1/n$.

Speaker:

Sumedh Vinod Tirodkar, TIFR

Friday, 21 April 2017, 17:15 to 18:15

Consider the following communication problem. Alice holds a graph $G_A = (P, Q, E_A)$ and Bob holds a graph $G_B = (P, Q, E_B)$, where $|P| = |Q| = n$. Alice is allowed to send Bob a message $m$ that depends only on the graph $G_A$.

Speaker:

Nikhil S Mande, TIFR

Friday, 14 April 2017, 16:00 to 17:30

In this talk, we will see how certain "degree hardness" properties of a function (e.g approximate degree, sign-degree) amplify to give us "monomial based" hardness properties of a certain "lift" (as defined by Krause and Pudlak (STOC '94)) of the