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.