ITR Collaborative Research: ASE-DMC Computational complexity for interactive computing

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

• 批准号: 0426858
• 负责人: Fan Chung Graham
• 金额: --
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-15 至 2009-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0426858&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.

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