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

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

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.