Tata Institute of Fundamental Research
What can one do with little memory?
Colloquium
Speaker:
Jaikumar Radhakrishnan
School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabh
Date:
Friday, 26 Jun 2009 (all day)
Venue:
AG-66
(Scan to add to calendar)
Abstract:
We will study computations performed with limited memory. This will bring us into contact with several ideas in the area of randomness and computation. We will illustrate these ideas using the following toy example.
The ASET coordinator orders cookies for all the 200 members in the audience. At the end, each member is allowed to take one cookie (this allowance is likely to be increased to two by the seventh pay commission). The coordinator has a piece of paper on which he can keep track of who all picked up cookies. The trouble is that the paper has space to store just about fifty check marks.
Can the coordinator ensure that nobody takes more than one cookie? (Answer: No)
If he does run out of cookies in the end, can he at least identify someone who took more than her share? (Answer: Yes)
| Speaker: | Jaikumar Radhakrishnan School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabh |
| Date: | Friday, 26 Jun 2009 (all day) |
| Venue: | AG-66 |
(Scan to add to calendar)
Abstract:
We will study computations performed with limited memory. This will bring us into contact with several ideas in the area of randomness and computation. We will illustrate these ideas using the following toy example.
The ASET coordinator orders cookies for all the 200 members in the audience. At the end, each member is allowed to take one cookie (this allowance is likely to be increased to two by the seventh pay commission). The coordinator has a piece of paper on which he can keep track of who all picked up cookies. The trouble is that the paper has space to store just about fifty check marks.
Can the coordinator ensure that nobody takes more than one cookie? (Answer: No)
If he does run out of cookies in the end, can he at least identify someone who took more than her share? (Answer: Yes)
The ASET coordinator orders cookies for all the 200 members in the audience. At the end, each member is allowed to take one cookie (this allowance is likely to be increased to two by the seventh pay commission). The coordinator has a piece of paper on which he can keep track of who all picked up cookies. The trouble is that the paper has space to store just about fifty check marks.
Can the coordinator ensure that nobody takes more than one cookie? (Answer: No)
If he does run out of cookies in the end, can he at least identify someone who took more than her share? (Answer: Yes)