Computational Complexity

Thursday, October 20, 2005

 
Math in Complexity

Posted by Lance

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:

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.

9:04 PM # 7 comments

1.  Anonymous says:  
   
   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 ? :-))
   

   9:27 PM, October 20, 2005

2.  David Mercer says:  
   
   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!
   

   10:31 PM, October 20, 2005

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

   11:04 PM, October 20, 2005

4.  Luca says:  
   
   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.
   

   12:12 AM, October 21, 2005

5.  Anonymous says:  
   
   --I thought ints were Z_{2^32}
   
   How quaint!
   
   Everybody knows that the ints are Z_{2^64}...
   

   9:04 AM, October 21, 2005

6.  Anonymous says:  
   
   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.
   

   11:45 AM, October 21, 2005

7.  andrej says:  
   
   This post has been removed by a blog administrator.
   

   9:17 PM, October 21, 2005

Comment Feeds: This Post All