How to identify m numbers using m/log m checks

By Renata Czarniecka

Here’s an old trick that we found useful for proving some tight complexity lower bounds. You are given m coins, each of weight either a or b, and a modern scale that can tell you the total weight of any chosen subset of coins. How many weighings do …read more

From:: Banach’s Algorithmic Corner

Submit a post

You can use the anonymous submission form to upload information about an event, a blog post or a job posting. It will be published when it is approved by the moderator.

Calendar

May 2025
M T W T F S S
 1234
567891011
12131415161718
19202122232425
262728293031  

Other Posts