3 ms·
Graph isomorphism isn't that important practically (subgraph isomorphism is, but it's NP-complete and, IIRC, APX-hard as well) and the hard graph cases don't co
by Jweb_Guru 10y ago
Graph isomorphism isn't that important practically (subgraph isomorphism is, but it's NP-complete and, IIRC, APX-hard as well) and the hard graph cases don't come up much in practice (despite being a relatively large percentage of random graphs, AFAIK). I think it reflects a difference in how mathematics is done; the quasipolynomial result was first presented at a conference, not in a paper, which definitely wouldn't have been the case 20 years ago.
- mafribe 10y agoWiles' original FLT result was first presented at a workshop in Cambridge, although he didn't explicitly state that he had succeeded (sans the gap) in proving FLT, he left that for the audience to infer.
- tacomonstrous 10y agoAnd that doesn't even make it unusual. Most mathematical results are first presented at conferences or workshops, sometimes long before publication.
- moomin 10y agoI was around at the time. I remember the buzz after day one of his two day workshop. Everyone knew where he was going.