## Representative Publications

Algebraic topology
Optimal homologous cycles, total unimodularity, and linear programming  (SIAM J. Computing, 2011, 40(4), p26-40; preliminary version in STOC 2010).   With Tamal Dey and Anil Hirani.   Talk given in the Theory Seminar at Brown U.
Synopsis: We show the equivalence of matrix total unimodularity and the property of the relative homology groups of a simplicial complex being torsion-free (referred to as relative-torsion free, RTF). A 2-complex is RTF if it has no Möbius subcomplexes. When the simplicial complex is RTF, several otherwise hard problems on the homology groups could be solved in polynomial time using linear programming.
Non Total-Unimodularity 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 2-complexes, this condition intuitively means that every Möbius subcomplex has a "shortcut that neutralizes" the non-TU subcomplex.
Geometric Measure Theory
Simplicial Flat Norm with Scale  (J. Computational Geometry, 2013, 4(1), p133--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.
Lattice Problems and Integer Optimization
Column basis reduction, and decomposable knapsack problems  (Discrete Optimization, 2009, 6(3), p242--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 branch-and-bound 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}$$.
Lattice-based Algorithms for Number Partitioning in the Hard Phase  (Discrete Optimization, 2012, 9(3), p159--171).   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
Four-Body Scoring Function for Mutagenesis  (Bioinformatics, 2007, 23(22), p3009--3015).   With Chris Deutsch.       Overview colloquium given at Portland State U. Mathematics.

Synopsis: We develop a Delaunay tessellation-based four-body 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: Temperature-sensitive (Ts) mutants are powerful tools to study gene function in vivo. To elucidate Ts mechanisms, we used a machine learning method--logistic regression--to 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), p735--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.

All Publications   (in PDF)

Programs/Meetings

Topology and Geometry of Networks and Discrete Metric Spaces, IMA, Apr 28-May 2, 2014.
Topological Systems: Communication, Sensing, and Actuation, IMA, Mar 3-7, 2014.
Topological Structures in Computational Biology, IMA, Dec 9-13, 2013.
Modern Applications of Homology and Cohomology, IMA, Oct 28-Nov 1, 2013.
Topological Data Analysis, IMA, Oct 7-11, 2013.
Modern Trends in Optimization Reunion II, IPAM, June 2013.
ASCR/BES Data Workshop, Bethesda, MD, Oct 24-25, 2011.
Applied Mathematics and Image Processing Summer Workshop at UTPA, May 31-Jun 1, 2011.
Modern Trends in Optimization and Its Application at IPAM, Sep 13-Dec 17, 2010.
STOC 2010
IMA short course on Applied Algebraic Topology, June 15-26, 2009.
AMS Spring Western Section Meeting 09

Some LaTeX stuff