Archives: Friday, March 15, 2019

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

Read on »