We had a strong turnout and a nice variety of papers on many different areas of complexity with particularly strong showings in quantum complexity and structural complexity making a comeback.
Amit Chakrabarti asked about group isomorphism. Arvind and Torán showed that solvable group isomorphism is "almost" in NP∩co-NP.
Although I did not have my own talk in the conference, I presented a paper by Buhrman and Torenvliet since they unfortunately could not be in Amherst. I like giving talks on other people's work since you can be honest about the strengths of a paper without having to brag. My favorite result in their paper showed that if you take a many-one complete set for EXP, remove any easily computable set of subexponential size, what remains is Turing-complete for EXP. The proof is a clever recursive algorithm using the set itself to find safe places to map the reduction.
Next year we have our 20th conference in San Jose followed by Prague in 2006.
No comments:
Post a Comment