How to fool people to work on circuit lower bounds

Опубликовано 17 августа 2016, 22:20

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.