## Organisers:

## Time:

## Venue:

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

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.

Vidya Sagar Sharma

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

Storing sets is a common problem in Computer Science.

Apoorva Khare

Tuesday, 17 October 2017, 16:00 to 17:00

Given a graph $G$, let $\mathbb{P}_G$ denote the cone of positive semidefinite (psd) matrices, with non-negative entries, and zeros according to $G$. Which powers preserve psd-ness when applied entrywise to all matrices in $\mathbb{P}_G$?

Speaker:

Nikhil S Mande, TIFR

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

We use exponential sums to analyze the Fourier spectrum of functions of the type MOD_m^A (with output in {-1, 1}), for any constant m, and a general accepting set A. We will then see how this yields lower bounds on the number of monomials require

Speaker:

Anamay Tengse, TIFR

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

The polynomial identity testing task is to determine whether a given circuit computes the zero polynomial.

Shweta Agrawal

Monday, 23 October 2017, 14:30 to 15:30

Garbled circuits are a central primitive in cryptography. Intuitively, a garbled circuit enables its holder to evaluate a circuit on an input, so that the evaluator learns the output but learns nothing about the circuit or the input.

Ankit K.

Friday, 29 September 2017, 16:00 to 17:00

Logical relations are proof techniques that can be used to prove properties about languages like normalization, type safety, program equivalence and are closed under elimination.

Mukund Thattai

Tuesday, 10 October 2017, 14:30 to 15:30

We study the logistics system of eukaryotic cells, whose warehouses are micron-scale "organelles" and whose trucks are 10-nanometer-scale "vesicles". Organelles form the nodes and vesicle fluxes form the edges of a transport graph.

Nishad Kothari

Friday, 22 September 2017, 16:00 to 17:00

Valiant (1979) showed that unless $P = NP$, there is no polynomial-time algorithm to compute the number of perfect matchings of a given graph --- even if the input graph is bipartite.

Speaker:

Tulasi mohan Molli, TIFR

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

A boolean circuit is a natural model of computation for Boolean functions. Size and Depth of a circuit are two measures of complexity of the circuit.