LESSWRONG
LW

All of Ben Champion's Comments + Replies

SARS-CoV-2 pool-testing algorithm puzzle
Ben Champion10

Would you be able to post this under answers? It seems to describe algorithms and their performance bounds in quite some detail and definitely deserves to be the top answer.

Reply
6gwern
It describes a lot of things, and I'm not sure which ones would be the right answer here. If anyone wants to read through and describe which one seems to best fit the corona problem, that'd be a better answer than just providing an enormous difficult-to-read monograph.
SARS-CoV-2 pool-testing algorithm puzzle
Answer by Ben Champion*30

[EDIT:

I see the monograph in gwern's post below makes the observation that group testing is a Boolean version of compressed sensing and references Gilbert et al. 2008 which I'm just reading - found a freely available version on Google Scholar. And more importantly, the monograph contains algorithms with similar bounds to CS.

READ GWERN'S POST BELOW FIRST

]

Some ideas...

This is can be seen as a nonlinear version of a compressed sensing problem (see here for a good "25 minute" intro to compressed sensing, or the Wikipedia article).

The ... (read more)

Reply