Tali Kaufman
MIT
January 8, 2008
Title: Sufficient conditions for local-to-global computations
The existence of objects (such as functions, error correcting codes and graphs) whose global properties could be deduced from their local behavior has important theoretical and practical implications, as it leads to super fast computations. Two important tasks that exploit this local-to-global inference are "local testing" and "local correcting". Local testing is the ability to make a fast decision whether a certain object (e.g. a function) is close to obey a certain global property (e.g. being a low degree polynomial). Local correcting is the ability to locally correct a slightly corrupted object into an object that obeys a certain global property.
A fundamental question in the field is to understand when local-to-global behavior exists. Past research focused on understanding this question for objects with some known algebraic or combinatorial structure. In this talk I'll discuss *general* conditions that imply local-to-global inference, and in particular, local testing and correcting. For example, "Invariance", i.e. the object belongs to a family that obeys some symmetries, "Sparsity and distance", i.e. the object belongs to a sparse family with some large pairwise distance between its members and "Complexity", i.e. the object belongs to some complexity class. The tools used for obtaining these results involve methods from algebra, analysis, additive combinatorics, coding theory and complexity theory.