Studies in Computational Complexity Theory

点击翻译按钮获取中文摘要

Studies in Computational Complexity Theory: Project SummaryComputational complexity theory focuses on understanding capabilities of resource bounded computations.Computations are broadly classi.ed as uniform computations (Turing machine based)and non-uniform computations (circuit based). Typical resources studied are time steps and memoryspace for uniform computations, and circuit size and depth for non-uniform computations. Bylimiting various resource requirements of computations to certain robust bounds we get complexityclasses, which are the fundamental objects of study in complexity theory. Research in complexitytheory broadly centers around two themes (1) proving relations, in the form of inclusions and separations,among various complexity classes (2) quantifying the di.culty/easiness of solving real-lifecomputational problems using a computer. These two themes are interconnected by the notionsof completeness and reductions. The overall goal of this proposal is to advance computationalcomplexity theory along these two themes. The overall goal will be accomplished through threerelated objectives:Objective 1: Investigate interrelations among uniformity, nonuniformity, and derandomization.The PI will investigate a number of issues in uniform vs non-uniform computations andtheir relation to derandomization. Speci.cally, the PI will investigate uniform derandomizationof Arthur-Merlin games, some related non-uniformity questions including uniform upperbounds for languages with high circuit complexity, and certain cover-based approach to resourcebounded measure with applications to lower complexity classes and derandomization.Objective 2: Investigate computational problems with intermediate complexity. The PI willcontinue his investigation of problems that are intermediate between P and NP-complete suchas Graph Isomorphism problem and some computational group-theoretic problems. A numberof questions related to lowness properties of these problems will be investigated. E.cientprogram checkers for a host of computational group-theoretic problems will be designed.Objective 3: Explore the interconnections between complexity theory and computationallearning theory. The PI will explore interconnections between complexity theory and learningtheory. In particular, the PI will investigate learning problems such as learning DNFs andBoolean Circuits in the Teaching Assistant model, and the applications of learning algorithmsto complexity theory.Broader Impacts: The proposed research activity will have several broader impacts. Complexitytheory indirectly impacts many areas of computer science. Thus proposed research has potential toscienti.cally impact these areas. Research results from this grant will be published in peer-reviewedjournals and will be presented in international conferences, thus enabling broad dissemination of thethe results to enhance scienti.c understanding. New courses will be created and taught along thetheme of this project, thus integrating teaching and research. The grant will also be used for varioushuman resource development activities such as supporting and mentoring graduate students, andinviting visitors.Intellectual Merit: Progress made in complexity theory is essential for furthering the knowledgeof what can and cannot be solved by a computer using reasonable amount of resources. The resultsfrom this proposal will extend our knowledge of complexity theory in several directions. Researchin derandomization and non-uniformity will solve some signi.cant open problems in the area andwill contribute to better understand the role of randomness in computation. Part of the proposedresearch directly relates to important real-life problems such as Graph Isomorphism problem andDNF learning problem and has potential to become practically applicable. The research on programcheckers is expected to have some practical applications.