Talks - Spring 2018

ArithmeticCircuit

Title

Speaker

Date

Time

Venue

Abstract

Depth reduction in Arithmetic Circuits

Pranav Bisht

13 January, 2018

4:30 pm

KD102

We plan to cover one of the most significant result in the area of arithmetic circuit complexity, namely "Depth-4 chasm" due to Agrawal, Vinay 2008. It greatly simplified the work of researchers to focus only on depth <= 4 arithmetic circuits for the purpose of lower bound and polynomial identity testing problems. We will cover the proof in 2 steps. We will start by reducing a general circuit to O(log d) depth, where d is the degree of the polynomial the circuit is computing. This result is due to Valiant et cetera 1983. The second step would be to convert this new circuit to depth-4 along the lines of AV08.

References:
  1. http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=4690941 (AV08)
  2. https://github.com/dasarpmar/lowerbounds-survey (Sap, Chapter 5)


ALL SESSIONS


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator