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.

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