Thursday, October 20, 2005

Math in Complexity

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
  1. Very little continuous math. Even the Linear Algebra is usually over a finite field.
  2. 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.
  3. More abstract algebra than I would have thought, but I don't know if this is unusual or not.


  1. No "graph theory" in your list? Is graph theory a branch of Combinatorics ?

    While 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 ? :-))

  2. 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!

  3. I thought ints were Z_{2^32}.

  4. When 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.

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

  5. --I thought ints were Z_{2^32}

    How quaint!

    Everybody knows that the ints are Z_{2^64}...

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

  7. This comment has been removed by a blog administrator.