## Organisers:

## Time:

## Venue:

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.

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

Speaker:

Varun Narayanan, TIFR

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

Suppose $A$ and $B$ are parties in a network and want to communicate with each other privately. This problem is trivial if $A$ and $B$ have a private communication link between them. What if there is no such link?

K. Gajjar, S. Bhandari

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

The Liars Game is a turn-based two-player game (lets call the two players Alice and Bob). The game is specified by two positive integers $k$ and $n$ which are known to both Alice and Bob.

Speaker:

Aditya Nema, TIFR

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

In this talk, we will discuss De Finetti representation theorem on exchangeable probability assignment, that provides an operational definition of the concept of an unknown probability in Bayesian probability theory, where probabilities are taken

Rakesh Venkat

Friday, 24 February 2017, 16:00 to 17:30

A two-player game is an important construct used in proving many hardness of approximation results.

Speaker:

Sayantan Chakraborty, TIFR

Friday, 17 February 2017, 16:00 to 17:30

The usual idea of compactness of a space is that if the space has an open cover then it has a finite subcover which is not very intuitive. In this talk we attempt to look at some equivalent characterisations of compact spaces.