| Date: | Thursdays, 4.00 p.m. |
| Room: | NA 5-64 (University of Bochum) |
June 25, 2009, 4.00 p.m.
Balazs Szorenyi, University of Bochum
The PCP theorem was a breakthrough result in the theory of discrete optimization, which brought a new paradigm to complexity theory: the notion of probabilistically checkable proofs. It states that membership for the languages in NP can be certified by some "short" strings, such that it is enough to read only a constant number of randomly chosen bits of this certificates to verify the membership of an instance in polynomial time. The original version of the proof applied interactive protocols; the result of Dinur provided a long waited simplification of the proof of this theorem.
July 2, 2009, 4.00 p.m.
Dirk Sudholt, TU Dortmund
The Lovasz Local Lemma is a powerful tool to prove the existence of combinatorial objects meeting a prescribed collection of criteria. The technique can directly be applied to the satisfiability problem, yielding that a k-CNF formula in which each clause has common variables with at most 2^{k-2} other clauses is always satisfiable. Moser (STOC 2009) presented a randomized algorithm that finds a satisfying assignment to every k-CNF formula in which each clause has a neighbourhood of at most the asymptotic optimum of 2^{k-5}-1 other clauses and that runs in expected time polynomial in the size of the formula, irrespective of k. In contrast to all previous approaches, his analysis does not anymore invoke the standard non-constructive versions of the Local Lemma and can therefore be considered an alternative, constructive proof of it.
June 18, 2009, 4.00 p.m.
Thomas Dullien, University of Bochum
The question on whether a fully homomorphic encryption scheme (e.g. that permits the evaluation of arbitrary circuits on ciphertext with only polynomial blowup in circuit and ciphertext size) exists has been long-standing. Various schemes for allowing unlimited additions and a limited number of multiplications have been proposed in the past. At STOC 2009, Craig Gentry presented a new scheme that achieves evaluation of arbitrary circuits on ciphertexts. The short (12-page) paper is quite dense, and in some places elliptic. An attempt will be made at explaining the functioning of the proposed scheme, also taking into account some facets of an expanded version (126 pages) of the initial paper.
May 28, 2009, 4.00 p.m.
Balazs Szorenyi, University of Bochum
The PCP theorem was a breakthrough result in the theory of discrete optimization, which brought a new paradigm to complexity theory: the notion of probabilistically checkable proofs. It states that membership for the languages in NP can be certified by some "short" strings, such that it is enough to read only a constant number of randomly chosen bits of this certificates to verify the membership of an instance in polynomial time. The original version of the proof applied interactive protocols; the result of Dinur provided a long waited simplification of the proof of this theorem.
May 14, 2009, 4.00 p.m.
Tibor Jager, University of Bochum
"Lossy trapdoor functions", introduced by Peikert and Waters (STOC 2008), are a very useful general cryptographic primitive. They are the first known injective trapdoor functions based on problems not directly related to integer factorization, and give rise to the development of new approaches for constructing several important cryptographic tools.
Goal of the talk is to introduce the notion of lossy trapdoor functions and describe applications such as the construction of CPA- and CCA-secure encryption schemes.
May 7, 2009, 4.00 p.m.
Christian Sohler, TU Dortmund
Given access to a bounded degree graph G the goal of testing a property P is to distinguish between the case that G satisfies P and the case that one should add/remove more than eps n d edges to make G satisfy P. In this talk we how that a large family of properties can be efficiently tested in the bounded degree graph model.
June 3, 2009 - Christiane Lammersen