Abstract

In this talk we are going to consider two questions:

The first one is depth reduction i.e. assume that we arithmetic circuit computing some function f(x_1,x_2,...,x_n) of size s. What upper bounds can we show on the size of the circuit of bounded depth computing f.

Second, we are going to show techniques to show lower bounds for depth 3 and 4 arithmetic circuits. We are going to show the following results:

If f is a polynomial of degree d that could be computed by circuit of size s then

  1. Polynomial f could be computed by circuit of size poly(s) and depth O(log d log s).
  2. Polynomial f could be computed by circuit of size exp(O(\sqrt{d} \log(s))) and depth 4.
  3. Polynomial f could be computed by circuit of size exp(O(\sqrt{d} \log(s))) and depth 3.
  4. We also going to show basic technique of shifted partial derivatives for proving lower bounds for depth 4 circuits.

Video Recording