Tata Institute of Fundamental Research
Membership Problem in Bit Probe Model
STCS Student Seminar
Speaker:
Vidya Sagar Sharma
Organiser:
Somnath Chakraborty
Date:
Friday, 20 Oct 2017, 17:15 to 18:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Storing sets is a common problem in Computer Science. Given a set S (subset of a universal set U), we have to store it using some data structure so that it do not take much space and membership queries can be done quickly. There is an open problem (by J.Radhakrishnan) that for |S|=2 and for number of probe at most 2 the space required to store S will have lower bound \Omega($m^{2/3}$). We have shown that for class of algorithms under certain restriction(s), space have the lower bound \Omega($m^{2/3}$).
| Speaker: | Vidya Sagar Sharma |
| Organiser: | Somnath Chakraborty |
| Date: | Friday, 20 Oct 2017, 17:15 to 18:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Storing sets is a common problem in Computer Science. Given a set S (subset of a universal set U), we have to store it using some data structure so that it do not take much space and membership queries can be done quickly. There is an open problem (by J.Radhakrishnan) that for |S|=2 and for number of probe at most 2 the space required to store S will have lower bound \Omega($m^{2/3}$). We have shown that for class of algorithms under certain restriction(s), space have the lower bound \Omega($m^{2/3}$).