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 还将利用活跃的理论研究小组与布法罗的地理位置相近的优势，组织年度研讨会，以促进和促进计算理论研究人员之间的区域互动。