A tutorial 0on PCP theorem

Date Thursday, October 20, 5:20-7:30 pm
the first tutorial of

5-hour tutorial
"PCP theorem, Interactive Proofs and Inapproximability of
Optimization Problems"


This talk would be more a tutorial, then a seminar. Full proofs, explanations and background materials will be given. I have given it once already in UoQ and this tutorial is quite ready in sense of quality of presentation.

PCP theorem is considered to be one of the major development in TCS in 90s. Perhaps, since 1992 every STOC and FOCS conference has at least one article strongly related to the PCP theorem.

Basically the PCP theorem provides a new characterization of NP class as a class of languages, a membership problem of which can be solved by the logarithmic number of random bits and the constant number of proof bits. (sounds miracle? The constant number of bits is actually needed instead of polynomial to proof a membership of the word.)
The original proof based on algebraic technique is quite complicated (around 20 pages of proof). The new proof based on combinatorial techniques (zig-zag products) was discovered this year by Irit Dinur.
Using other version of interactive proof systems we can capture PSPACE and NEXPTIME class and investigate some interesting properties of them.

NPO means NP optimization problem. NPO is a search version of NP class which is defined to be a class of decission problems. The NPO problem required to find a minimal (or maximal) solution among given one. For example, a Traveling Salesman Problem expressed as a search problem (Find a minimal lengh route in the graph which visit all vertices ones) would be an example of NPO problem. Usually NPO problem, a search version of NP decission problems belongs to FP^NP or FP^NP(log n) - hard classes indeed.
Since assuming P is not equal NP, there does not exist a polynomial algorithm to solve EXACTLY NP-hard-problems, given a NP-hard NPO problem it would be natural to ask, if a polynomial-time algorithm exists which can solve a problem with some approximation quality.
It was discovered that there exists a few approximation classes of NPO problems, which put certain bounds on approximation quality of algorithms for those problems. PCP theorem is useful to prove in-approximation properties of NPO problems.

Besides PCP theorem other important for theoretical computer science techniques will be introduced. Expanders are graphs which posses good expansion properties. (n,d,c) expander is a d-regular undirected graph with n vertices, such that if a set of vertices S chooses such that |S| < |n|/2, then a cardinality of a set of vertices adjacent to S is not less then c|S| Expanders are useful in computational complexity, error-correcting codes, communication networks.
Using expanders and PCP theorem we will prove n^\epsilon-inapproximability of MAX CLIQUE problem and NP-hardness of MAX 3SAT5 (SAT with 3 variables per clause and each variable is used not more then 5 times)

Pablo Barcelo's talk on Temporal Logic Over Unranked Trees

Pablo Barcelo gives a talk at 16:00, Thursday 21, 2005
Topic: Temporal logic over unranked trees.
Abstract: We consider unranked trees, that have become an active subject of study recently due to XML applications, and characterize commonly used fragments of first- order (FO) and monadic second-order logic (MSO) for them via various temporal logics. We look at both unordered trees and ordered trees (in which children of the same node are ordered by the next-sibling relation), and characterize Boolean and unary FO and MSO queries. For MSO Boolean queries, we use extensions of the \mu - calculus: with counting for unordered trees, and with the past for ordered. For Boolean FO queries, we use similar extensions of CTL*. We then use composition techniques to transfer results to unary queries. For the ordered case, we need the same logics as for Boolean queries, but for the unordered case, we need to add both past and counting to the -calculus and CTL*. We also consider MSO sibling-invariant queries, that can use the sibling ordering but do not depend on the particular one used, and capture them by a variant of the \mu-calculus with modulo quantifiers.