How to fool people to work on circuit lower bounds

Speaker  Ran Raz

Host  Alexandra Kolla

Affiliation  Weizmann Institute

Duration  00:57:32

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.
> How to fool people to work on circuit lower bounds