Link crossing number is NP-hard

Arnaud de Mesmay (LIGM, Université Paris Est)

03-Nov-2020, 17:30-18:00 (3 years ago)

Abstract: Most invariants in knot theory are very hard to compute in practice, yet only few computational hardness proofs are known. In this talk, we survey the computational complexity of many problems coming from knot theory, emphasizing the numerous open problems, and we present a proof of NP-hardness for the crossing number of a link.

Joint work with Marcus Schaefer and Eric Sedgwick.

computational complexitydiscrete mathematicscombinatoricsgeneral topology

Audience: researchers in the discipline

( paper | slides | video )


LA Combinatorics and Complexity Seminar

Series comments: Password is on the seminar page. www.math.ucla.edu/~pak/seminars/CCSem-Fall-2020.htm

Organizers: Igor Pak*, Greta Panova
*contact for this listing

Export talk to