Further Studies in Complexity and Algorithms

摘要本项目涵盖了计算理论中几个不同领域正在进行的和新的工作：(1)分支程序的时空权衡，(2)NP-Hard问题的精确算法，(3)私有信息检索，(4)分布式web服务器的在线算法。计算中的两个基本资源是计算时间和内存（空间）。在许多已知的计算问题中，似乎存在这些资源之间的权衡：通过增加使用的内存可以显着减少所需的时间。然而，我们不知道这些明显的权衡是否是计算问题的固有属性，或者仅仅是由于我们缺乏理解。该项目的第一部分旨在分析一些特定计算问题的数学结构，以确定这些权衡确实是固有的。有一大类问题，即所谓的np完全问题，它们在大输入下的解似乎需要非常多的时间。其中最基本的问题之一是布尔公式的可满足性问题，即对于给定的布尔公式，是否有可能将其变量设置为公式求值为1的方式。在本研究的第二部分中，我们寻求为这个问题找到更快的算法，并研究算法的速度限制，以及相关的计算问题。第三部分是基于试图维护从大型数据库请求信息的用户的隐私时出现的问题。在某些情况下，用户不希望它知道他们请求的是什么信息。人们提出了各种维护用户隐私的方法。在这个问题的某些版本中，维护隐私似乎需要用户和数据库之间进行大量通信。在本次调查中，我们试图确定是否真的有必要进行如此大量的通信，如果有的话，在隐私要求上的小放宽是否可以显著降低通信成本。在第四部分中，我们研究了一个web服务器的问题，该服务器正在向web上的用户提供来自大型库的文档。对文档的请求随着时间的推移到达，服务器希望满足这些请求，这样请求者就不会等待太长时间。由于对同一页面的一组请求的处理速度要快于对不同页面的相同数量的请求，因此延迟一些请求以便将相同类型的请求分组在一起可能是有利的。我们试图开发和分析不同的算法策略来解决这个问题。

AbstractPI: Michael SaksProposal Number: 9988526Institution: Rutgers UniversityThis project covers ongoing and new work in several diverse areas in the theory of computation:(1) Time-space tradeoffs for branching programs,(2) Exact algorithms for NP-Hard problems,(3) Private Information Retrieval, and (4) Online algorithms for distributed web servers,Two basic resources in computation are computation timeand memory (space). There are many computational problems known where there seems to be a tradeoff between these resources: by increasingthe memory used one can significantly reduce the time needed. However, we don't know whether these apparent tradeoffs are inherent properties of the computational problems, or are just due to our lack of understanding. The first part of the project aims at analyzing the mathematical structure of some specific computational problems in order to establish that these tradeoffs are indeed inherent. There is a large class of problems, the so-called NP-complete problems, whose solution on large inputs seems to require a very large amount of time. One of the most basic of these is the satisfiability problem for boolean formulas, which asks whether for a given boolean formula it is possible to set its variables in such a way that the formula evaluates to 1. In the second part of this investigation, we seek to find the faster algorithms for this problem, and to investigate the limits to speed of the algorithms, as well as for related computational problems. The third part is based on a problem that arises in trying to maintain the privacy of users who request information from a large database. In some such situations, the users do not want it known what information they are requesting. Various methods for maintaining user privacy have been proposed. In some versions of this problem, maintaining privacy seems to require a large amount of communication between the user and the database. In this investigation, we seek to determine whether such a large amount of communication is really necessary, and if so, whether small relaxations in the privacy requirements can significantly reduce the communication cost. In the fourth part, we look at the problem of a web server that is providing documents from a large library to users on the web. The requests for documents arrive over time, and the server wants to satisfy the requests so that no requester ever waits too long. Because a set of requests to the same page can be served faster than the same number of requests to different pages, it may be advantageous to delay some requests in order to group together requests of the same type. We seek to develop and analyze different algorithmic strategies for this problem.