| Title | : | Building Arithmetic Circuits over Read-Once Formulas |
| Speaker | : | Ramya C (IITM) |
| Details | : | Thu, 31 Aug, 2017 2:00 PM @ Alan Turing Hall |
| Abstract: | : | Polynomials are one of the most fundamental objects in algebra. As a natural computational question one would ask 'Given a polynomial, how easy is it to compute it?' The complexity of polynomial can be defined as the number of arithmetic operations (additions and multiplications) needed to compute it. Leslie G. Valiant introduced arithmetic circuits as a model for computing polynomials and size of the circuit to be the number of addition and multiplication operations needed to compute it. Valiant conjectured that permanent(when viewed as a polynomial) cannot be computed by small size arithmetic circuits. While the answer to Valiant's conjecture still seems to be at a distance, recent research has focused restricted classes of arithmetic circuits. In this talk we show that permanent cannot be computed efficiently by restricted classes of arithmetic circuits. More specifically : (1) We study the strength and limitations of sums and sums of products of Read-Once Formulas as a computational model. Here Read-Once Formulas(ROFs) are arithmetic circuits where no computation can be reused and every variable can be read by the circuit exactly once. (2) We prove exponential size lower bound for the sum of ROFs computing an explicit 2n-variate polynomial. We also try to extend the exponential size lower bounds for sums of products of Read-Once Formulas with some additional restrictions. Our results exhibit the strength and limitations of lower bound techniques introduced by Ran Raz [2004]. |
