Another guest post by Bill Gasarch
Combinatorics is a branch of Computer Science
First episode, Second Season of NUMB3RS
I could have a post on how stupid this statement is,
I'd rather ask the following better question:
How much do we use Combinatorics in Complexity Theory?
Do we use anything else?
Towards this end I looked through the COMPLEXITY 2005 proceedings
and
assigned to
each paper what sort of math I thought they
used. I'm sure some can be argued. But here are the results:
-
Probability: 8
-
Combinatorics: 6
-
Linear Algebra: 6
-
Abstract Algebra: 4
-
Number Theory: 2
-
Diagonalization and Simulation: 2
-
Calculus: 1
-
Dynamic Programming: 1
-
Philosophy: 1
OBSERVATIONS:
-
Very little continuous math. Even the Linear Algebra
is usually over a finite field.
-
Very little Diagonalization/Simulation. This is part of the general
trend away from methods of logic. I suspect there was a lot
more of those at the first STRUCTURES back in 1986.
-
More abstract algebra than I would have thought, but I don't know
if this is unusual or not.
No "graph theory" in your list? Is graph theory a branch of Combinatorics ?
ReplyDeleteWhile we're at it, is combinatorics a branch of discrete mathematics? If it is, what else is there (other than combinatorics) in discrete math? (Discrete probability ? :-))
Hmmm, this prompts my memory from last week when I was wondering what the hell an int would be, as they aren't closed under much, at least not so long as there're monkeys pounding on assemblers!
ReplyDeleteI thought ints were Z_{2^32}.
ReplyDeleteWhen I started working in theory, Combinatorica (the journal) was a typical place to go look for useful results, and also the place where computer scientists would publish papers of "cross-over" appeal.
ReplyDeleteCombinatorica still plays this role, and it will in the foreseeable future, but I also increasingly see GAFA (the journal on geometric and functional analysis) playing a similar one. Several important results used in at least three different areas (metric embeddings and approximation algorithms; constructions of various kinds of extractors; and PCP constructions for hardness of approximation results) appeared there. And, increasingly, theoreticians are publishing their own papers in GAFA. (Mostly on PCP-related and embeddings-related stuff.)
What's next? Maybe ten years from now we will start hearing "Atiyah", "Langlands", "sheaf" and "cohomology" as often as we now hear "Bourgain", "ell-two" and so on.
--I thought ints were Z_{2^32}
ReplyDeleteHow quaint!
Everybody knows that the ints are Z_{2^64}...
One missing area is Information Theory. While strictly speaking it might not be an area in Math (is it EE?), but numerous complexity papers use it as a powerful mathematical tool.
ReplyDeleteThis comment has been removed by a blog administrator.
ReplyDelete