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.