BEGIN:VCALENDAR
VERSION:2.0
PRODID:ILLC Website
X-WR-TIMEZONE:Europe/Amsterdam
BEGIN:VTIMEZONE
TZID:Europe/Amsterdam
X-LIC-LOCATION:Europe/Amsterdam
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:19700329T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:19701025T030000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:/NewsandEvents/Archives/2001/newsitem/74/11-De
cember-2001-Complexity-lower-bounds-for-Positivste
llensatz-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;TZID=Europe/Amsterdam:20011211T000000
DTEND;TZID=Europe/Amsterdam: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

URL:/NewsandEvents/Archives/2001/newsitem/74/11-De
cember-2001-Complexity-lower-bounds-for-Positivste
llensatz-proofs-D-Grigoriev
END:VEVENT
END:VCALENDAR