- When: Thursday, October 27, 2016 from 12:00 PM to 01:00 PM
- Speakers: Indranil Banerjee
- Location: Nguyen Engineering, Room 4201
- Export to iCal
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
This was discovered by Pettie and Ramachandran who gave an optimal (in the sense of decision tree complexity) MST algorithm on a pointer machine.
The speaker is a PhD candidate in Computer Science at GMU.Posted 1 year, 1 month ago