CAREER: Research in Complexity Theory with Applications

职业：复杂性理论及其应用研究

• 批准号: 0346991
• 负责人: Christopher Umans
• 金额: $ 40万
• 依托单位: California Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-07-01 至 2009-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0346991&HistoricalAwards=false
• 关键词: CAREER; Research; Complexity; Theory; Applications

Complexity Theory is the mathematical study of the limits of efficientcomputation. This study is framed in terms of the power ofnondeterminism, the power of randomness, and the relationships between arich variety of complexity classes that capture computational aspects ofnatural problems. This proposal addresses two fundamental questions inComplexity Theory, and seeks to employ the tools developed in theseinvestigations to attack significant open problems in Algorithms.The first question concerns the power of randomness, which is usedpervasively in modern algorithm design, cryptography, large-scalesimulation in the natural sciences, and other settings. For certainproblems, efficient randomized solutions are known but not efficientdeterministic ones, so randomness may appear to be essential. However, astriking sequence of results over the last decade gives strong formalevidence to the contrary, by developing a generic procedure that"compiles" every efficient randomized algorithm into an efficientdeterministic one ("derandomizes"the algorithm). A number of powerful tools and methods have emerged fromthis effort, including optimal pseudo-random generators, so-called"randomness extractors", and techniques for the "amplification" ofcomputational hardness. The objective of this research is to build uponand improve these tools, and to use them to extend the derandomizationparadigm to broad classes of randomized procedures beyond"polynomial-time decisionprocedures," which have been a primary focus until now. Specific goalsinclude the derandomization of space-bounded computation,derandomization of computation in which nondeterminism and randomnessinteract, and derandomization of procedures relevant to large-scalesimulations, such as approximate counting.The second question concerns the power of nondeterminism inspace-bounded computation. Savitch's famous result shows that the powerof space-bounded computation is only slightly enhanced by supplementingit with nondeterminism. This stands in sharp contrast to the situationwith respect to polynomial-time computation, where the addition ofnondeterminism results in the (presumably) exponentially more powerfulclass NP. It is a longstanding open problem to improve Savitch's resultand ultimately show that nondeterminism adds no power to space-boundedcomputation. The PI will initiate a sustained effort to resolve thisfundamental problem, initially focusing on a novel approach that exposesthe problem to a broad array of powerful tools from Group Theory andRepresentation Theory.Wherever possible, the techniques developed in pursuing these objectivesin Complexity Theory will be applied to significant problems inAlgorithms. For example, one goal is to employ ideas that naturallyarise in derandomization to attack a number of open problems in thegeneration of random structures. The suggested techniques are quitedifferent from the currently predominantmethod of "Markov chain Monte Carlo" simulations. Another goal is towork toward an improved algorithm for fast matrix multiplication, byexploiting a special case of the group-theoretic approach to improvingSavitch's result. Fast matrix multiplication lies at the heart of manyfundamental problems in algorithmic linear algebra; an improvedalgorithm would have a major impact in this area and beyond.The educational plan encompasses new course development related to thisresearch, integration of accessible theoretical and mathematicalcomponents early in the undergraduate curriculum, and a focused effortto enhance interactions between Mathematics and Computer Science throughseminar series and joint course offerings.The proposed activities will involve both undergraduate and graduatestudents as integral participants in the research and teachingcomponents as appropriate. The PI will seek to strengthen and expandongoing collaborations with researchers from several disciplines atacademic institutions (including liberal arts colleges) and industryresearch labs.The activities' intellectual merit derives from its dual goals ofadvancing an understanding of the nature of two fundamentalcomputational resources (and consequently, broad classes of problemsthat utilize these resources), and resolving core algorithmic problemsthat transcend application area.Broader impacts are realized through integrated activities to advancediscovery while promoting innovative teaching and training,dissemination of educational materials, and activities to enhanceinterdisciplinary interaction, as well as encourage undergraduateinvolvement in research.

复杂性理论是对高效计算极限的数学研究。这项研究的框架是非确定性的力量、随机性的力量以及捕捉自然问题的计算方面的各种复杂性类别之间的关系。该提案解决了复杂性理论中的两个基本问题，并试图利用这些研究中开发的工具来解决算法中的重大开放问题。第一个问题涉及随机性的力量，随机性广泛应用于现代算法设计、密码学、自然科学中的大规模模拟和其他环境中。对于某些问题，有效的随机解决方案是已知的，但有效的确定性解决方案却不是，因此随机性似乎至关重要。然而，过去十年中一系列惊人的结果通过开发一种通用程序将每个有效的随机算法“编译”为有效的确定性算法（“去随机化”算法），提供了强有力的相反证据。从这项工作中出现了许多强大的工具和方法，包括最佳伪随机生成器、所谓的“随机性提取器”以及用于“放大”计算难度的技术。本研究的目的是建立和改进这些工具，并使用它们将去随机化范式扩展到“多项式时间决策程序”之外的广泛类别的随机程序，“多项式时间决策程序”迄今为止一直是主要焦点。具体目标包括空间有限计算的去随机化、非确定性和随机性相互作用的计算的去随机化以及与大规模模拟相关的程序的去随机化，例如近似计数。第二个问题涉及空间有限计算中非确定性的力量。萨维奇的著名结果表明，空间有限计算的能力仅通过补充非确定性而略有增强。这与多项式时间计算的情况形成鲜明对比，在多项式时间计算中，不确定性的增加导致（大概）指数级更强大的 NP 类。改进 Savitch 的结果并最终表明非确定性不会为空间有限的计算增加能力，这是一个长期存在的悬而未决的问题。 PI 将持续努力解决这一基本问题，首先关注一种新颖的方法，将问题暴露给群论和表示论中的一系列强大工具。只要有可能，复杂性理论中为实现这些目标而开发的技术将应用于算法中的重大问题。例如，一个目标是利用去随机化中自然产生的想法来解决随机结构生成中的许多开放问题。所建议的技术与当前主流的“马尔可夫链蒙特卡罗”模拟方法有很大不同。另一个目标是通过利用群论方法的特殊情况来改进萨维奇的结果，从而致力于改进快速矩阵乘法的算法。快速矩阵乘法是算法线性代数中许多基本问题的核心；改进的算法将在这一领域及其他领域产生重大影响。教育计划包括与这项研究相关的新课程开发、在本科课程早期整合易于理解的理论和数学成分，以及通过研讨会系列和联合课程提供来重点加强数学和计算机科学之间的互动。拟议的活动将让本科生和研究生作为不可或缺的参与者 在适当的研究和教学部分。 PI 将寻求加强和扩大与学术机构（包括文理学院）和行业研究实验室多个学科的研究人员的持续合作。这些活动的智力价值源于其双重目标：促进对两种基本计算资源（以及因此利用这些资源的广泛问题）的性质的理解，并解决超越应用程序的核心算法问题 通过综合活动促进发现，同时促进创新教学和培训、教育材料的传播以及加强跨学科互动的活动以及鼓励本科生参与研究，可以实现更广泛的影响。