Max-Planck-Institut für Informatik
max planck institut
informatik
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
Language:English
Date, Time and Location
Date:Thursday, 28 August 2014
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
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.

Contact
Name(s):Michael Sagraloff
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Michael Sagraloff, 08/11/2014 01:23 PM
  • Michael Sagraloff, 08/08/2014 10:19 AM -- Created document.