doc. Michal Koucký presents Lower bounds and the physical reality

Algorithms provide bounds (upper bounds) on the amount of resources such as time
and space that suffice to solve various computational problems. On the other
hand, lower bounds provide bounds on the amount of resources that are necessary
to solve such problems. Together they allow us to recognize what is the best
possible algorithm for the given problem.

In this talk I will survey our progress in proving lower bounds, and I will
illustrate how these questions are related to some fundamental problems studied
in physics. I will demonstrate some of the obstacles that we face when proving
lower bounds on the example of catalytic computation. Catalytic computation is a
novel way of using occupied space (memory) to carry out useful computation.