Investigations in Concrete Complexity and Truthful Mechanism Design

点击翻译按钮获取中文摘要

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.