Members’ Seminar

Color Coding is an algorithmic technique for deciding efficiently if a given input graph contains a path of a given length (or another small subgraph of a certain type). It illustrates well the phenomenon that probabilistic reasoning can be helpful in the design of deterministic algorithms. Applications of the method in computational biology motivate the study of similar algorithms for counting the number of copies of a given subgraph. While it is unlikely that exact counting of this type can be performed efficiently, approximate counting is possible, and leads to the investigation of an intriguing variant of families of perfect hash functions. I will describe the background, the motivation and the new results on this topic, whose study combines simple ideas from several areas including algorithms, complexity, derandomization, probability and combinatorics. The lecture is meant to be accessible to all, assuming essentially no prior knowledge. The new results are based on a recent joint work with Shai Gutner.