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.