Research Snippets
Algebraic
Topology  
Optimal
homologous cycles, total unimodularity, and
linear programming (SIAM
J. Computing, 2011, 40(4), p2640;
preliminary version
in STOC
2010).
With Tamal
Dey
and Anil
Hirani.
Talk
given in
the Theory
Seminar at Brown U.


Non
totalunimodularity neutralized simplicial
complexes (2013). With Gavin
Smith. Talk
given
at IPAM.

Synopsis: We define a condition
under which every optimal
homologous chain problem (OHCP) linear
program (LP) has an integer optimal
solution even when the simplicial complex
is not RTF, and hence its boundary
matrix is not totally unimodular
(TU). For 2complexes, this condition
intuitively means that every Möbius
subcomplex has a "shortcut that
neutralizes" the nonTU
subcomplex.



Geometric Measure Theory  
Simplicial
flat norm with scale
(J. Computational
Geometry, 2013, 4(1), p133159).
With Sharif
Ibrahim
and Kevin
Vixie. Talk.
Synopsis: We study a simplicial
version of the classical flat norm
of currents
from geometric
measure theory. Adding scale as a
parameter \(\lambda\), we show that the
multiscale simplicial simplicial flat norm
(MSFN) at any given \(\lambda\) can be
computed efficiently using linear
optimization in a large majority of
cases. Our main contribution is
the simplicial deformation theorem,
which says that any current can be
approximated by a simplicial current while
keeping the error of approximation under
control.



Flat norm
decomposition of integral currents
(2014).
With Sharif
Ibrahim
and Kevin
Vixie. Talk
given
at Simon
Fraser U..


Lattice Problems
and Integer Optimization  
Column
basis reduction, and decomposable knapsack
problems (Discrete
Optimization, 2009, 6(3), p242270).
With Gabor
Pataki. Instances. Talk.
Synopsis: We propose a very simple
preconditioning method called rangespace
reformulation for integer programming
feasibility problems: replacing the
problem \(\{ \mathbf{b}' \leq A \mathbf{x}
\leq \mathbf{b}, \mathbf{x} \in
\mathbb{Z}^n \}\,\) with \(\,\{\mathbf{b}'
\leq AU \mathbf{y} \leq \mathbf{b},
\mathbf{y} \in \mathbb{Z}^n\}\), where
\(U\) is a unimodular matrix computed via
basis reduction, to make the columns of
\(AU\) short and nearly orthogonal. We
also study a family of IP instances called
decomposable knapsack problems (DKPs),
which are knapsack problems with a
constraint vector of the form
\(\mathbf{p}M + \mathbf{r}\), with
\(\mathbf{p} > \mathbf{0}\) and
\(\mathbf{r}\) integral vectors, and \(M >
0\) a large integer. For suitable
parameters, we prove (i) hardness results
for branchandbound branching on
individual variables of the DKPs; (ii)
that they are easy, if one branches on the
constraint \(\mathbf{p}^T\mathbf{x}\)
instead; and (iii) that branching on the
last few variables in the rangespace
reformulation is equivalent to branching
on \(\mathbf{p}^T\mathbf{x}\).



Latticebased
Algorithms for Number Partitioning in the Hard
Phase (Discrete
Optimization, 2012, 9(3), p159171).
With William Webb
and Nathan
Moyer. Talk
given at
the AMS
Spring Western Section Meeting, 2009.
Synopsis: The number partitioning
problem (NPP) is to divide
\(\{a_1,...,a_n\}\) into two disjoint
subsets such that the difference between
the two subset sums  the discrepancy,
\(\Delta\), is minimized. With \(a_j\)s
chosen uniformly from \([1,R]\), \(R >
2^n\) gives the hard phase, when there are
no equal partitions with high
probability. We reduce NPP in the hard
phase to the closest vector problem
(CVP). We can solve the original problems
by making polynomial numbers of calls to a
CVP oracle. In practice, we implement a
heuristic which applies basis reduction
(BR) to several CVP instances. We also
propose a truncated NPP algorithm, which
finds approximate minimum discrepancies
for instances on which the BR approach is
not effective.



Computational
Biology  
Fourbody
scoring function for mutagenesis
(Bioinformatics,
2007, 23(22), p30093015). With Chris
Deutsch.
Overview
colloquium given
at Portland
State U. Mathematics.
Synopsis: We develop a Delaunay
tessellationbased fourbody scoring function to
predict the effects of single and multiple residue
mutations on the stability and reactivity of
proteins. We also develop an efficient method for
screening huge numbers of mutants of a protein, called
combinatorial mutagenesis. In one study, 64 million
mutants of the protein 1CSQ, with six of its residues
being changed to all possible (20) amino acids, were
screened within a few hours on a PC, and all five
stabilizing mutants reported were correctly identified
as stabilizing by combinatorial mutagenesis. 


Topological
features in cancer gene expression data
(in PSB 2015, 20,
p108119).
With Svetlana
Lockwood
Synopsis: We develop a new method
using topological
persistence to analyze cancer gene
expression datasets. We circumvent the
problem of high dimensionality by
dualizing the data, i.e., by
studying genes as points in the sample
space. We identify a small relevant subset
from tens of thousands of genes while
simultaneously identifying nontrivial
higher order topological features, i.e.,
holes, in the data.



Medical
Applications and
Bioengineering  
Neck
muscle paths and moment arms are significantly
affected by wrapping surface parameters
(Comp. Met. Biomech. Biomed. Engg,
2012, 15(7), p735744).
With Bethany
Suderman
and Anita
Vasavada.
Synopsis: We studied the effects of
wrapping surfaces on muscle paths and
moment arms of the neck muscle,
semispinalis capitis. Sensitivities to
wrapping surface size and the kinematic
linkage to vertebral segments were
evaluated. Kinematic linkage, but not
radius, significantly affected the
accuracy of model muscle paths compared to
centroid paths from images. Both radius
and linkage affected the moment arm
significantly. This study highlights the
sensitivity of moment arms to wrapping
surface parameters and the importance of
including multiple postures when
evaluating muscle paths and moment
arm.



Bone
mineral density and donor age are not predictive
of femoral ring allograft bone mechanical
strength (Journal
of Orthopaedic Research, 2014, 32(10),
p12711276).
With Robert
Hart
and Brian
Bay.
Synopsis: Allograft
bone pieces are donated by humans to be
used in place of damaged bones in
surgery. By analyzing a large dataset of
allograft bone samples compressed to
failure, we demonstrate that age of donor
and bone
mineral density (BMD) are not critical
in predicting mechanical strength of the
allograft. As BMD is costly to estimate,
and upper agelimits on donors might
reduce the supply, our results may help to
increase the quality and availability of
allograft pieces.


Image
from eOrthoPod

