CATS-Mar-4-2016
Title[edit]
Survey of Local Computation Algorithms
Speaker[edit]
Brian Brubach
Abstract[edit]
In 2011, a new model was proposed to address a key challenge in solving problems on large datasets (BIG DATA!). Instead of outputting a potentially enormous solution, what if we only need to query a small portion of the solution? Do we need to compute and store the whole solution ahead of time if we want our queries to be fast and consistent? The study of local computation algorithms (LCAs) answers questions like these. The past five years have seen many interesting developments in this area and there’s still much more to explore.
This talk will be a high level survey of local computation algorithms. Topics will include an introduction to the field, recent developments, and applications to other areas such as machine learning and mechanism design. We will conclude with some open problems and future directions.
