BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Lower bound for arithmetic circuits via Hankel matrix - Pierre Ohl
 mann\, IRIF\, Université Paris 7
DTSTART:20181116T141500Z
DTEND:20181116T151500Z
UID:TALK113263@talks.cam.ac.uk
CONTACT:Victor Gomes
DESCRIPTION:Arithmetic circuit are the algebraic analogue of boolean circu
 its. As a natural model for computing multivariate polynomials\, they have
  been extensively studied. The most important open question in the field o
 f algebraic complexity theory is that of separating the classes VP and VNP
 \, the analogues of P and NP. More precisely\, can one obtain super-polyno
 mial lower bounds for circuits computing a given explicit polynomial ?\n\n
 Despite decades of efforts\, this question yet seems out of reach\, the be
 st general lower bound being only slightly super-linear. The most common a
 pproach is to prove lower bounds for restricted classes of circuits\, such
  as monotone or constant-depth circuits. Another approach would be removin
 g relations arising from the mathematical structure underlying the computa
 tions\, making it harder for circuits to compute polynomials and thus conc
 eivably easier to obtain lower bounds. In this line of thought\, Nisan (19
 91) was able to obtain breakthrough results in the context of non-commutat
 ive computations\, separating circuits and formulas and characterizing the
  minimal size of Algebraic Branching Programs (ABP).\n\nLikewise\, circuit
 s for which the multiplication is assumed to be non-associative\, meaning 
 that (xy)x and x(yx) are different monomials\, have been considered. Gener
 al exponential lower bounds can be proved in this setting. We highlight a 
 syntactical equivalence between non-associative circuits and acyclic Multi
 plicity Tree Automata (MTA)\, which leads to a general algebraic character
 ization of the size of the smallest non-associative circuit computing a gi
 ven non-associative polynomial.\n\nAs a direct consequence of this charact
 erization\, we unify several recent circuit lower bounds in the non-commut
 ative setting. Going deeper in the comprehension of this new algebraic too
 l\, we are able to considerably extend known lower bounds to classes of ci
 rcuits which are very close to general.
LOCATION:SS03
END:VEVENT
END:VCALENDAR