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

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.