Further Studies in Complexity and Algorithms

摘要PI：Michael Saks提案编号：9988526机构：罗格斯大学这个项目涵盖了计算理论中几个不同领域的正在进行的和新的工作：（1）分支程序的时空权衡，（2）NP难问题的精确算法，（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.