CAREER: Research in Complexity Theory with 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.