Haifa University - Dept. of CS Theory Seminar
Speaker : Ran Raz, Weizmann.
Title: "Elusive Functions and Lower Bounds for Arithmetic Circuits"
Date: Thursday, Jan. 17.
Place: Haifa U. Education Building, room 570.
Time: 12:15 - 13:30
Abstract:
I will present a family of mathematical problems that are very simple to describe, that seem very
natural-to-study from geometric, algebraic and combinatorial points of view, and are seemingly unrelated to
arithmetic circuit complexity, and whose solution would give strong (up to exponential) lower bounds for the
size of general arithmetic circuits. I may also discuss lower bounds of $n^{1+\Omega(1/d)}$ for the size of
arithmetic circuits of depth $d$ (for explicit polynomials of degree $O(d)$) that are proved using these
methods.