Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

11 December 2001,
Complexity lower bounds for Positivstellensatz proofs
,
D. Grigoriev

Speaker: D. Grigoriev (University of Rennes)
Date: Tuesday 11 December 2001
Time: to be announced
Location: TU Delft, room to be announced

Recently an approach to NP-coNP problem based on proof systems using the Nullstellensatz was developed and there were shown complexity lower bounds for the proofs in such systems. In the talk a stronger proof system which relies on the Positivstellensatz is introduced and complexity lower bounds for several problems like the knapsack or the parity principle are established. These results could be also treated independently of the complexity theory as the lower bounds in the Positivstellensatz.

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

Please note that this newsitem has been archived, and may contain outdated information or links.