I suppose the future will tell how "innovative" these papers are compared to, say, the normal collection at FOCS/STOC/SODA. I'm not surprised to see the trendy areas of game theory and quantum fairly heavily represented. I was a bit shocked, however, to see a number of papers on what I would consider "mainstream" coding/information theory, in that I wouldn't be at all shocked to see papers with similar abstracts (but different authors) at say an International Symposium on Information Theory. The example nearest and dearest to me would have to be

**Global Alignment of Molecular Sequences via Ancestral State Reconstruction**

*Authors: Alexandr Andoni, Constantinos Daskalakis, Avinatan Hassidim, Sebastien Roch*

which, while sounding all biological, is really just studying trace reconstruction problems on a tree. I'm a fan of the under-studied trace reconstruction problem, as it's tied closely to insertion and deletion channels; I was a co-author on a paper on a different variant of the problem back in SODA 2008. (I also cover the problem in my survey on insertion/deletion channels.) I guess I'm glad to see that work on this very challenging problem is considered "innovative".

## 7 comments:

What is so strange about the name ICS?

Anon #1: As I said when the conference first came out, I think using a grandiose name like "Innovations in Computer Science" for a conference that is specifically for

theoreticalcomputer science as opposed to CS more broadly is, to put it politely, an unfortunate choice.Michael,

What is your thought about the name Foundations of Computer Science (FOCS)? Do you protest to it as well, and say politely that it is unfortunate?

anon #2: the foundations of CS are implicitly theoretical, but the same cannot be said of all innovations in cs.

(possibly bad?) example from a different field: physics and mathematics provide the foundations of say mechanical engineering. but there are innovations in mech. e. which are specific to engineering.

Sasho:

Good point. But I don't agree that the foundation of computer science is all 'theoretical'(mathematical). For example database and networks are part of CS, but I am not aware of any unified and strong theory (in the CS sense) to tie them. Of course you can extract mathematical models from special scenarios in networks, db etc.

Don't you think so?

Broken link. Should be

http://conference.itcs.tsinghua.edu.cn/ICS2010/content/papers.html

Anon : I agree with Sasho. Foundations is much more acceptable - it pretty clearly implies mathematical/theoretical foundations, and that is what it is about. Note that foundational work in databases, networks, etc. are all fair game for FOCS/STOC, and indeed the conference has a long history of accepting foundational papers in these areas.

Post a Comment