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

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

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.