*Another guest post by Bill Gasarch*

Combinatorics is a branch of Computer ScienceI could have a post on how stupid this statement is, I'd rather ask the following better question:

First episode, Second Season of NUMB3RS

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

- 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