What can one do with little memory?

Speaker: 

Jaikumar Radhakrishnan School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabh

Time: 

Friday, 26 June 2009 (All day)

Venue: 

  • AG-66

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)