Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, May 04, 2010, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Mohammad Torabi Dashti (D-INFK - Information Security)
Permutation-complete words contain all the permutations of 1 .. N, for some positive natural N. Here w contains w' iff w' can be found by erasing zero or more letters from w. In 1972, Karp  posed the problem of finding the length of a shortest permutation-complete word, given a positive natural N. The problem is still open.
Recently, Mauw, Radomirovic and Torabi Dashti  proved that the message complexity of N-party contract signing protocols is tightly related to the length of shortest permutation-complete words. This result in particular implies that efficient algorithms for constructing (resp. recognizing) permutation-complete words can be used for designing (resp. debugging) N-party contract signing protocols. The talk will give an overview on the combinatorial aspects of constructing and recognizing permutation-complete words.
 Vaclav Chvátal, David Klarner, Donald Knuth: Selected Combinatorial Research Problems. Technical Report: CS-TR-72-292. Stanford University, 1972.
 Sjouke Mauw, Sasa Radomirovic, Mohammad Torabi Dashti: Minimal Message Complexity of Asynchronous Multi-party Contract Signing. CSF 2009, IEEE Computer Society.
Automatic MiSe System Software Version 1.4803M | admin login