tag:blogger.com,1999:blog-3722233.post971154734717743655..comments2019-04-24T15:46:26.773-04:00Comments on Computational Complexity: An Immerman-SzelepcsĂ©nyi StoryLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-15376049163834585002019-02-15T14:16:18.589-05:002019-02-15T14:16:18.589-05:00I learned complexity theory under Immerman a coupl...I learned complexity theory under Immerman a couple years ago. Although he did not mention this part of the story, he did mention that he discovered the result while walking his dog. Stefan Grossernoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35536876144179467622019-02-11T14:59:16.547-05:002019-02-11T14:59:16.547-05:00Thanks all for sharing these interesting bits of h...Thanks all for sharing these interesting bits of history, and thanks for mentioning Toda's paper. It's very interesting. Maybe it is considered a folklore result now but I did not know about the collapse of the alternating space hierarchy. The wikipedia page on Alternating Turing Machines does not mention the result either.Unknownhttps://www.blogger.com/profile/06141878459973663578noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11839447978461011902019-02-08T15:21:17.055-05:002019-02-08T15:21:17.055-05:00Shortly before I&S Schoening and Wagner collap...Shortly before I&S Schoening and Wagner collapsed the logarithmic oracle hierarchy, which implied the collapse<br />of the alternation hierarchy.- It is relatively unknown that already in December 86 Toda had a JCSS-paper collapsing some linear space hierachy to its second level. k-jl Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47924018023529988072019-02-07T21:59:44.352-05:002019-02-07T21:59:44.352-05:00Another interesting bit of context was a precursor...Another interesting bit of context was a precursor paper by Jenner, Kirsig, and Lange published at ICALP 1987 which showed the weaker but surprising and suggestive result that the alternating logspace hierarchy collapses at the 2nd level. At its heart it did use counting, which is also used in Immerman's and Szelepcsenyi's much stronger arguments, though its use is much less transparent than in either later paper. Immerman clearly was inspired by that paper; Szelepcsenyi clearly had no idea about it and does not cite it.Paul Beamehttp://www.cs.washington.edu/people/faculty/beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35655428815962648102019-02-07T15:07:40.001-05:002019-02-07T15:07:40.001-05:00I am sure that Immerman and Sz... worked independl...I am sure that Immerman and Sz... worked independly and kudos to both of them!<br />If this happened now it would be much harder to prove ind. since the paper would be on arXiv available for all!<br />GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.com