Wed, March 14, 2018
Public Access Category: All |
||||||||||||||||||||||
|
- Time:
- 11:30am
- Location:
- Ramanujan Hall, Department of Mathematics
- Description:
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.
- Time:
- 2:00pm-3:00pm
- Location:
- Ramanujan Hall, Department of Mathematics
- Description:
- 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.