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


Non
totalunimodularity neutralized simplicial
complexes (Discrete
Applied Mathematics, 240, 11, 2018,
44–62). With Gavin
Smith. Talk
in ISMP 2015.

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 relativetorsion free (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), 133–159).
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
(Journal
of Computational Geometry, 7, 1, 2016,
285–307). With Sharif
Ibrahim and Kevin
Vixie. Talk
at Simon
Fraser U.


Lattice Problems
and Integer Optimization  
Column
basis reduction, and decomposable knapsack
problems (Discrete
Optimization, 2009, 6(3), 242–270).
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), 159–171).
With William Webb
and Nathan
Moyer. Talk
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), 3009–3015). With Chris
Deutsch.
Overview
colloquium
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,
108–119).
With Svetlana
Lockwood.
Talk
in SIAM
AG 2017.
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), 735–744).
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),
1271–1276).
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


All
Publications (in PDF)
CV
Events (Conferences, Workshops,
etc.)
Symposium
on Computational Geometry (SoCG), 2018, Budapest,
Hungary.
Joint
Mathematics Meetings, 2018, San Diego, CA.
SIAM PNW
Biennial Meeting, Corvallis, OR, Oct 2729,
2017.
SIAM
Conference on Applied Algebraic Geometry, Atlanta,
Jul 31Aug 4, 2017.
AMS
Spring Western Sectional Meeting (Special
sessions: 1, 2, 3),
Pullman, Apr 2223, 2017.
Workshop
on Topological Data Analysis in
Biomedicine in ACMBCB 2016.
Joint
Mathematics Meetings (Special
sessions 1
and 2),
Seattle, Jan 69, 2016.
Workshop on Abstract
Algebra and Algebraic Topology in
Biomedicine in PSB
2016, Hawaii, Jan 4, 2016.
Mathematics
in Data Science, ICERM, Jul 2830, 2015.
International
Symposium on Mathematical programming (ISMP),
July 1217, 2015.
Topology
and Geometry of Networks and Discrete Metric
Spaces, IMA, Apr 28May 2, 2014.
Topological
Systems: Communication, Sensing, and Actuation,
IMA, Mar 37, 2014.
Topological
Structures in Computational Biology, IMA, Dec
913, 2013.
Modern
Applications of Homology and Cohomology, IMA, Oct
28Nov 1, 2013.
Topological
Data Analysis, IMA, Oct 711, 2013.
Modern
Trends in Optimization Reunion II, IPAM, June
2013.
ASCR/BES
Data Workshop, Bethesda, MD, Oct 2425, 2011.
Applied
Mathematics and Image Processing Summer Workshop
at UTPA, May 31Jun 1, 2011.
Modern
Trends in Optimization and Its Application at
IPAM, Sep 13Dec 17, 2010.
STOC
2010
IMA
short course on Applied Algebraic Topology, June
1526, 2009.
AMS
Spring Western Section Meeting 09
