Forschungsreise ans MIT (Entwurf und Analyse effizienter Algorithmen), Laboratory for Computer Science and Artificial Intelligence, CSAIL, MIT

点击翻译按钮获取中文摘要

Die Forschungsreise (während meines vorlesungsfreien Forschungssemesters im Sommersemester 2004) ans MIT soll folgenden Forschungszielen dienen: 1. Verbesserung der existierenden Techniken für sog. traversal der Merkle trees (siehe [JLMS031, [M79]; Referenzen (6.)) und die effiziente Generierung der zusammenhängenden "authentication paths". Die algorithmischen Ideen, die in [BKNO21 und in [KN02] verwendet wurden, sollten hier auch weiter entwickelt und verwendet werden. Merkle trees haben viele potentielle Anwendungen, wie z.B. in certification refreshal, wireless security und signatures (siehe [JLMS03] und [M97]). Es ist eine Zusammenarbeit mit den MIT-Forschern Professor Silvio Micali und Professor Tom Leighton geplant. 2. Es werden die Konstruktionen effizienter Sampler-Techniken und Approximationsalgorithmen für kombinatorische und geometrische Optimierungsprobleme basierend auf den Sampling Ideen von [AFKK02] und effizienter Linearisierung der Smooth Programme von [AKK99] untersucht. Diese Methoden sollen zur Verbesserung der existierenden Approximationsalgorithmen und Approximationsschemata für NP-Harte Probleme der metrischen Partitionierung und Clustering Probleme und deren Anwendungen (siehe [199], [FKKR03], [K02], [BKO2b]) sowie zur Verbesserung der Approximationsalgorithmen für ausgewählte Minimum Constraint Satisfaction Probleme, aufbauend auf die folgenden Arbeiten [BKO2b], [BFK02], [AFKK02], [FKL02], dienen. Eine Zusammenarbeit über dieses Thema mit den MIT-Forschern P. Indyk, M. Goemans, D. Karger und M. Sudan ist geplant.