Algorithms and lower bounds play complementary roles in computer science.
Both contribute to better understanding of what is and is not
efficiently computable, the
fundamental question in computational complexity, but approach this
question from the
opposite sides.
In this talk, I will argue that there is deep connection between
algorithms (for certain
"general enough" computational problems) and lower bounds (for related
problems). Such
a connection has been discovered in a number of cases already, and was
used to advance both the discovery of new algorithms and the proofs of
new lower bounds. I will discuss a few such important examples, and
suggest directions for further exploration of this intriguing
connection.
