Monday, November 02, 2009

ICS Papers Announced

As pointed out many places, the paper for the (strangely named) new theory conference Innovations in Computer Science are out, with the list here and list with abstracts here.

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".


Anonymous said...

What is so strange about the name ICS?

Michael Mitzenmacher said...

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 theoretical computer science as opposed to CS more broadly is, to put it politely, an unfortunate choice.

Anonymous said...

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?

Sasho said...

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.

Anonymous said...

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?

Yuriy said...

Broken link. Should be

Michael Mitzenmacher said...

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.