Nov 27-28: Shport Course on Probabilistic Proofs

Subject: Nov 27-28: Shport Course on Probabilistic Proofs
From: Helmut Veith (
Date: Wed Nov 26 1997 - 17:11:36 MET

Short Course Announcement

Oleg Verbitsky
Lviv University

Probabilistic Proofs and Approximation.

November 27-28, 14.00-17.00

The short course of lectures is devoted to Probabilistically
Checkable Proofs. This concept includes several related
computational models combining nondeterminism and randomization.
Results in this area allow one to prove that finding even an approximate
solution for some well-known optimization problems is NP-hard.
We will discuss also applications to Structural Complexity and


Seminarraum SEM 181A, Institut fuer Informationssysteme,
Paniglgasse 16, 1. Stock, 1040 Wien.

Technische Universitaet Wien
Institut fuer Computersprachen E185.2
Resselgasse 3/1, A-1040 Wien

Tel: (+43 1) 588 01/4088
Fax: (+43 1) 504 15 89

Mit Unterstuetzung des
Bundesministeriums fuer Wissenschaft und Forschung

This archive was generated by hypermail 2b25 : Thu Apr 06 2000 - 16:19:18 MET DST