CAREER: Research in Complexity Theory with Applications

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

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.