Archives: March 2019

The Curse of Euclidean Metric: Square Roots

By Renata Czarniecka The deadline was approaching without mercy and there was, of course, still some polishing to be done for our SODA paper. But then we run into an issue. To make things worse, this issue turned out to be a hard one, a fundamental known open problem in computational geometry. …read more From::

Read on »

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 »