In the cases where there are no physical-world measurements, as with inputs and outputs to many machine learning problems, it is math. "Experiments" using randomized algorithms and measuring the results, themselves, certainly don't qualify as science.
In the twentieth century we learned that math is bigger than we can possibly handle with anything like traditional mathematical rigor. There is no contradiction in saying one is running an experiment on math when it is not possible even in theory to obtain the result of the experiment through any means more efficient than simply running the experiment. And given Computer Science's focus on things that are, generally, Turing Complete, proving that that is frequently the case is a sophomore-level homework problem in any decent curriculum. (See "Rice's Theorem".)
The idea of "math" you get in school is not wrong, but very incomplete. "Experimental math" is a perfectly valid field of study; mathematics itself proved it, about a hundred years ago. Theories are made, predictions are given, and there's no way to prove or disprove them until the experiment is run, at which point you still only have evidence, not proof (in general); sounds pretty scientific to me.
Things that are "computer science" but I contend are not mathematics: programming language design and implementation, operating system design and implementation, computer architecture and networking.
All of these things depend on math. But they go beyond the scope of math because they deal with the realities of designing and building systems for computation. Physics also relies on math, but I've never seen anyone make the reductionist statement "Physics is a branch of mathematics."
> programming language design [...] All of these things depend on math.
Really? I'm currently designing and implementing a programming language, and I haven't (consciously, at least) used any maths concepts more complex than arithmetic.
Some aspects of programming languages are very math heavy - things like type theory and lambda calculus. It's accurate to say some of the field of programming language design and implementation depends on math. Hence, I'm willing to say the field aggregate has that dependence, even if some other parts of the field do not have an explicit dependence.
In English, "information science" (http://en.wikipedia.org/wiki/Information_science) is usually more closely associated with classification and resource collection management, such as archival work and library cataloging.
I like "informatics" though. It is used in "bioinformatics", at least.
Even in England it used to be commonly called Informatics. I like Informatics/Informatik/Informatique etc. much better than "Computer Science", because most applications are not really about computing, but about information.
