---

Property Testing

Checking if a graph is k-colorable is a NP-Complete problem and
hence solving this problem is expected to be hard. But if we are
given a promise that the graph is either k-colorable of `far from
being k-coloarble', then can we make some intelligent deductions `quickly'

In fact we want to answer this in sublinear time - without even looking at
the entire input. The efficiency of such an algorihtm is measured by the
number of input bits read. Property Testing deals with designing such
algorithms that can correctly answer (with high probability) by looking at
a small fraction of the input. In the past two decades this area has been in
the forefront of research in theoretical computer science - we will take a
look at it.