The 17th McGill Invitational Workshop on Computational Complexity will be held at Bellairs Research Institute of McGill University, Holetown, St. James, Barbados, West Indies from February 27th to March 6th, 2005. Participants are expected to arrive on Sunday afternoon, February 27th. The topic of this year's workshop will be "Lower Bounds for Algebraic Circuits".
Ran RazAddress:
Faculty of Mathematics and Computer ScienceAbstract:
The Weizmann Institute of Science
POB 26, Rehovot 76100, ISRAEL
Tel: 972-8-934-3540
ran.raz@weizmann.ac.il
The workshop will concentrate on arithmetic circuit complexity, and in particular on proving lower bounds for arithmetic circuits. After a short introduction and a short survey of known results, I hope to cover the following subjects:
I may also talk about lower bounds for bounded-depth arithmetic circuits, and may also touch related issues, such as the polynomial identity testing problem, and such as interesting upper bounds.
- Strassen's and Bower-Strassen's super-linear lower bounds (for polynomials of non-constant degree)
- Some directions for proving super-linear lower bounds for polynomials of constant degree
- Exponential lower bounds for non-commutative formulas
- Super-polynomial lower bounds for multilinear formulas
- Super-linear lower bounds for bounded-coefficients circuits