Wednesday, March 14, 2018
Public Access

Category: All

March 2018
Mon Tue Wed Thu Fri Sat Sun
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31  
11:00am [11:30am]Anand Srivastav Department of Mathematics Kiel University, Germany
Combinatorics Seminar Date & Time: Wednesday, 14th March, at 11:30am Venue: Ramanujan Hall Title: Derandomizing Martingale Inequalities with Applications to Hypergraph Vertex Covering Speaker: Anand Srivastav Department of Mathematics Kiel University, Germany Abstract: In this talk we present a derandomized form of the famous martingale inequality of Kazuoki Azuma (1967), and the bounded differences inequality of Colin McDiarmid (1988) based on it. We further show how to embed limited independence in the concentration bounds of Angluin-Valiant, motivated by work of Svante Janson (2003) on sums of partially dependent random variables for the Chernov-Hoeffding inequality. We then demonstrate that the derandomized McDiarmid-inequality is an easy applicable and elegant frame work for derandomization in presence of dependent random variables. As an example we choose the randomized algorithm for the vertex cover (or hitting set) problem in hypergraphs due to Mourad El Ouali, Helena Fohlin and Anand Srivastav (2016), which for hypergraphs with bounded vertex degree gives the presently best approximation bounds. This is joint work with Mayank.

2:00pm [2:00pm]Mithun Bhowmick (Postdoc candidate)
Analysis Seminar Speaker: Mithun Bhowmick (Postdoc candidate) Date & time: Wednesday 14th March, 2-3 pm Venue: Ramanujan Hall Title: Theorems of Ingham, Levinson and Paley-Wiener on certain Lie groups Abstract: In this talk, our focus will be on certain classical results due to Ingham, Levinson and Paley-Wiener which find optimal decay of the Fourier transform of nonzero functions vanishing on `large sets'. We will talk about these theorems in details and their generalisations on the $n$- dimensional Euclidean space, the $n$-dimensional torus and certain non-commutative Lie groups.