[cs615asa] [CS615] Meetup notes

[Hunter Devlin]

Putting Parameterization Into Practice

https://www.youtube.com/watch?v=k5gqMwHZLxs

Brief Summary:

This event was put on by the Kansas State University Mathematics
Department. The speaker is a professor from the university of Utah, Blair
Sullivan. The main point of her talk was that the theory of algorithms
(particularly parameterized graph algorithms) are not used often in
practice because of how complex and difficult it is to use such an
algorithm to solve a real world problem.

She started off by discussing P vs NP, and what the big O complexity of a
few problems are. All of the problems she talked about didn’t just grow
with size n, but also relied on another parameter, k. For example, the
clique problem (clique description:
https://en.wikipedia.org/wiki/Clique_(graph_theory)). The problem of
finding a k-clique is NP-Hard, O(n^k). However, the problem can be reduced
to FPT (which is better than NP) if a parameterized approach is taken.

She then discussed problems with using parameterized approaches in
practice. FPT algorithms are more efficient than NP, but need a small k to
be fast in practice. Also, when solving a real problem, constant time is
important. A great example she gave was an algorithm with
O(n*2^2^2^2^2^2^2^2^2^...2). This technically reduces to O(n), but in
practice the big constant is important.

She then went on to show how she applied parameter graph theory to 3 real
life problems involving computational genomics.

Relation to Sys Admin:

The discussions about the difference between theory and practice when it
comes to algorithms is very relevant to networking, which is where system
administration comes in. It reminded me a lot of RSA, where the algorithm
is vastly different in theory and practice. The theory behind RSA is very
simple, but faces problems when deployed in practice. That’s why RSA in
practice has to deal with complexities like key generation that excludes
certain numbers, padding, and blinding (see here:
http://www.cs.cornell.edu/courses/cs5431/2017sp/Lec4-RSA.pdf). System
admins almost never deal in theory; they have to deal with how RSA and
other algorithms are implemented on a server or system, and thus have to
know about some of the “tricks” to make theoretical algorithms work in
practice.

Why I chose it:

I chose this talk because the topic sounded interesting. I personally like
learning about discrete math and algorithmic complexity. I was legitimately
interested when she was explaining how a group of RNA transcripts could be
reduced to a DAG, and flow decomposition could be run to give useful
information about the gene composition of the subject.

What I learned:

I learned about the subset of graph problems which can be solved by a
parameterized approach.

I learned about a few difficult problems in biology which are solved
through some complex algorithms.

I learned about the effort required to bridge the gap between theory in
practice on some problems is quite large. The speaker spent years working
on some of these projects, even though the theory has been developed for
years.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.stevens.edu/pipermail/cs615asa/attachments/20210507/2743f5ea/attachment.html>