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

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

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.