Tata Institute of Fundamental Research
Streaming Algorithms using Finger Printing Technique
Student Seminar
Speaker:
Girish Varma
Tata Institute of Fundamental Research
School of Technology and Computer Science
Homi Bhabha Road
Date:
Friday, 4 Jun 2010 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Algorithms working on large data(say of size n) should be both space and time efficient. Any algorithm has to see atleast the whole data once, so time required has to be atleast n(see sublinear time algorithms for exceptions). Also it should use space much less than n(ie. o(n)). We will see a good technique for designing such algorithms and use it to solve two problems. First will be checking whether a string x can be derived from a grammar and the second one is to check whether a sequence of n numbers are exactly the out degrees of the corresponding vertices in an n vertex graph. Furthermore we will prove that the algorithms are optimal in their space usage(ie. being more space efficient is a mathematical impossibility) using techniques from communication complexity (joint work with Ajesh Babu and Nutan Limaye and is going to be presented next Monday at TAMC 2010).
| Speaker: | Girish Varma Tata Institute of Fundamental Research School of Technology and Computer Science Homi Bhabha Road |
| Date: | Friday, 4 Jun 2010 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Algorithms working on large data(say of size n) should be both space and time efficient. Any algorithm has to see atleast the whole data once, so time required has to be atleast n(see sublinear time algorithms for exceptions). Also it should use space much less than n(ie. o(n)). We will see a good technique for designing such algorithms and use it to solve two problems. First will be checking whether a string x can be derived from a grammar and the second one is to check whether a sequence of n numbers are exactly the out degrees of the corresponding vertices in an n vertex graph. Furthermore we will prove that the algorithms are optimal in their space usage(ie. being more space efficient is a mathematical impossibility) using techniques from communication complexity (joint work with Ajesh Babu and Nutan Limaye and is going to be presented next Monday at TAMC 2010).