Talks - Spring 2019

ArithmeticCircuit

Title

Speaker

Date

Time

Venue

Abstract

An Improved Depth Reduction for Syntactically Multilinear Circuits

Prof. Ramprasad Saptharishi

17nd January 2019

5:00-6:00 PM

KD102

We show that any n-variate polynomial computable by a syntactically multilinear circuit of size poly(n) can be computed by a syntactically multilinear depth-4 circuit of size at most exp({O(\sqrt{nlog n}). For degree d = omega(n/log n), this improves upon the upper bound of exp({O(\sqrt{d}\log n)} obtained by Tavenas for general (non-multilinear) circuits, and is known to be asymptotically optimal in the exponent when d is less than n^{\epsilon} for a small enough constant epsilon. Our upper bound matches the lower bound of exp({Omega(\sqrt{nlog n})} proved by Raz and Yehudayoff, and thus cannot be improved further in the exponent. Based on joint work with Mrinal Kumar and Rafael Oliveira.

ALL SESSIONS


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator