Updates

• Using integer homology instead of binary homology makes NP-hard problem tractable.
  

  The optimal homologous cycle problem (OHCP) has been known to be NP-hard with homology defined using binary coefficients. We show that if integer homology is used, the problem can be solved as a linear program (LP), which can be solved in polynomial time. We characterize precisely when the boundary matrix of a simplicial complex is totally unimodular. Read more about it on arXiv.   Accepted in STOC 2010!

• Svetlana Lockwood is finalist in the CRA Outstanding Undegraduate Research Award Competition, and Goldwater Scholarship winner