## Organisers:

## Time:

## Venue:

**Abstract:** Schaffer and Yannakakis have shown that the max-cut problem with the FLIP neighborhood is polynomial-time local search (PLS) complete, and hence among the most difficult problems in the PLS class.

Speaker:

Vidya Sagar Sharma, TIFR

Friday, 6 March 2020, 14:00 to 15:00

**Abstract:** Schaffer and Yannakakis have shown that the max-cut problem with the FLIP neighborhood is polynomial-time local search (PLS) complete, and hence among the most difficult problems in the PLS class.

Speaker:

Prabhat Kumar Jha, TIFR

Friday, 21 February 2020, 14:00 to 15:00

**Abstract: **The Skolem - Mahler - Lech Theorem states that given any linear recurrence sequence over any field of characteristic 0, the set of positions where 0 occurs is union of a finite set and finitely many arithmetic progressio

Sayantan Chakraborty

Friday, 14 February 2020, 14:00 to 15:00

Abstract:*The problem of approximate sampling using Markov Chain Monte Carlo has received considerable attention in the Theoretical Computer Science and Physics communities.

Speaker:

Tulasi mohan Molli, TIFR

Friday, 31 January 2020, 14:00 to 15:30

Details: We will finish the remainder of previous student talk. We will begin where we ended last time.

Speaker:

Tulasi mohan Molli, TIFR

Friday, 24 January 2020, 16:00 to 17:30

Abstract: The problem of list-decoding an error-correcting code is the following:

Speaker:

Prerona Chatterjee, TIFR

Friday, 17 January 2020, 16:00 to 17:30

Abstract: An Algebraic Branching Program (ABP) is a layered graph where each edge is labeled by an affine linear form and the first and the last layer have one vertex each, called the “start” and the “end” vertex respectively.

Speaker:

Vidya Sagar Sharma, TIFR

Friday, 27 December 2019, 17:15 to 18:15

**Abstract: **We study the complexity of simulating a neural network. We simplified the model of a neural network as a directed graph $G(V,E)$, where the nodes represent the neurons.

S. Venkitesh

Friday, 6 December 2019, 14:30 to 15:30

**Abstract:** The probabilistic degree of a Boolean function f is defined to be the smallest d such that there is a random polynomial P of degree at most d that agrees with f at each point with high probability.

Speaker:

Anamay Tengse, TIFR

Friday, 29 November 2019, 17:15 to 18:15

**Abstract: **Say we are "given" a set of matrices S, such that for any two matrices A and B from S, we have AB=BA. What kind of "structure" can we assume for the matrices in S?

Speaker:

Kumar Saurav, TIFR

Friday, 22 November 2019, 17:15 to 18:15

**Abstract: **In distributed IoT paradigm, we often have cases where multiple nodes need to keep a common server updated with their status information.