 max planck institut
informatik # MPI-INF or MPI-SWS or Local Campus Event Calendar

 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: Reduction of the depth for arithmetic circuits Sebastien Tavenas ENS Lyon Talk D1, D2, D3, D4, D5, RG1, SWS, MMCIWe use this to send out email in the morning. AG Audience English
Date: Thursday, 28 August 2014 13:00 30 Minutes Saarbrücken E1 4 024
 The arithmetic complexity is the study of the resources required to compute some polynomials using only the arithmetic operations. In the late 70s, Valiant defined (similarly to the Boolean complexity) some classes of polynomials. The polynomials computed by circuits of polynomial size form the VP class (we can imagine them as the easy ones). Exponential sums of polynomials in VP belong to the class VNP. It is conjectured that VP is different to VNP (Valiant hypothesis). Although this conjecture is still widely open, it seems more accessible than its Boolean counterpart. The underlying algebraic structure limits the possibilities of computations. In particular, an important result for this model ensures that the low-degree polynomials in VP can be effectively parallelized. Moreover, if we allow a reasonable increase in size, it is also possible to compute them by circuits such that the depth is bounded by a constant. Then, we will try to see how some lower bounds for these circuits could be achieved by using univariate polynomials. Bürgisser showed that the τ-conjecture which upper-bounds the number of roots of some univariate polynomials, implies lower bounds in arithmetic complexity. But what happens if we try to reduce, as previously, the depth of the considered polynomial? Bounding the number of real roots of certain families of polynomials would allow to separate VP from VNP.
Name(s): Michael Sagraloff