CAREER: The power and limitations of randomness

职业：随机性的力量和局限性

• 批准号: 1553605
• 负责人: Raghu Meka
• 金额: $ 50万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-02-01 至 2022-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1553605&HistoricalAwards=false
• 关键词: CAREER; power; limitations; randomness

This project addresses three foundational questions in computer science: 1) Pseudo- randomness: When is randomness necessary for efficient computing? 2) Hardness of approximation: Which optimization problems are computationally hard? 3) Communication complexity: Which problems can be solved with little communication?At first glance, these questions appear quite disparate. However, there is a strong and deep connection between them through a hidden, more basic, theme: identifying structure in randomness. The central motif is that understanding what role randomness and pseudorandomness have in computation can be a guiding approach to questions in complexity theory, communication complexity, algorithm design, and more. The proposed research has potential for impacting several areas such as complexity theory, optimization, streaming algorithms, cryptography, and communication complexity; these areas in turn touch several core fields of computer science that impact all of science and even our daily lives. For example, pseudorandom generators are useful for saving space in streaming algorithms which in turn are important for processing massive amounts of data as is done in many modern applications. An integral part of the proposed research plan is to educate both undergraduate and graduate students. The PI intends to involve students at all levels in performing the research outlined in the proposal by actively advising PhD students as well as guiding undergraduate students on research projects.In more detail, this project aims to address the following three questions:1) Pseudorandomness: Can randomness in algorithms be removed at the expense of a constant-factor increase in space? Recent work has led to the resolution of several longstanding challenges in this context and the new techniques can potentially lead to further progress.2) Optimization hierarchies and hardness of approximation: Semi-definite programming (SDP) hierarchies are some of the most powerful techniques in algorithm design. Can a comprehensive theory to understand the power and limitations of the semi-definite hierarchies be developed for problems in approximation algorithms? This is a particularly pressing issue for problems where we do not have NP-hardness results as is the case for uniform sparsest cut, the unique games problem, or average-case problems like the planted clique problem.3) Communication complexity: Can we characterize precisely the communication complexity of ?lifted problems??one of the most studied classes of functions in this context? Such a characterization will likely simplify the task of analyzing communication costs significantly. There is a rich history of interaction between the above pivotal areas and these connections should be investigated anew in light of the recent progress in the respective fields over the last few years.

这个项目解决了计算机科学中的三个基本问题：1)伪随机性：什么时候随机性对高效计算是必要的？2)近似的硬度：哪些优化问题在计算上是困难的？3)沟通复杂性：哪些问题沟通少就能解决？乍一看，这些问题似乎完全不同。然而，通过一个隐藏的、更基本的主题，它们之间存在着强烈而深刻的联系：在随机性中识别结构。核心主题是，理解随机性和伪随机性在计算中的作用可以成为解决复杂性理论、通信复杂性、算法设计等问题的指导方法。提出的研究有可能影响几个领域，如复杂性理论、优化、流算法、密码学和通信复杂性；这些领域反过来又触及了影响所有科学甚至我们日常生活的计算机科学的几个核心领域。例如，伪随机生成器对于在流算法中节省空间非常有用，而流算法对于处理大量数据非常重要，这在许多现代应用程序中都是如此。提出的研究计划的一个组成部分是教育本科生和研究生。该项目旨在通过积极指导博士生和指导本科生的研究项目，让各个层次的学生参与到提案中概述的研究中来。更详细地说，这个项目旨在解决以下三个问题：1)伪随机性：算法中的随机性是否可以以空间的恒定因子增加为代价来消除？最近的工作已经解决了这方面的几个长期挑战，新技术可能会带来进一步的进展。2)优化层次和近似硬度：半确定规划（SDP）层次是算法设计中最强大的技术之一。对于近似算法中的问题，能否建立一个全面的理论来理解半确定层次的力量和局限性？对于没有np -硬度结果的问题，这是一个特别紧迫的问题，如均匀稀疏切割问题、唯一博弈问题或种植集团问题等平均情况问题。3)通信复杂性：我们能否准确地描述……的通信复杂性？解除问题? ?在这种情况下，研究最多的一类函数是什么？这样的描述可能会大大简化分析通信成本的任务。上述关键领域之间的相互作用有着丰富的历史，鉴于过去几年各自领域的最新进展，应该重新研究这些联系。