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

• Applicant: Professor Dr. Marek Karpinski
• Subject Area: Theoretical Computer Science
• Term: Funded in 2004
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5428978

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.

• DFG Programme: Research Grants