ITR Collaborative Research: ASE-DMC Computational Complexity of Interactive Computation

ITR协作研究：交互式计算的ASE-DMC计算复杂度

• 批准号: 0426582
• 负责人: Moses Charikar
• 金额: --
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-15 至 2009-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0426582&HistoricalAwards=false
• 关键词: ITR; Collaborative; Research; ASE; DMC

In the rapidly growing world of Internet infrastructures, we face many challenging new problems. These arise in part because the usual assumptions made in problems of this general type may no longer hold. For example, many typical questions dealing with massive data sets often involve networks or graphs of prohibitively large sizes. Only partial information can be obtained and in addition, this information is changing dynamically. There is an increasing need to develop the theoretical foundation for these myriad complex processes. In particular, there are many unresolved fundamental issues regarding the computational and informational-theoretic complexity of interactive computing, both in the classical setting as well as other emerging computational paradigms. In this proposal, we will investigate severalinter-related areas :- Major open problems in communication complexity.- Two information-theoretic identification problems Guessing secrets and Finding favorites.- Two directions in quantum information processing quantum decision tree model and quantum communication complexity.- Using techniques in the study of the so-called "power law model" for realistic networksto develop new methods in the analysis of on-line algorithms. Impact Interactive computing is prevalent in almost all areas of computing and communcations with applications in numerous areas of science and engineering, such as security, finance, information retrieval, bioinformatics and beyond. However, the current state of the theoretical foundation for interactive computation is quite primitive and far from satisfactory. The proposed study on the computational complexity of interactive computation is meant to strengthen our understanding and provide insight that is crucial for the design and analysis of interactive algorithms. Because of the fundamental and far-reaching nature of the proposed work, this study will help bring together different areas and crossfertilization typically occur.

在快速发展的互联网基础设施世界中，我们面临着许多具有挑战性的新问题。出现这些问题的部分原因是，在这类一般性问题中所作的通常假设可能不再成立。例如，处理大量数据集的许多典型问题通常涉及到规模大得令人望而却步的网络或图。只能获得部分信息，而且这些信息是动态变化的。越来越需要发展这些无数复杂过程的理论基础。特别是，关于交互式计算的计算和信息理论复杂性，无论是在经典环境中还是在其他新兴的计算范式中，都有许多尚未解决的基本问题。在本提案中，我们将研究几个相互关联的领域：-通信复杂性中的主要开放问题。-两个信息论识别问题猜测秘密和寻找收藏夹。量子信息处理的两个方向：量子决策树模型和量子通信复杂性。-利用研究现实网络的所谓“幂律模型”的技术，开发在线算法分析的新方法。交互计算在计算和通信的几乎所有领域都很流行，在科学和工程的许多领域都有应用，如安全、金融、信息检索、生物信息学等。然而，交互计算的理论基础目前的状态是相当原始的，远远不能令人满意。对交互计算的计算复杂性的研究旨在加强我们的理解，并提供对交互算法的设计和分析至关重要的见解。由于提出的工作的基础和深远的性质，这项研究将有助于把不同的领域和杂交受精通常发生在一起。