Investigations in Concrete Complexity and Truthful Mechanism Design

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

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.