BEGIN:VCALENDAR
VERSION:2.0
PRODID:ILLC Website
BEGIN:VEVENT
UID:/NewsandEvents/Events/Upcoming-Events/newsitem
/74/11-December-2001-Complexity-lower-bounds-for-P
ositivstellensatz-proofs-D-Grigoriev
DTSTAMP:20011114T000000
SUMMARY:\n Complexity lower bounds for Positi
vstellensatz proofs\n , \n D. Grigoriev
ATTENDEE;ROLE=Speaker:D. Grigoriev (University of
Rennes)
DTSTART:20011211T000000
DTEND:20011211T000000
LOCATION:TU Delft, room to be announced
DESCRIPTION:Recently an approach to NP-coNP proble
m based on proof systems using the Nullstellensatz
was developed and there were shown complexity low
er bounds for the proofs in such systems. In the t
alk a stronger proof system which relies on the Po
sitivstellensatz is introduced and complexity lowe
r bounds for several problems like the knapsack or
the parity principle are established. These resul
ts could be also treated independently of the comp
lexity theory as the lower bounds in the Positivst
ellensatz. For more information, see http://ssor
.twi.tudelft.nl/~dima
X-ALT-DESC;FMTTYPE=text/html:\n \n
Recently an approach to NP-coNP problem based on p
roof systems using\n the Nullstellensatz wa
s developed and there were shown complexity lower\
n bounds for the proofs in such systems. In
the talk a stronger proof\n system which r
elies on the Positivstellensatz is introduced and\
n complexity lower bounds for several probl
ems like the knapsack or the\n parity princ
iple are established.\n These results could
be also treated\n independently of the com
plexity theory\n as the lower bounds in the
Positivstellensatz. \n

\n \n For more information, see\n http:
//ssor.twi.tudelft.nl/~dima\n

\n
URL:/NewsandEvents/Events/Upcoming-Events/newsitem
/74/11-December-2001-Complexity-lower-bounds-for-P
ositivstellensatz-proofs-D-Grigoriev
END:VEVENT
END:VCALENDAR