Faster algorithms for hard problems like subset sum, syndrome decoding in linear codes and the shortest vector problem, with various applications in complexity theory and cryptography

• Applicant: Professor Dr. Alexander May
• Subject Area: Theoretical Computer Science
• Term: from 2011 to 2014
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 206738461

2010 stellten Howgrave-Graham und Joux eine neue Representationstechnik zum Lösen des Subset Sum Problems vor. Dabei wird eine eindeutige Lösung mit Hilfe von exponentiell vielen Representationen dargestellt. Unter diesen Darstellungen wird wiederum eine eindeutige Lösung mit gewissen Eigenschaften berechnet. Interessanterweise liefert dieses Aufblasen und Kürzen des Suchraums beim Subset Sum Problem eine signifikante Verbesserung der Zeitkomplexität von ∂(20.5n) auf ∂(20.337n).Unser Ziel ist eine generelle Analyse der Representationstechnik, die einen generischen Einsatz der Technik als allgemeines algorithmisches Tool erlaubt. Unsere erste Anwendung der Methode liefert bereits eine Verbesserung des besten bekannten Algorithmus zum Berechnen des Dekodierproblems in allgemeinen linearen Codes. Weitere wichtige Anwendungen der Representationstechnik sehen wir u.a. bei der Berechnung kürzester Vektoren in Gittern und bei einem neuen kombinatorischen Algorithmus für ein Problem in zyklischen Gittern, das dem NTRU Kryptosystem zugrunde liegt.Wir erwarten, dass eine hinreichend generische Formulierung der Representationstechnik viele weitere Anwendungen bei der Algorithmenkonstruktion für harte kombinatorische Suchprobleme innerhalb des SPP Algorithm Engineering liefert.

• DFG Programme: Priority Programmes
• Subproject of: SPP 1307: Algorithm Engineering