BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Logic and Semantics Seminar (Computer Laboratory)
SUMMARY:Lower bound for arithmetic circuits via Hankel mat
rix - Pierre Ohlmann\, IRIF\, Université Paris 7
DTSTART;TZID=Europe/London:20181116T141500
DTEND;TZID=Europe/London:20181116T151500
UID:TALK113263AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/113263
DESCRIPTION:Arithmetic circuit are the algebraic analogue of b
oolean circuits. As a natural model for computing
multivariate polynomials\, they have been extensiv
ely studied. The most important open question in t
he field of algebraic complexity theory is that of
separating the classes VP and VNP\, the analogues
of P and NP. More precisely\, can one obtain supe
r-polynomial lower bounds for circuits computing a
given explicit polynomial ?\n\nDespite decades of
efforts\, this question yet seems out of reach\,
the best general lower bound being only slightly s
uper-linear. The most common approach is to prove
lower bounds for restricted classes of circuits\,
such as monotone or constant-depth circuits. Anoth
er approach would be removing relations arising fr
om the mathematical structure underlying the compu
tations\, making it harder for circuits to compute
polynomials and thus conceivably easier to obtain
lower bounds. In this line of thought\, Nisan (19
91) was able to obtain breakthrough results in the
context of non-commutative computations\, separat
ing circuits and formulas and characterizing the m
inimal size of Algebraic Branching Programs (ABP).
\n\nLikewise\, circuits for which the multiplicati
on is assumed to be non-associative\, meaning that
(xy)x and x(yx) are different monomials\, have be
en considered. General exponential lower bounds ca
n be proved in this setting. We highlight a syntac
tical equivalence between non-associative circuits
and acyclic Multiplicity Tree Automata (MTA)\, wh
ich leads to a general algebraic characterization
of the size of the smallest non-associative circui
t computing a given non-associative polynomial.\n\
nAs a direct consequence of this characterization\
, we unify several recent circuit lower bounds in
the non-commutative setting. Going deeper in the c
omprehension of this new algebraic tool\, we are a
ble to considerably extend known lower bounds to c
lasses of circuits which are very close to general
.
LOCATION:SS03
CONTACT:Victor Gomes
END:VEVENT
END:VCALENDAR