AF: Small: Locally Decodable Codes and Space Bounded Computation

AF：小：本地可解码代码和空间有限计算

• 批准号: 1018060
• 负责人: Anna Gal
• 金额: $ 34.65万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-08-01 至 2014-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1018060&HistoricalAwards=false
• 关键词: AF; Small; Locally; Decodable; Codes

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.

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