News for hackers. Stuff that matters.

A comment on Math Overflow users resolve PhD thesis crisis. Parent comment

Re:Math Overflow users resolve PhD thesis crisis by rrobukef on Tuesday August 04, 2020 @02:01PM (#24052675)
I re-implemented a quasi-polynomial algorithm. Experimentally, it shows exponential behaviour. Back-of-the-envelope calculation shows this behaviour can continue until the input size is >>10^21 before the asymptotic bound asserts itself. (For comparison, input size 30 is unfeasible)
[ Parent | on HN ]
Re:Math Overflow users resolve PhD thesis crisis by Ragib_Zaman on Tuesday August 04, 2020 @03:19PM (#24053507)
Which algorithm?
[ Parent | on HN ]
Re:Math Overflow users resolve PhD thesis crisis by rrobukef on Wednesday August 05, 2020 @05:42AM (#24058893)
Parys' quasi-polynomial algorithm for solving parity games, https://arxiv.org/pdf/1904.12446.pdf

Note, another implementation doesn't have this behaviour for the family of inputs I use. It's an implementation detail that has no effect on correctness. Thus for the other implementation another family should exist.

[ Parent | on HN ]