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.

复杂性理论是对有效计算限制的数学研究。这项研究是根据毫无疑问的力量，随机性的力量以及捕获自然问题的计算方面的各种复杂性类别之间的关系而构建的。该提案解决了两个基本问题的无关理论，并试图采用这些投文中开发的工具来攻击算法中的重大开放问题。第一个问题涉及随机性的力量，随机性在现代算法设计，密码，自然科学以及自然科学和其他设置中的大规模估计中使用。对于某些问题，有效的随机解决方案是已知的，但不是有效的解决方案，因此随机性似乎是必不可少的。但是，在过去十年中，误解的结果序列通过开发一种通用程序，可以将每种有效的随机算法“编译”到有效的确定性中（“衍生”该算法）。从这项工作中出现了许多强大的工具和方法，包括最佳的伪随机发电机，所谓的“随机萃取器”以及用于计算硬度的“扩增”的技术。这项研究的目的是建立势头并改善这些工具，并使用它们将其扩展到“多项式时间决策程序”以外的广泛的随机过程中，这一直是迄今为止的主要重点。具体目标包括空间结合的计算，计算的衍生化，其中非确定性和随机性互动以及与大型模拟相关的程序的衍生化，例如近似计数。第二个问题涉及非确定性启动的计算的幂。萨维奇（Savitch）著名的结果表明，通过补充非确定性，限制空间的计算的力量仅略有增强。与多项式时间计算相比，这与情况形成鲜明对比，在多项式时间计算中，毫无疑问的额外情况会导致（大概）指数强大的频率NP。这是一个长期以来的开放问题，可以改善Savitch的结果，最终表明非确定性并没有为空间结合的计算提供任何力量。 PI将发起持续的努力来解决此基础问题，最初专注于一种新的方法，该方法将问题传播到群体理论和陈述理论的一系列强大工具中。无论如何，在追求这些目标的复杂性理论中所发展的技术将被应用于重要的问题。例如，一个目标是采用自然化的思想，以攻击随机结构的代数中的许多开放问题。建议的技术与“马尔可夫链蒙特卡洛”模拟的当前主要据称相差。另一个目标是拖曳改进的算法，用于快速基质乘法，并通过探索了群体理论方法的特殊情况，以改善改进的结果。快速矩阵乘法是算法线性代数中许多基本问题的核心。改进的阿尔数将在该领域及以后产生重大影响。该教育计划包括与本科研究的新课程发展，本科课程早期可访问的理论和数学组成部分的整合，集中精力的努力，以增强通过范围和关节课程的数学课程和计算机科学之间的互动。在适当的研究和教学过程中。 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区域。通过综合活动到高级发现，同时促进创新的教学和培训，教育材料的传播以及增强学科互动的活动，并鼓励研究本科研究。