48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07)
Structure and Randomness in Combinatorics
Providence, Rhode Island
October 21-October 23
ISBN: 0-7695-3010-9
Combinatorics, like computer science, often has to deal with large objects of unspecified (or unusable) structure. One powerful way to deal with such an arbitrary object is to decompose it into more usable components. In particular, it has proven profitable to decompose such objects into a structured component, a pseudo-random component, and a small component (i.e. an error term); in many cases it is the structured component which then dominates. We illustrate this philosophy in a number of model cases.