Talks - Spring 2018

ArithmeticCircuit

Title

Speaker

Date

Time

Venue

Abstract

Reconstruction of depth three circuits with top fan-in two

Gaurav Sinha (Microsoft, Cal, USA)

5 January, 2018

4:30 pm

KD102

Reconstruction of arithmetic circuits has been heavily studied in the past few years and has connections to proving lower bounds and deterministic identity testing. In this talk we present a polynomial time randomized algorithm for reconstructing depth−3 circuits with fan-in 2 at the top addition gate and having coefficients from a characteristic zero field.

The algorithm needs only a black-box query access to the polynomial, runs in time polynomial in input size and returns a circuit (from the above model) computing the polynomial (with high probability).

Our main techniques are based on the use of Quantitative Sylvester Gallai theorems from recent work of Barak et.al., to find a small collection of "nice" sub-spaces onto which we restrict our input polynomial. The heart of our work lies in applying these theorems to prove why restrictions w.r.t. the "nice" sub-spaces can be ”glued”. We also use "Brill’s Equations" to construct a set of linear forms which are computed at the first computational (from the bottom) layer of our arithmetic circuit.

ALL SESSIONS


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator