Upcoming Talks
 Speaker : Ankita Sarkar
Title : Introduction to Parameterized Algorithms and the FPT Class of Problems
Time & Date : 6:30 PM on 21st November 2017 (Tuesday)
Venue : LH1
Abstract : In this talk we will introduce key concepts of Parameterized Algorithms. We show many NPhard problems to be Fixed Parameter Tractable (FPT) or randomizedFPT under some natural parameterizations, using key techniques like Kernelization and a few useful structures. A basic result will be proved.
We will briefly review the associated complexity theory, including FPT reductions and a rudimentary notion of hardness. To conclude, we motivate the "pointofregret" technique mentioned in Michael Fellows' talk at IMSc.
Required Background : Basic graph theory. A first course in Algorithms and NPhardness will help.
References used : Personal course notes from PEA2017; Parameterized Algorithms by Cygan et al; Hartung and Niedermeier 2013.
Past Talks (This semester)

November 2017
 Speaker : Nikhil Kalyanapuram
Title : Measurement and The SternGerlach Experiment
Time & Date : 9:30 PM on 17th November 2017 (Friday)
Venue : LH1
Abstract : The paradigmatic experiment to motivate quantum mechanics as a fundamental theory of particle dynamics is undoubtedly the SternGerlach experiment. The study of the SternGerlach experiment is carried out in an abstract setting, in the process withholding practical details in favour of a more theoretic treatment. Using this experiment as an exemplar, we see how measurement processes when observed in this light lead inexorably to a new description of particle dynamics. Familiarity with linear algebra will suffice to understand the talk and the relevant physical details will be covered during the lecture.

October 2017
 Speaker : Bishal Deb
Title : Chromatic Polynomials and Heaps of Pieces
Time & Date : 9:15 PM on 24th October 2017 (Tuesday)
Venue : LH1
Abstract : Stanley in 1973 proved that the number of acyclic orientations of an undirected graph is the value of its Chromatic Polynomial at (1) upto sign. In 1983 Greene and Zaslavsky showed that the number of acyclic orientations of an undirected graph with a unique sink at a fixed vertex is same as the coefficient of the linear term of the chromatic polynomial of the graph upto sign.
In 1969 Cartier and Foata defined commutation monoids (also known as trace monoids in Concurrency Theory). In 1985 Xavier Viennot came up with a geometric interpretation of commutation monoids in the form of Heaps of Pieces.
In this talk after a brief introduction to heaps of pieces we shall look at an involution on layer factorisations of heaps which we shall use to prove the theorems of Stanley. If time permits we shall either look at a variation to this involution which can be used to prove the result of Greene and Zaslavsky or we shall look at a survey of results on chromatic polynomials which can be proved using variations to this involution.
 Speaker : Pranjal Dutta
Title : Discovering the roots: Uniform closure results for algebraic classes under factoring
Time & Date : 9:30 PM on 21st October 2017 (Saturday)
Venue : LH1
Abstract : Newton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly. I willtalk about generalizing it to a matrix recurrence that approximates all the roots "simultaneously". I will also discuss an interesting property of multivariate polynomial factorization which shows that under a random linear transformation τ , f(τx) completely factors via power series roots. Combining these, I will establish that for an algebraic circuit f(x_1, . . . , x_n) of size s, each factor has size at most a polynomial in: s and the degree of the squarefree part of f. For the remaining time, I will talk about different model of interest when the given polynomial f is of degree poly(n) and can be computed by a formula (resp. Algebraic Branching Program) size n^{O(log n)} . I will show how to find a similar size formula (resp. ABP) factor in randomized poly(n^{log n})time.
This is based on joint work with Nitin Saxena (IIT Kanpur) and Amit Sinhababu (IIT Kanpur).

September 2017
 Speaker : Shravan Patankar
Title : Hilbert theorem 90
Time & Date : 9:15 PM on 17th September 2017 (Sunday)
Venue: LH1
Abstract:
In abstract algebra, Hilbert's Theorem 90 (or Satz 90) is an important result on cyclic extensions of fields that has many applications in number theory. We will follow Balwant Singh's book, introduce group cohomology and use it to prove the theorem.
Prerequisites: some familiarity with commutative and homological algebra.
 Speaker : Aalok Thakkar
Title: How nonregular are contextfree languages?
Subtitle: The theorems of Chomsky, Schützenberger, and Parikh
Time and Venue: 9:00 PM on 9th September 2017 (Saturday)
Venue : LH1
Abstract:
Did you think contextfree languages are totally different from regular languages? Or do you believe adding a stack to finite state automata is some unnatural construct that changes everything? Let us revisit the time when America funded language theory to realize that context free languages are not very different from regular languages. We present an analog of regular expressions for contextfree languages, the ChomskySchützenberger representation theorem (which essentially says that Dyck languages are the only contextfree languages that matter) and Parikh's theorem (which states that contextfree languages are regular up to rearrangement of letters.) These shall help us appreciate some subtle aspects of contextfree languages. Come to the talk and let CFLs light up your day!
Prerequisites: Working knowledge of context free languages will be sufficient.

August 2017
 Speaker : Sridhar Venkatesh
Topic : Category theoretic proof of the van Kampen theorem
Time & Date : 9:45 PM on 26th August 2017 (Saturday)
Venue : LH1
Abstract : The van Kampen theorem gives us a method to calculate the fundamental groups of spaces from smaller/simpler spaces. I will begin by talking about the classification of covers and then move on to give a functorial proof of the van Kampen theorem.
Absolutely essential prerequisites  Knowledge of group actions, categorical language (natural transformations, equivalence of categories), some familiarity with the fundamental group, covering spaces, path lifting, map lifting. These are essential and I will be using them freely.