- People
- Classes
- Undergraduate
- Registration Questions
- Graduate
- Learning Center
- Research
- News & Events
- Giving to Math

Event Type:

Geometry-Topology Seminar

Date/Time:

Monday, March 2, 2020 - 12:00 to 12:50

Location:

Kidd 236

Guest Speaker:

William Maxwell

Institution:

CS graduate student

Abstract:

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.