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
    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.