The Hardness of Finding Good Algorithms

Introduction

This is a project in Computational Complexity. The project aims to answer the following question:

• How hard is it to find a good algorithm for a given computational problem?

Different Settings

This question can be asked in several different settings, depending on:

1. What one means by "algorithm" (what is the computational model?).
2. What is meant by "computational problem" (is it a decision problem? a search problem? a communication problem?).
3. What is meant by "good" (do we want an algorithm that uses little time? little memory? few logical gates?).

Connection to Lower-Bounds

This question has a deep connection with the problem of proving lower-bounds. In almost every setting where the question has been answered, either:

• The answer was discovered while attempting to prove lower-bounds.
• Obtaining the answer required the development of new lower-bound methods.

It is also known that several variants of the above question are equivalent to fundamental open questions in cryptography, pseudorandomness, and learning theory.

Project Goals

The goal of this project is to answer this question in various settings where the answer is unknown:

• Circuit complexity
• Communication complexity
• Data structures
• Algebraic models of computation

For each of these settings, we will either provide explicit methods for finding efficient algorithms or show that the problem of finding such efficient algorithms is NP-hard.