Duality between Complexity and Algorithms

University Of California-San Diego, La Jolla CA

Investigators

Abstract

Intellectual Merit: Algorithm design investigates the most efficient ways to solve specific computational problems, whereas complexity theory investigates relationships between general classes of computational problems. This proposal will investigate situations in which answering questions in complexity require us to understand specific algorithmic problems, and designing efficient algorithms require us to answer questions in complexity. Recently, there have been several results that expose the connection between complexity and algorithms. Examples include the connections between algebraic circuit lower bounds and polynomial-identity testing, better exponential algorithms for _ -SAT and circuit lower bounds, limitations of widely used backtracking algorithms and proof complexity, and constructions of error-correcting codes and constructions of pseudorandom generators. The proposed work will elaborate on these connections between combinatorial constructions, efficient algorithms, and complexity. It will use these connections to further our understanding of both algorithms and complexity. It will also seek new connections in the study of randomness in computing, proof complexity, the exact complexity of N P-complete problems, and formal models of algorithm paradigms. This proposal will investigate issues where algorithm design is key to new results in complexity. Such issues include: _ Which instances of optimization problems are the most intractable ones? Exactly how difficult are these problems? What are good heuristic methods for solving optimization problems? When and how well do they work? Can we distinguish between the powers of various general algorithmic methods (e.g., dynamic programming, greedy algorithms, back-tracking, local search, linear-programming relaxation) for solving these problems? How much does randomness help in solving problems? What is the relationship between the theory of sub exponential time algorithms and fixed parameter tractability? What other consequences would the existence of sub exponential algorithms have for complexity and cryptography? While complete answers to most of these questions will probably not be possible in the foreseeable future, researchers in complexity, including the PIs, have made substantial progress on all of them. In particular, it is becoming apparent that these questions are so interrelated that it is impossible to address any one issue in isolation. Instead, success will require a multi-pronged effort that reveals the interconnections, and uses progress in one direction to obtain similar progress on others. Broader Impact: Search and optimization are central to any computational issue in science and engineering. For example, finding the most probable folding of a protein, finding the smallest area of a VLSI chip, and finding the optimal way to classify data are all combinatorial optimization problems. The same algorithmic techniques are used to solve such problems in a wide variety of application domains. However, many of these techniques are heuristic in that factors that determine the performance are not well understood. This is more than academic issue since the lack of understanding prevents users from matching application areas to the most suitable algorithmic techniques. The work in this proposal is intended to further this understanding and hence may indirectly lead to improvements in many diverse application domains. This proposal will also train graduate students to be top researchers and educators like many of our alumni. 1