You can use an oracle that gives you uniform samples from , and you can perform infinite precision arithmetic on these samples in unit time. That is, after accesses, item should have priority for an item of weight . Give a solution that does not explicitly keep track of the observed frequency. Show that there is no perfect hash family mapping from to of size polynomial in if . The Aethernet corporation has developed an exciting new protocol to let a collection of machines communicate on a shared wire.
Time is divided into fixed slots.
In a slot, any machine that wants to send information to another can broadcast it onto the wire. If more than one broadcast is attempted, none are successful. That is, we want . However, in each time slot, the set of machines might be different. In other words, show that if there are slots in which is one of the machines trying to broadcast, then with high probability, broadcasts in slots.