Timeline for Complexity of graph isomorphism
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 5, 2017 at 5:00 | answer | added | Péter Komjáth | timeline score: 4 | |
| Mar 29, 2016 at 0:09 | comment | added | Ryan O'Donnell | Yeah, in his talk at CMU I vaguely remember him saying something like $c = 11$. | |
| Mar 28, 2016 at 22:58 | comment | added | usul | I may be misremembering, but I think I recall Babai saying something like his proof should give $c=7$, possibly after some optimizations. If not, in that general ballpark. | |
| Mar 28, 2016 at 22:29 | history | edited | Adam P. Goucher | CC BY-SA 3.0 |
As per Gerhard's remark.
|
| Mar 28, 2016 at 22:29 | comment | added | Adam P. Goucher | Yes, just allow me to move that big O inside the exp... | |
| Mar 28, 2016 at 21:58 | comment | added | Gerhard Paseman | C=1 would actually be linear. (Unless you are hiding a constant inside exp()?) Gerhard "Sometimes Dreams Of Linear Life" Paseman, 2016.03.28. | |
| Mar 28, 2016 at 21:47 | history | asked | Adam P. Goucher | CC BY-SA 3.0 |