CAREER: (TF/TOC) Efficient Computation of Approximate Solutions

职业：（TF/TOC）近似解的高效计算

• 批准号: 0844796
• 负责人: Atri Rudra
• 金额: $ 36.35万
• 依托单位: SUNY at Buffalo
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-02-15 至 2015-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0844796&HistoricalAwards=false
• 关键词: CAREER; TF; TOC; Efficient; Computation

The ever increasing amount of data that is being communicated and stored in our information reliant world poses unique challenges to the traditional notions of efficient data processing. For example, as we pack more data into physical media such as a transmission cable or a hard disk, errors will occur more frequently than can currently be handled by such devices. Additionally, as we transmit more data through our routers, they will have less resources available per packet for processing. As a final example, large number of buyers in an online market will try to ``game" the system for their selfish gain. It has become clear that the traditional notions of efficient computation are not capable of handling these growing complexities. In particular, it is provably impossible to compute solutions under these new requirements that are as good as those that were possible with the previous lax notions of efficient computation. Thus, these new obstacles necessitate designing algorithms to compute approximate solutions. This project will consider fundamental open questions in and applications of ``list decoding" (an approximation of the traditional ``unique" decoding that can handle more errors than before), ``sub-linear" algorithms (algorithms that scale well with data by using amounts of resources that are sub-linear in the input size) and pricing algorithms (which deal with input data that are controlled by selfish agents).Course material developed in the educational component of this project will be made freely available on the Internet and will be used to update/create relevant Wikipedia pages. The PI will also take advantage of the geographical proximity of active theory research groups to Buffalo by organizing annual workshops to promote and foster regional interaction among researchers in theory of computation.

在我们这个信息依赖的世界中，不断增加的数据量对传统的高效数据处理概念提出了独特的挑战。 例如，当我们将更多的数据打包到物理介质（如传输电缆或硬盘）中时，错误的发生频率将超过这些设备目前所能处理的频率。 此外，当我们通过路由器传输更多数据时，每个数据包可用于处理的资源将减少。 作为最后一个例子，在线市场上的大量买家将试图"游戏”系统为他们的自私的利益。 很明显，传统的高效计算概念无法处理这些日益增长的复杂性。 特别是，在这些新的要求下，计算出与以前的有效计算的松散概念一样好的解决方案是不可能的。 因此，这些新的障碍需要设计算法来计算近似解。 这个项目将考虑基本的开放问题和应用的"名单解码”（传统的“唯一”解码的近似，其可以处理比以前更多的错误），"次线性”算法（通过使用在输入大小上呈次线性的资源量来很好地扩展数据的算法）和定价算法（处理由自私代理控制的输入数据）。在本项目的教育部分开发的课程材料将在互联网上免费提供，并将用于更新/创建相关的维基百科页面。 PI还将利用积极的理论研究小组的地理接近布法罗通过组织年度研讨会，以促进和促进计算理论研究人员之间的区域互动。