Speaker Ran Raz
Host Alexandra Kolla
Affiliation Weizmann Institute
Date recorded 20 October 2010
I will present two families of mathematical problems that are very simple to describe, that seem natural to study from geometric, algebraic or combinatorial points of view, and are seemingly unrelated to theoretical computer science, and whose solution would give exceptionally strong results in theoretical computer science; namely, super-polynomial lower bounds for the size of general arithmetic circuits and formulas.
More specifically, I will discuss 'elusive functions and lower bounds for arithmetic circuits' - an approach to prove exponential lower bounds for circuit size; and 'tensor-rank and lower bounds for arithmetic formulas' - an approach to prove super-polynomial lower bounds for formula size.
©2010 Microsoft Corporation. All rights reserved.