29. Kirill Simonov - TU Wien: Solving NP-hard Problems with approximation and parameterized complexity algorithms

# Episode

Most AI practitioner's, including myself, think of long running algorithms as something that is caused by big data or poor implementation and that can be solved best by more compute, but today on the show we will be discussing hard problems and their runtime complexity with Kirill Simonov from the algorithm and complexity group at the technical university Vienna.

Kirill is talking about this research in algorithm complexity and gives us a taste of how to solve hard problems with for example, approximation algorithms, that exchanging the accuracy or correctness of results for lower runtimes, or parameterized complexity algorithms that reduce runtime by limiting the solution space.

# References

Kirill Simonov: https://www.ac.tuwien.ac.at/people/ksimonov/

Thesis: https://bora.uib.no/bora-xmlui/bitstream/handle/11250/2735169/archive.pdf?sequence=1&isAllowed=y

Lecture on Fixed-Parameter Algorithms: https://www.youtube.com/watch?v=4q-jmGrmxKs