## Organisers:

## Time:

## Venue:

Nisan gave an exact characterization of the ``non-commutative algebraic branching program (ABP) complexity'' of a polynomial in 1991.

Speaker:

Anamay Tengse, TIFR

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

Nisan gave an exact characterization of the ``non-commutative algebraic branching program (ABP) complexity'' of a polynomial in 1991.

Santhoshini Velusamy

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

This paper is joint work with Venkatesan Guruswami and Ameya Vellingker, to appear in APPROX 17.

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:

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:

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