# Poster Session and Reception

Tuesday, February 14, 2012 - 4:15pm - 5:30pm

Lind 400

**Poster - Approximation for Nonunique Probe Selection**

Ding-Zhu Du (University of Texas)

Given a binary matrix $M$, find submatrix with the same number of columns and minimum

number of raws such that all boolean sums of at most $d$ columns are distinct. We show

that for any fixed $d$, this problem has no polynomial-time $o(\log n)$-approximation

unless NP-P. Meanwhile, some approximation algorithms are also presented.**Poster - Finding one of m defective elements**

Christian Deppe (Universität Bielefeld)

In contrast to the classical goal of group testing we want to find onw defective elements of $D$

defective elements. We examine four

different test functions. We give adaptive strategies and lower bounds for the number of tests.

We treat the cases if the number of defectives are known and if the number of defectives are bounded.**Poster - Upgraded Separate Testing of Inputs in Compressive Sensing**

Mikhail Malyutov (Northeastern University)

Screening experiments (SE) deal with finding a small number s Active

Inputs (AIs) out of a vast total amount t of inputs in a regressionmodel.

Of special interest in the SE theory is finding the so-called maximal rate

(capacity).

For a set of t elements, denote the set of its s-subsets by (s, t). Introduce

a noisy system with t binary inputs and one output y. Suppose

that only s themby a sequence of N trials resulting in outputs yN. Suppose a ‘(f,

)-

separating’ (N × t) matrix exists for N Nf (s, t,

) such that it allows

identifying the true s-subset of uniformly distributed AIs with probability

1 −

under analysis f : yN ! (s, t) of outputs. Nf (s, t,

)

admits equivalent definition in terms of random design matrices which

turn out to be asymptotically optimal under

> 0. The f-capacity

Cf (s) = limt!1(log t/Nf (s, t,

)) for any

> 0 is the ‘limit for the per-

formance of the f-analysis’.

We obtained tight capacity bounds [4], [5] by formalizing CSS as a special

case of Multi-Access Communication Channels (MAC) of information

transmission capacity region construction developed by R. Ahlswede

in [1] and comparing CSS’ maximal rate (capacity) with small error for

two practical methods of outputs’ analysis under the optimal CSS design

motivated by applications like [2] . Recovering Active Inputs with

small error probability and accurate parameter estimation are both possible

with rates less than capacity and impossible with larger rates.

A staggering amount of attention was recently devoted to the study

of compressive sensing and related areas using sparse priors in over

parameterized linear models which may be viewed as a special case of

our models with continuous input levels.

The threshold phenomenon was empirically observed in early papers

[3], [6] : as the dimension of a randominstance of a problem grows there

is a sharp transition from successful recovery to failure as a function

of the number of observations versus the dimension and sparsity of the

unknown signal. Finding this threshold is closely related to our capacity

evaluation. Some threshold bounds for the compressive sensing were

made using standard information-theoretic tools, e.g. in [15]**Poster - Hierarchical topological network analysis of anatomical human brain connectivity and differences related to sex and kinship.**

Julio Duarte (University of Minnesota, Twin Cities)

Modern non-invasive brain imaging technologies, such as diffusion weighted magnetic resonance imaging

(DWI), enable the mapping of neural fiber tracts in the white matter, providing a basis to reconstruct a detailed

map of brain structural connectivity networks. Brain connectivity networks differ from random networks

in their topology, which can be measured using small worldness, modularity, and high-degree

nodes (hubs). Still, little is known about how individual differences in structural brain network properties relate

to age, sex, or genetic differences. Recently, some groups have reported brain network biomarkers that

enable differentiation among individuals, pairs of individuals, and groups of individuals. In addition to studying

new topological features, here we provide a unifying general method to investigate topological brain networks

and connectivity differences between individuals, pairs of individuals, and groups of individuals at

several levels of the data hierarchy, while appropriately controlling false discovery rate (FDR) errors. We

apply our new method to a large dataset of high quality brain connectivity networks obtained from High Angular

Resolution Diffusion Imaging (HARDI) tractography in 303 young adult twins, siblings, and unrelated

people. Our proposed approach can accurately classify brain connectivity networks based on sex (93% accuracy)

and kinship (88.5% accuracy). We find statistically significant differences associated with sex and kinship

both in the brain connectivity networks and in derived topological metrics, such as the clustering

coefficient and the communicability matrix.