Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

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)
What and Who
Title:Reduction of the depth for arithmetic circuits
Speaker:Sebastien Tavenas
coming from:ENS Lyon
Speakers Bio:
Event Type:Talk
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 28 August 2014
Duration:30 Minutes
Building:E1 4
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
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Michael Sagraloff, 08/11/2014 01:23 PM
  • Michael Sagraloff, 08/08/2014 10:19 AM -- Created document.