MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Reduction of the depth for arithmetic circuits

Sebastien Tavenas
ENS Lyon
Talk
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Thursday, 28 August 2014
13:00
30 Minutes
E1 4
024
Saarbrücken

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

Michael Sagraloff
--email hidden
passcode not visible
logged in users only

Michael Sagraloff, 08/11/2014 13:23
Michael Sagraloff, 08/08/2014 10:19 -- Created document.