High Throughput Testing and TCS meets EDA

Several items caught my interest this week:

The latest document used by the french minister in charge of Research that is set to develop axes of research of national interest include:

"..Premier axe : santé, bien-être, alimentation et biotechnologies (analyses biologiques à haut débit, nanobiotechnologies, cohortes suivies sur vingt ans, robots d’aide aux personnes dépendantes)..."

The item of high throughput testing seems to get some traction at the policy level. While we are on the subject of high throughput testing, here is a recent arxiv preprint on the subject of compressive sensing and group testing: Boolean Compressed Sensing and Noisy Group Testing by George Atia, Venkatesh Saligrama (I featured it here).

The second item of interest is more general and concerns the view of theoretical people to applied problems. The US NSF recently had a workshop on Design Automation and Theory/Electonic Design Automation that drew theoretical researchers to look into the problems of chip engineering. Both Dick Lipton and Suresh Venkatasubramanian are well known researchers in the area of Theoretical Computer Science (TCS) and blogged about this in their respective blog:

• Dick Lipton's entry is entitled: NSF Workshop On Design Automation and Theory
• Suresh Venkatasubramanian's entry is entitled: NSF Workshop: Electonic Design Automation

In Suresh's entry, one can read:

A second thought was how the lessons of massive data analysis might be useful in the realm of DA. One speakr described one critical problem as being the degree of complexity associated with current DA tools: there are over 4000 "knobs" to turn in one such tool ! It's believed that these knobs are not independent, and might even be contradictory. If we think of each "run" of the DA tool, outputing some kind of chip layout, as a point in this 4000+ dimensional space, I wonder whether techniques for dimensionality reduction and manifold analysis might be useful to find a set of "core knobs" that control the process.

Let us note the issue of engineers having to deal with "4000 knobs," is an issue eerily similar to what the Experimental Probabilistic Hypersurface (EPH) seems to be solving for thermal hydraulics codes used in nuclear reactor simulations. I note that he has a similar view to mine about performing dimensionality reduction. An issue, that affects also the EPH, is setting up the right metrics between the "knobs".

Table: Parameters of the Cathare code as used in the EPH. From L'Hypersurface Probabiliste Construction explicite à partir du Code Cathare" by Olga Zeydina,

Group Testing and Compressive Sensing

As Bernard Beauzamy will present a paper at the Aerospace Testing, Design and Manufacturing 2009 Seminar in Munich, I was reminded that he refers to a testing procedure called "group testing" as a solution for companies to comply with the E.U. REACH regulations without incurring major financial losses.

There is a clear connection between group testing and compressive sensing, a subject area for which I perform some type of Technology Watch on a blog: http://nuit-blanche.blogspot.com . More information can be found in either the repository at Rice University or in the Compressive Sensing Big Picture page.

Initially, Group testing was used extensively by the U.S. Army in the 1940's in order to screen for syphilis in their troops. The procedure enabled enormous savings since the detection kits were pricey at the time. One can read the first few paragraphs of this report by Joel Tropp and Anna Gilbert on the connection between compressive sensing and group testing in Signal Recovery From Random Measurements via Orthogonal Matching Pursuit: The Gaussian Case. Also of interest is the video by Anna Gilbert who presented their latest results using this technique (CS + group testing) on bio chips called SNPs (in this experiment they do not use Gaussian matrices but rather sparser constructs called Expander Graphs). I pointed to it before and the video is here. While current results are OK for the time being, it may be difficult for this type of solution to convert the folks in pure bio research unless there is a tremendous savings for the detection of a certain disease. On the other hand, if there is an important financial gain and this testing procedure is Ok'ed by the proper regulation authorities, there is a likely chance that commercial companies could adopt this type of technique faster.