School of Technology and Computer Science Seminars

The Isolation Lemma

by Mr. Girish Varma (School of Technology and Computer Science)

Friday, June 1, 2012 from to (Asia/Kolkata)
at Colaba Campus ( A-212 (STCS Seminar Room) )
Description
Isolation lemma is a technique used in randomized algorithms to reduce the number of solutions of a problem to one, should a solution exist. This is achieved by giving random weights to solutions and showing that there is a unique solution of minimal weight with constant probability. We will prove this lemma and use it to show that in a computational model called switching networks counting is not weaker than non determinism.