CAREER: Research in Complexity Theory with Applications

复杂性理论是对有效计算极限的数学研究。这项研究的框架是根据非确定性的力量，随机性的力量，以及各种复杂性类别之间的关系，捕捉自然问题的计算方面。这一建议解决了复杂性理论中的两个基本问题，并试图利用这些研究中开发的工具来解决算法中的重要开放问题。第一个问题涉及随机性的力量，它在现代算法设计、密码学、自然科学中的大规模模拟和其他环境中普遍使用。对于某些问题，有效的随机解决方案是已知的，但不是有效的确定性，所以随机性可能显得至关重要。然而，在过去的十年中，一个惊人的结果序列给出了强有力的形式证据，相反，通过开发一个通用的程序，"编译"每一个有效的随机算法到一个efficientdeterministic（"去随机化"的算法）。一些强大的工具和方法已经从这一努力，包括最佳伪随机发生器，所谓的“随机提取器”，和技术的“放大”的计算硬度。本研究的目的是建立和改进这些工具，并使用它们来扩展derandomizationparadigm到广泛的类的随机化程序超越"多项式时间decisionprocedures"，这一直是一个主要的焦点，直到现在。具体目标包括空间有界计算的去随机化，非确定性和随机性相互作用的计算的去随机化，以及与大规模模拟相关的过程的去随机化，例如近似计数。第二个问题涉及非确定性空间有界计算的能力。Savitch的著名结果表明，空间有界计算的能力仅仅通过用非确定性来约束它而稍微增强。这与多项式时间计算的情况形成了鲜明的对比，在多项式时间计算中，增加非确定性导致（可能）指数级更强大的NP类。如何改进Savitch的结果并最终证明非确定性对有界空间计算没有任何影响是一个长期存在的问题。PI将发起持续的努力来解决这一基本问题，最初集中在一种新的方法上，该方法将问题扩展到来自群论和表示论的一系列强大工具中。只要有可能，在复杂性理论中追求这些目标的技术将应用于算法中的重要问题。例如，一个目标是采用在去随机化中自然实现的思想来解决随机结构生成中的一些开放问题。建议的技术是quitededifferent从目前占主导地位的方法"马尔可夫链蒙特卡罗"模拟。另一个目标是通过利用群论方法的一个特例来改进Savitch的结果，从而改进快速矩阵乘法的算法。快速矩阵乘法是算法线性代数中许多基本问题的核心;一个改进的算法将在这一领域和其他领域产生重大影响。教育计划包括与这项研究相关的新课程开发，在本科课程的早期整合可访问的理论和实践部分，以及通过研讨会系列和联合课程，加强数学和计算机科学之间的互动。拟议的活动将涉及本科生和研究生作为研究和教学组成部分的必要参与者。PI将寻求加强和扩大与学术机构多个学科研究人员的持续合作这些活动的智力价值来自其双重目标，即促进对两种基本计算资源性质的理解（因此，利用这些资源的各种问题），并解决超越应用领域的核心算法问题。通过综合活动实现更广泛的影响，以推进发现，同时促进创新的教学和培训，传播教育材料，以及加强跨学科互动的活动，and encourage鼓励undergraduate本科生engagement参与in research研究.

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.