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.