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 \nFor 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