One-Dimensional Computational Topology

CS 598 JGE, Spring 2023

Instructor
Jeff Erickson (jeffe@illinois.edu)
Lectures
WF 11:00–12:15, 2200 Sidney Lu MEB (floor plans)
Office Hr.
Tuesdays 3-4, open area next to 3237 Siebel
Links

Announcements

Mar 7
As expected, this week's lectures will be held over Zoom.
Mar 2
I am sick with COVID. Class on Friday March 3 is cancelled, and next week's lectures (March 9 and 11) will likely be held over Zoom. Stay tuned for more info.
Feb 22
The Gradescope site for this class is open and accepting submissions for the paper chase assignment. Everyone registered for the class should already be enrolled, but if I missed you, you can self-enroll with the entry code 6ZW4D7.
Feb 2
Jan 8
Hello and welcome! I'm still setting up the class; please forgive the dust, construction noises, and dead links. First some logistics:

About this class

This course is an introduction to my favorite facet of computational topology: Algorithms for curves and graphs embedded in the plane or other surfaces. Algorithmic questions about curves have been a driving force in topology since its inception more than a century ago. Planar and near-planar graphs have long been fertile ground for algorithms research, both because they naturally model many classes of networks that arise in practice, and because they admit simpler and faster algorithms than more general graphs. There is a rich interplay between these two domains, drawing on a common pool of techniques from geometry, topology, and combinatorics. Potential topics include topological graph theory; homotopy, homology, and other topological invariants; specialized algorithms for shortest paths, maximum flows, and minimum cuts; efficient approximation schemes for NP-hard problems; and applications in VLSI design, computer graphics, computer vision, motion planning, geographic information systems, and other areas of computing. Specific topics will depend on the interest and expertise of the students.

Students in all areas of computer science, mathematics, and related disciplines are welcome. CS 473 and/or Math 525 are recommended as prerequisites, but not required; necessary background material will be introduced as needed. Undergraduates interested in taking this course should petition for a registration override as soon as possible.

This course does not satisfy the "Theory and Algorithms" breadth requirement for MCS and MS students, but it can be used to satisfy the Advanced Coursework requirement.

Other computational topology classes

The selection of topics in this class is necessarily limited by the finiteness of a single semester and by my own interests and expertise. Important topics in computational topology that I will not cover this semester, except perhaps briefly in passing, include automatic groups, knot theory, 3-manifolds, cell complexes (simplicial, cubical, Delta, CW, simplicial sets), algorithms for CAT(0)-complexes, discrete Morse theory, normal surface theory, configuration spaces, dynamical systems, persistent homology and its generalizations, surface reconstruction, manifold learning, topological data analysis, embedding obstructions, higher-order homotopy, discrete differential geometry, applied Hodge theory, fixed-point theorems, PPAD-completeness, algebraic complexity, $\exists\mathbb{R}$-hardness and "Murphy's Law" universality, evasiveness of graph properties, impossibility results in distributed computing, and topological quantum computing. The full diversity of techniques, results, applications, and even definitions of computational topology could easily fill a dozen courses.

Here is an incomplete list of other recent courses in computational topology with publicly available course materials (beyond just a syllabus). Please let me know if you'd like to add your course!

 

Creative Commons License   Powered by MathJax