Time: Monday's 3 pm - 4.30 pm
Link: https://meet.google.com/pdn-xsye-bsq
Resources: Use iitgoa email id for accessing video links to the talks.

Talks

#	Date	Talk details	Resource
		No talk scheduled for 11/10 and 18/10
17	4/10	Title: Equivalence checking methods for proving equivalence for scalar and array-handling programs Speaker: Sudakshina Dutta Abstract: Program equivalence is the problem of theoretically proving that two programs are functionally equal. In this presentation, a method of proving equivalence for scalar-handling programs and a method of proving equivalence for array-handling programs will be presented with simple examples. Also, the recent advances in this area will be briefly discussed.
16	27/9	Title: Estimation of finite mixtures of Gaussians via Bayesian sampling Speaker: Clint P. George Abstract: In this talk, I review the hierarchical model of the Bayesian mixture of Gaussians. I then present the popular Markov chain Monte Carlo method, Gibbs sampler, to generate samples from the posterior of the model. We also look at a toy example that illustrates the generative process of the model and the working of the Gibbs sampler. Reference: Estimation of Finite Mixture Distributions through Bayesian Sampling by Jean Diebolt and Christian P. Robert	video
15	20/9	Title: Learning regular sets from queries and counterexamples Speaker: Prince Mathew Abstract: In this talk, we address the problem of learning an unknown regular language using membership and equivalence queries. We assume that this regular language is presented by a minimally adequate teacher who can determine the membership of a word in that language. The teacher can also check a given language is not equal to the unknown regular language and provide a counterexample. We will discuss the L* algorithm, which correctly learns any regular language from the teacher using membership and equivalence queries in time polynomial in the number of states of the minimal DFA recognising the regular language and the length of the longest counterexample provided by the teacher. Reference: Angluin's seminal paper	video
14	13/9	Title: Mixture models and inference II Speaker: Clint George continues Clint's hand-notes	video
13	6/9	Title: Mixture models and inference I Speaker: Clint George Abstract: This talk looks at some popular mathematical models such as k-means clustering and probabilistic mixtures of Gaussians for grouped, continuous data. We see that we can derive an efficient iterative scheme for k-means clustering via error minimization. We set up a Bayesian approach for the mixture of Gaussians, but we will see that exact posterior inference is intractable. We thus discuss a posterior inference scheme based on Markov chain Monte Carlo methods. Clint's hand-notes	video
		No talk scheduled for 23/8 and 30/8
12	16/8	Title: Isolation lemma Speaker: Sreejith A. V. Abstract: In this talk, we look at the Isolation lemma of Mulmuley, Vazirani and Vazirani. The lemma helps one randomly reduce number of solutions of an NP problem to one. It has various applications in computational complexity and randomized algorithms. See the lecture notes by Amnon Ta-Shma and Dean Doron	video
11	9/8	Title: Vapnik–Chervonenkis theory VI Speaker: Satyanath Bhat	video scribe
10	2/8	Title: Vapnik–Chervonenkis theory V Speaker: Satyanath Bhat	video scribe
9	26/7	Title: Vapnik–Chervonenkis theory IV Speaker: Satyanath Bhat	video scribe
8	19/7	Title: Vapnik–Chervonenkis theory III Speaker: Satyanath Bhat	video scribe
7	12/7	Title: Vapnik–Chervonenkis theory II Speaker: Satyanath Bhat	video scribe
6	5/7	Title: Vapnik–Chervonenkis theory I Speaker: Satyanath Bhat Abstract: Vapnik–Chervonenkis theory provides a characterization of when a learning model is feasible. In this series, we will go through the VC theory systematically. We will assume basic probability. For example, see chap 1-3 from Ross, Sheldon M. Introduction to probability models (9th edition). Besides this no further background is assumed. Simulation of polynomial noiseless demo: colab link and pdf	video notes
5	28/6	Title: An algebraic characterisation of first-order logic with neighbour Speaker: Amaldev Manuel Abstract: The aim of the talk is to shed some light on the basic concerns of the logic-algebra discipline. As an example I will take the logic FO(N) and describe an algebraic characterisation for it. We will only assume familiarity with regular languages.	video notes
4	21/6	Title: Hypersafety Verification and Programming Assignment Evaluation Speaker: Kumar Madhukar (TCS Research) Abstract: In this talk, I will relate the problem of hypersafety verification to that of evaluating programming assignment submitted by a student (wrt a reference implementation provided by the teacher). I will present Ron et al.'s self-composition technique for hypersafety verification, explain its applicability for assignment evaluation, and propose an enhancement that makes their technique fully automatic. Reference: Property Directed Self Composition by Ron et. al.	video talk pdf
3	14/6 18/6	Title: The ellipsoid method for solving linear programming Speaker: Sreejith A V Abstract: In this talk, we look at the ellipsoid method for solving linear programming. This is a polynomial time algorithm. Reference: 1) Introduction to Linear Optimization by D. Bertsimas and J.N. Tsitsiklis, Chapter 8 2) Combinatorial Optimization by Papadimitriou and Steiglitz, Chapter 8	video 1 video 2 notes
2	7/6	Title: Exploiting the spatial dimension of big data jobs for efficient cluster job scheduling Speaker: Akshay Jajoo
1	1/6	Title: Approximation Guarantee for the Max-Cut Problem using Semi-Definite Programming Speaker: Divya Padmanabhan Abstract: The Max-Cut problem is a well studied graph theoretic problem where one is interested in finding the cut of the largest value in a given graph. While the problem is NP-hard, it finds several applications in clustering, VLSI design, and more generally in network domains. For many years, various researchers had worked with different kinds of approximation techniques but could not get beyond a guarantee of 0.5. In 1995, Goemans and Williamson proposed an approximation using convex optimization (particularly with semi-definite programming) and were able to obtain a highly improved guarantee of 0.878. This is the best known approximation guarantee for the max-cut problem today. In this talk, I will briefly introduce semi-definite programming for those new to the topic and provide a proof of the Goemans-Williamson result. Reference: Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming by Goemans and Williamson. pdf	video notes