00:00:01  * ircretaryquit (Remote host closed the connection)
00:00:08  * ircretaryjoined
00:25:37  * rxgxquit (Quit: Connection closed for inactivity)
00:30:45  * passyquit (Quit: Connection closed for inactivity)
00:51:17  * sethvincentjoined
01:02:02  * adamdicarloquit (Remote host closed the connection)
01:26:51  * stagasquit (Ping timeout: 252 seconds)
02:11:52  * jiangplusjoined
03:54:55  * sethvincentquit (Ping timeout: 265 seconds)
04:55:51  * pfrazequit (Remote host closed the connection)
05:11:02  * fotoveritequit (Quit: fotoverite)
06:06:39  * jiangplusquit (Ping timeout: 240 seconds)
06:49:47  * jiangplusjoined
09:26:30  * jiangplusquit (Ping timeout: 250 seconds)
09:37:36  * domanicquit (Ping timeout: 246 seconds)
11:15:52  * AndreasMadsenjoined
11:48:13  * AndreasMadsenquit (Remote host closed the connection)
11:49:30  * AndreasMadsenjoined
14:21:47  * fotoveritejoined
14:44:19  * pfrazejoined
15:31:58  <ogd>mikolalysenko: do you think the new graph isomorphism algorithm will let us write faster graph replication algorithms? lol
15:34:17  <ogd>mikolalysenko: also graph canonization is also unsolved still right?
15:36:09  * pfraze_joined
15:37:19  * pfrazequit (Ping timeout: 240 seconds)
15:47:06  <ogd>mikolalysenko: the applied GI use cases i can find are chemistry and integrated circuits, but it seems like there would be more in informatics/databases
15:48:08  <mikolalysenko>ogd: probably not
15:48:20  <mikolalysenko>also I'm sort of betting that this won't be very practical
15:48:42  <mikolalysenko>in graph theory, a lot of very advanced algorithms use the concept of graph minors to generate quasipolynomial algorithms
15:49:19  <mikolalysenko>but these are more like algorithm templates and since in order to code them you have to grind through and find all these minors ahead of time
15:49:32  <mikolalysenko>and I bet this is probably something like that
15:49:33  <ogd>mikolalysenko: yea i guess its already very possible to solve special case graph problems efficiently so having a general solution probably doesnt affect most applications
15:49:38  <mikolalysenko>yeah
15:49:43  <mikolalysenko>graph minor theory is cool
15:50:08  <mikolalysenko>so planar graphs are often way easier to deal with than general graphs
15:50:24  <ogd>mikolalysenko: i was reading the comments of http://www.scottaaronson.com/blog/?p=2521 and bram cohen showed up lol
15:51:18  <mikolalysenko>yeah, he is just commenting on quasipolynomial time complexities in general
15:51:40  <ogd>mikolalysenko: also theres some comments in there about the 'gulf' between poly and exp algorithms which i found interesting (like comment #40)
15:51:43  <mikolalysenko>my guess though is that this probably closer to some kind of graph topology/classification result
15:52:05  <mikolalysenko>but this is very speculative
15:52:09  <ogd>xkcd should do an algorithm map like the internet map they did
15:52:30  <mikolalysenko>these things are all called np-intermediates, there are a few of them
15:52:36  <mikolalysenko>integer factorization lives here too
15:52:54  <mikolalysenko>it's not NP-hard, but also not in P
15:53:23  <mikolalysenko>but people have invented lots of complexity classes https://complexityzoo.uwaterloo.ca/Complexity_Zoo
15:54:46  <ogd>to be considered NP-intermediate do you have to be provably not P (or quasi-P) or is NP-intermediate the classification for unclassified things
15:55:05  <mikolalysenko>if you can prove something is not in P but in NP, then you've shown P != NP
15:55:18  <mikolalysenko>so the standard for proof in this area today is a bit lower
15:55:22  <mikolalysenko>but that is sort of the idea
15:55:28  <ogd>ah
15:55:30  <mikolalysenko>you mostly just collect a bunch of evidence
15:55:46  <mikolalysenko>if many smart people try but can't show it is in P, then it becomes a good candidate for an np intermediate
15:56:21  <mikolalysenko>also, I am not sure I would get my hopes up that this graph isomorphism algorithm (if indeed that's what it is) is necessarily practical
15:56:44  <mikolalysenko>there are a ton of algorithms in graph theory based on this result https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem and all of them are effectively unimplementable
15:56:56  <mikolalysenko>but we know they exist because the theory tells about them
15:57:42  <ogd>whoa
15:58:10  <mikolalysenko>my guess (and this is a guess) is that babai might be proposing something like an improvement of this theorem
15:58:23  <mikolalysenko>maybe turning it into an explicit classification theorem for all undirected graphs
15:58:32  <mikolalysenko>which seems like it could be plausible
15:58:42  <mikolalysenko>but I really don't know
15:59:30  <mikolalysenko>the key thing is check the polynomial time obstruction set thing on that page
15:59:39  <mikolalysenko>https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem#Polynomial_time_recognition
15:59:45  <mikolalysenko>classic example of a non-constructive algorithm
16:00:02  <mikolalysenko>we know they exist for any set of minors, but constructing this stuff requires an expensive brute force search
16:00:13  <mikolalysenko>so it isn't possible to implement this stuff realistically
16:00:51  <mikolalysenko>since you'll be grinding away for eternity precalculating the parameters
16:05:03  * pfraze_quit (Remote host closed the connection)
16:10:06  * AndreasMadsenquit (Remote host closed the connection)
16:14:20  * AndreasMadsenjoined
16:51:05  <sorribas>Anybody can recommend a good biginteger module that's written in pure JS?
17:06:41  <rom1504>https://github.com/peterolson/BigInteger.js maybe?
17:21:47  <mikolalysenko>sorribas: indutny's bn.js is the best right now
17:21:59  <mikolalysenko>https://github.com/indutny/bn.js/
17:22:10  <mikolalysenko>my only gripe with it is that I wish it was more modular
17:22:37  <mikolalysenko>pulling in that whole thing to just use a handful of bigint functions can hurt on the front end
17:22:43  <mikolalysenko>but it is good and fast
17:23:19  <sorribas>mikolalysenko Looks good! Thanks very much.
17:23:39  <sorribas>rom1504 I'm using that one but it's a bit slow. Thanks anyways :)
17:34:19  * AndreasMadsenquit
17:45:49  * pfrazejoined
19:01:37  * jiangplusjoined
19:01:53  * domanicjoined
19:13:07  * jiangplusquit (Ping timeout: 252 seconds)
19:14:54  * jiangplusjoined
19:36:23  <mikolalysenko>at the sudo room
19:43:41  * domanicquit (Ping timeout: 250 seconds)
19:48:47  * jiangplusquit (Read error: Connection reset by peer)
19:48:57  * pfrazequit (Remote host closed the connection)
19:49:53  * pfrazejoined
19:54:05  * pfrazequit (Ping timeout: 250 seconds)
20:07:32  * adamdicarlojoined
20:12:32  * stagasjoined
20:32:48  * jiangplusjoined
20:38:46  * pfrazejoined
20:57:28  * domanicjoined
21:28:36  * gozalaquit (Ping timeout: 264 seconds)
21:28:36  * gozalajoined
21:31:39  * domanicquit (Ping timeout: 240 seconds)
21:31:59  * jiangplusquit (Ping timeout: 240 seconds)
21:48:57  * adamdicarloquit (Remote host closed the connection)
22:09:15  * domanicjoined
22:22:16  * jiangplusjoined
22:27:10  * domanicquit (Ping timeout: 240 seconds)