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      <p>\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      </p>\n    \n      <p
 >For more information, see\n        <a target="_bl
 ank" href="http://ssor.twi.tudelft.nl/~dima">http:
 //ssor.twi.tudelft.nl/~dima</a>\n      </p>\n    
URL:/NewsandEvents/Archives/2001/newsitem/74/11-De
 cember-2001-Complexity-lower-bounds-for-Positivste
 llensatz-proofs-D-Grigoriev
END:VEVENT
END:VCALENDAR