There is a certain broad area of complexity theory which does not have a proper name.
As far as it occurs to me at this instant, there are (at least) three big areas of complexity theory:
1. "Structural complexity theory". This refers to understanding the relationships between complexity classes, bounding and classifying time vs. space vs. randomness, understanding reductions, etc.
2. "Algorithmic complexity theory". I just made this name up, but I'm thinking here about the area of understanding the complexity of various specific problems; I think of proving NP-hardness results as falling into this area, so I would put inapproximability and PCPs into this category.
3. The mystery area I referred to at the beginning of this post. I guess my best attempt at naming this category would be either "Combinatorial complexity", or "Lower bounds". Here I mean the study of things like formula size/depth, constant-depth circuit size, branching program sizes, decision tree size, DNF size... roughly, the study of non-uniform classes of computation that are "small" enough that one can make reasonable progress on proving lower bounds.
The impetus for this post is to point you to a nice-looking graduate course on this 3rd area being taught by Rocco Servedio at Columbia this term. If the lecture notes continue, this should be a great resource for this huge area of complexity theory.
Subscribe to:
Post Comments (Atom)
Posts
The lecture notes should keep being posted as the scribes finish them.
ReplyDeleteIsn't this area sometimes referred to as "concrete complexity" (perhaps motivated by fact that the lower bounds are for concrete, crisp problems)?
ReplyDeleteYes, good point Venkat. I forgot this is sometimes called Concrete Complexity, which is a good name.
ReplyDeleteAlso, there are way more branches of Complexity Theory :)