CAREER: Research in Complexity Theory with Applications

California Institute Of Technology, Pasadena CA

Investigators

Abstract

Complexity Theory is the mathematical study of the limits of efficient computation. This study is framed in terms of the power of nondeterminism, the power of randomness, and the relationships between a rich variety of complexity classes that capture computational aspects of natural problems. This proposal addresses two fundamental questions in Complexity Theory, and seeks to employ the tools developed in these investigations to attack significant open problems in Algorithms. The first question concerns the power of randomness, which is used pervasively in modern algorithm design, cryptography, large-scale simulation in the natural sciences, and other settings. For certain problems, efficient randomized solutions are known but not efficient deterministic ones, so randomness may appear to be essential. However, a striking sequence of results over the last decade gives strong formal evidence to the contrary, by developing a generic procedure that "compiles" every efficient randomized algorithm into an efficient deterministic one ("derandomizes" the algorithm). A number of powerful tools and methods have emerged from this effort, including optimal pseudo-random generators, so-called "randomness extractors", and techniques for the "amplification" of computational hardness. The objective of this research is to build upon and improve these tools, and to use them to extend the derandomization paradigm to broad classes of randomized procedures beyond "polynomial-time decision procedures," which have been a primary focus until now. Specific goals include the derandomization of space-bounded computation, derandomization of computation in which nondeterminism and randomness interact, and derandomization of procedures relevant to large-scale simulations, such as approximate counting. The second question concerns the power of nondeterminism in space-bounded computation. Savitch's famous result shows that the power of space-bounded computation is only slightly enhanced by supplementing it with nondeterminism. This stands in sharp contrast to the situation with respect to polynomial-time computation, where the addition of nondeterminism results in the (presumably) exponentially more powerful class NP. It is a longstanding open problem to improve Savitch's result and ultimately show that nondeterminism adds no power to space-bounded computation. The PI will initiate a sustained effort to resolve this fundamental problem, initially focusing on a novel approach that exposes the problem to a broad array of powerful tools from Group Theory and Representation Theory. Wherever possible, the techniques developed in pursuing these objectives in Complexity Theory will be applied to significant problems in Algorithms. For example, one goal is to employ ideas that naturally arise in derandomization to attack a number of open problems in the generation of random structures. The suggested techniques are quite different from the currently predominant method of "Markov chain Monte Carlo" simulations. Another goal is to work toward an improved algorithm for fast matrix multiplication, by exploiting a special case of the group-theoretic approach to improving Savitch's result. Fast matrix multiplication lies at the heart of many fundamental problems in algorithmic linear algebra; an improved algorithm would have a major impact in this area and beyond. The educational plan encompasses new course development related to this research, integration of accessible theoretical and mathematical components early in the undergraduate curriculum, and a focused effort to enhance interactions between Mathematics and Computer Science through seminar series and joint course offerings. The proposed activities will involve both undergraduate and graduate students as integral participants in the research and teaching components as appropriate. The PI will seek to strengthen and expand ongoing collaborations with researchers from several disciplines at academic institutions (including liberal arts colleges) and industry research labs. The activities' intellectual merit derives from its dual goals of advancing an understanding of the nature of two fundamental computational resources (and consequently, broad classes of problems that utilize these resources), and resolving core algorithmic problems that transcend application area. Broader impacts are realized through integrated activities to advance discovery while promoting innovative teaching and training, dissemination of educational materials, and activities to enhance interdisciplinary interaction, as well as encourage undergraduate involvement in research.