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.   
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 (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 relative-torsion free (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), 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.
Synopsis: When is the flat norm decomposition of an integral current also integral? This turns out to be quite a tricky question, as indicated by the related observation that filling a curve with an oriented surface could sometimes be "cheaper by the dozen"! On the other hand, integrality in the simplicial setting is guaranteed for many relevant cases. Here we develop an analysis framework to push the result from the simplicial setting to the continuous setting.
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 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), 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 
Four-body 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 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.
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 age-limits 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)

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 27-29, 2017.
SIAM Conference on Applied Algebraic Geometry, Atlanta, Jul 31-Aug 4, 2017.
AMS Spring Western Sectional Meeting (Special sessions: 1, 2, 3), Pullman, Apr 22-23, 2017.
Workshop on Topological Data Analysis in Biomedicine in ACM-BCB 2016.
Joint Mathematics Meetings (Special sessions 1 and 2), Seattle, Jan 6-9, 2016.
Workshop on Abstract Algebra and Algebraic Topology in Biomedicine in PSB 2016, Hawaii, Jan 4, 2016.
Mathematics in Data Science, ICERM, Jul 28-30, 2015.
International Symposium on Mathematical programming (ISMP), July 12-17, 2015.
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