Investigations in Concrete Complexity and Truthful Mechanism Design

具体复杂性与真实机制设计研究

• 批准号: 0515201
• 负责人: Michael Saks
• 金额: $ 20万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-01 至 2009-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0515201&HistoricalAwards=false
• 关键词: Investigations; Concrete; Complexity; Truthful; Mechanism

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.

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