IISER Pune
INDIAN INSTITUTE OF SCIENCE EDUCATION AND RESEARCH (IISER) PUNE
where tomorrow’s science begins today
An Autonomous Institution, Ministry of Human Resource Development, Govt. of India
Links
Seminars and Colloquia

Mathematics

Read-once Arithmetic Branching Programs (ROABPs) 
 
Thu, Oct 05, 2017,   04:30 PM to 05:30 PM at Madhava Hall

Dr. Arpita Korwar
IIT Kanpur

In computational complexity, arithmetic circuits are used to
compactly represent polynomials. How 'difficult' a polynomial is can be
measured by looking at the 'easiest' arithmetic circuit that represents
that polynomial. A Polynomial Identity Test for a family of circuits takes
a circuit from that family and says whether the polynomial computed by
that circuit is identically zero or not.

In this talk, we will look at special arithmetic circuits called
Arithmetic Branching Programs. They compute polynomials that can be
written as an Iterated Matrix Multiplication. We will give a
quasi-polynomial time hitting set for the sum of ROABPs. In the process,
we will study some defining properties of ROABPs.
 

homecolloquia_seminars