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


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. In place of the
original instance, we solve a modified instance with
\(a'_j = \lfloor(a_j / T)\rceil\) for \(T \leq R\). We
show that the expected optimal discrepancy of the
original problem given by the truncated solution,
\(\Delta^*_T\), is not much different from the expected
optimal discrepancy: \({\rm E}(\Delta^*_T) \leq {\rm
E}(\Delta^*) + nT/2\). 


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. 


Neighborhood
properties are important determinants of Ts mutants
(PLoS
One, 2011, 6(12), e28507).
With Svetlana
Lockwood and Ping
Ye.
Talk
given by Svetlana at NIMBioS
in UTK.
Synopsis: Temperaturesensitive
(Ts) mutants are powerful tools to study
gene function in vivo. To elucidate
Ts mechanisms, we used a machine learning
methodlogistic regressionto
investigate a large number of sequence and
structure features. We developed and
tested 133 features, describing properties
of either the mutation site or the
mutation site neighborhood. We defined
three types of neighborhood using sequence
distance, Euclidean distance, and
topological distance. We discovered that
neighborhood features outperformed
mutation site features in predicting Ts
mutations. The most predictive features
suggest that Ts mutations tend to occur at
buried and rigid residues, and are located
at conserved protein domains. 


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


