Tata Institute of Fundamental Research
The Isolation Lemma
Student Seminar
Speaker:
Girish Varma
Organiser:
John Barretto
Date:
Friday, 1 Jun 2012, 15:00 to 16:30
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Girish Varma |
| Organiser: | John Barretto |
| Date: | Friday, 1 Jun 2012, 15:00 to 16:30 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.