## Organisers:

## Time:

## Venue:

Propositional proof complexity is the study of the resources that are needed to prove formulas in propositional logic.

Speaker:

Marc Vinyals, TIFR

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

Propositional proof complexity is the study of the resources that are needed to prove formulas in propositional logic.

Speaker:

Varun Narayanan, TIFR

Friday, 10 November 2017, 17:15 to 18:15

We would discuss the lower bound on the joint entropy of pairwise independent random variables (X_1, ... , X_n) by Lazlo Babai (2013).

Speaker:

Anand Deo, TIFR

Friday, 3 November 2017, 17:15 to 18:15

The notion of control can be thought of as the process of selection of a policy to influence the dynamics of a system in order to achieve a desired objective.

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.