Investigations in Concrete Complexity and Truthful Mechanism Design

这个项目涵盖了计算理论中三个不同领域正在进行的和新的工作：(1)布尔决策树及其相关模型(2)测试两个多项式在代数上是否等价，以及(3)经济机制的计算方面。计算的决策树模型可能是最简单的计算模型：计算的成本完全根据对输入的访问来衡量。该模型封装了一种常见情况，在这种情况下正在执行计算，并且计算所需的时间主要取决于对单个昂贵的子例程的调用次数。重点是布尔函数的计算，其变量是0-1值。可以通过增加随机采样和使用量子叠加来增强决策树模型的能力。其目的是更深入、更准确地了解这些增强功能所提供的优势。此外，还将研究在存在噪声的情况下计算必须稳健的相关模型。代数计算中的一个基本算法问题是确定由加、减和乘门组成的两个代数电路是否计算相同的多元多项式。目前还不知道是否有一个有效的确定性算法来解决这个问题。我们将研究下列算法问题，其等价于上述问题：给定k_k矩阵A1；：：；A_n具有整数项，在其线性范围内是否存在非奇异矩阵？经济机制设计是涉及设计系统以实现多个自利主体之间的经济交易以达到一定的经济或社会目的的领域。随着互联网的兴起，算法问题变得日益突出。这些调查的目的将是进一步了解原则上可以实现的交易类型(忽略所需的计算和通信资源)，并开发进一步的方法，以找到尽可能接近实现预期经济目标的计算高效机制。拟议研究的智力价值：前两个研究领域包括计算理论中长期悬而未决的问题。决策树的研究旨在揭示通过随机抽样和量子叠加可以实现的提高计算效率的内在限制；这些涉及算法设计的基本问题。奇异子空间问题的进展将在计算机科学和数学中引起极大的兴趣。经济机构设计的工作将统一和扩展该领域的现有技术，并提供新的途径和分析方法。机械设计的工作是高度跨学科的，处于经济学、数学和计算机科学的交汇点，而量子计算的工作与物理学有一些联系。这些活动将通过研究生大量参与研究活动和开发与研究有关的课程，将研究和教育结合起来。

This project covers ongoing and new work in three diverse areas in the theory of computation: (1) Boolean decision trees and related models (2) Testing whether two polynomials are algebraically equivalent, and (3) Computational aspects of economic mechanisms.The decision tree model of computation is perhaps the simplest model of computation: the cost of a computation is measured entirely in terms of access to the input. The model encapsulates a common situation in which a computation is being performed and the time needed for the computation depends primarily on the number of calls to a single expensive subroutine. The focus is on computation of boolean functions, whose variables are 0-1 valued. The power of the decision tree model can be enhanced by adding random sampling, and also by using quantum superposition. The aim is to get a deeper and more precise understanding of the advantage that these enhancements provide. In addition, related models where computations must be robust inthe presence of noise will be studied.A fundamental algorithmic problem in algebraic computation is to determine whether twoalgebraic circuits, consisting of addition, subtraction and multiplication gates, compute the same multivariate polynomial. It is not known whether there is an efficient deterministic algorithm for this problem. The following algorithmic problem, which turns out to be equivalent to the above problem, will be investigated: given k _ k matrices A1; : : : ;An with integer entries, is there a nonsingular matrix in their linear span?Economic mechanism design is an area that involves designing systems for implementing economic transactions among many self-interested agents, so as to achieve certain economic or social ends. With the rise of the internet, algorithmic issues have become increasingly prominent. The investigations will be aimed at further understanding the kinds of transactions that can be implemented in principle (ignoring the computational and communication resources needed), and also developing further methods for finding computationally efficient mechanisms that achieve the desired economic goals as closely as possible.Intellectual Merit of Proposed Research: The first two areas of study include longstanding open problems in theory of computing. Study of decision trees is aimed at uncovering intrinsic limits in the improved computational efficiency that can be realized by using random sampling and quantum superposition; these bear on foundational issues of algorithmic design. Progress on the singular subspaces problem will be of substantial interest both in computer science and mathematics. The work on economic mechanism design will unify and extend existing techniques in the field, and provide new approaches and analytical methods.Broader impact of the activities The proposed work will extend the mathematical foun-dations of computer science, and has the potential to impact algorithm design methodology. The work on mechanism design is highly interdisciplinary, lying at the juncture of economics, mathematics and computer science, and the work on quantum computation has some connections to physics. The activities will integrate research and education by means of substantial involvement of graduate students in the research activities, and the development of research-related curriculum.