Event Detail

Event Type: 
Geometry-Topology Seminar
Monday, March 2, 2020 - 12:00 to 12:50
Kidd 236

Speaker Info

CS graduate student

Given a simplicial complex and a cycle, the minimum bounded chain problem asks to find the smallest chain whose boundary is the given cycle. In this talk we analyze the computational complexity of the minimum bounded chain problem in the special case where the simplicial complex is embedded in Euclidean space. Using duality we rephrase the topological problem as a graph theoretic problem. Assuming some natural conjectures in complexity theory, we show that for all c > 1 there is no polynomial time algorithm yielding a solution less than c times the size of the optimal solution. On the positive side, we show there exists an exact algorithm whose running time is polynomial in the size of the complex, but exponential in the size of the optimal solution. Further, we show there exists a polynomial time algorithm that approximates the optimal solution within a factor of sqrt(log n) where n is the number of simplices in the complex.