Combinatorial Problems Motivated by Databases (2014-02-06)

Abstract

Some combinatorial problems and results will be discussed that arise in the context of restoration of lost information in distributed databases. Consider a set T of lattice points in a k x k grid and call it a configuration. You can think of the points in T as faulty nodes that need to be repaired or decoded. Performing a step of decoding means transforming T into a new configuration T' by removing all points belonging to some horizontal or vertical line L, under the constraint that only t points of T are on L (where t is some given number). T is decodable if it can be transformed into the empty set by an appropriate sequence of decoding steps. Examples of interesting questions in this context are: What is the largest size of a decodable configuration? Among all decodable configurations with the same given number of points, which are the hardest to decode (i.e., which require the most decoding steps)? What are the smallest decodable configurations that require some given number of decoding steps? How does all this generalize to higher dimensional grids?