•   When: Thursday, October 27, 2016 from 12:00 PM to 01:00 PM
•   Speakers: Indranil Banerjee
•   Location: Nguyen Engineering, Room 4201
•   Export to iCal

ABSTRACT:

In the first part of the talk I will introduce soft-heaps which was first proposed by Chazelle about 15 years ago.

Unlike classical heaps, in a soft-heap the keys may become corrupted which depends on the error rate $\epsilon$.

These perturbations on keys  help in reducing the entropy of the key set and help achieve constant amortize time for all heap operations except for insert, which takes $O(\log 1/\epsilon)$ time.

In the second part of the talk I will briefly discuss one of the more famous applications of soft-heaps for solving the Minimum Spanning Tree

(MST) problem.

This was discovered by Pettie and Ramachandran who gave an optimal (in the sense of decision tree complexity) MST algorithm on a pointer machine.

BIO:

The speaker is a PhD candidate in Computer Science at GMU.