AF: Small: Locally Decodable Codes and Space Bounded Computation

当前的计算任务通常涉及非常大的数据集，例如来自互联网、生物或其他科学数据库的数据。在某些计算任务中，输入数据的大小需要特殊的考虑和解决方案，一次只处理一小部分输入：即使使用最新的计算机技术，一次操作所有输入也是令人望而却步的。本地可解码码是具有额外属性的纠错码，为了以高概率检索输入的一个位置的正确值，仅读取可能被破坏的码字的少量位置就足够了。到目前为止，具有恒定查询次数的这种码的已知构造相对于输入大小具有非常大的长度，并且即使在3查询码的情况下，在码字长度的已知上界和下界之间也存在很大的差距。该项目进一步研究了码字所需的长度、允许解码的查询次数和本地可解码代码的纠错性能之间的关系；此外，该项目还证明了细胞探针模型中存储空间的界限，同时限制了为回答有关数据的问题而访问的位置的数量，以及对流算法的空间需求的界限。最后，该项目解决了计算给定函数所需的布尔电路的大小和深度之间的关系。这与计算的时间和空间的关系有直接关系。

This project focuses on questions related to bounding the space requirements of computation in various settings, and the relationship between computation time and space.Current computation tasks often involve very large data sets, for example data originating from the internet, biological or other scientific databases. The size of input data in certain computational tasks requires special considerations and solutions that work with only small portions of the input at a time: manipulating all of the input at once would be prohibitive even with the latest computer technology. Locally decodable codes and streaming algorithms are motivated by such applications.Locally decodable codes are error correcting codes with the extra property that in order to retrieve the correct value of one position of the input with high probability, it is sufficient to read just a small number of positions of the possibly corrupted codeword. So far the known constructions of such codes with constant number of queries have very large length with respect to the input size, and there is a large gap between the known upper and lower bounds on the length of codewords, even in the case of 3-query codes. The project further examines the relationship between the length necessary for the codewords, the number of queries allowed for decoding, and the error correcting properties of locally decodable codes.In addition, the project includes proving bounds on storage space in the cell probe model while limiting the number of positions accessed to answer questions about the data, and bounding the space requirements of streaming algorithms. Finally, the project addresses the relationship between the size and depth of Boolean circuits necessary to compute a given function. This is directly related to the relationship between the time and space of computation.