Anwendungen von Ringen und diskreten Gittern beim Bestimmen der Komplexität von algebraischen Problemen

• Applicant: Dr. Thanh Minh Hoang
• Subject Area: Theoretical Computer Science
• Term: from 2009 to 2011
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 128306238

Viele algorithmische Probleme können algebraisch formuliert werden, wie z.B. eine Gleichung zu lösen, ein Polynom zu zerlegen u.s.w. Um solche algebraischen Probleme zu lösen, wurden in der letzten Zeit zunehmend spezielle mathematische Objekte wie endliche Ringe und diskrete Gitter mit erstaunlichem Erfolg eingesetzt. Gute Beispiele für den Einsatz von Ringen finden wir im Beweisargument PRIMES is in P [AKS04], dem Polynom-Nulltest für arithmetische Schaltkreise der Tiefe 3 [KS07] und in der Polynomfaktorisierung über endlichen Körper (s. [vzGP99]). Die Anwendung von Gittern geht schon auf Gauß und Minkowski (s. [Cas97]) zurück. Dank der Polynomialzeit-Gitter- reduktion von Lenstra, Lenstra und Lovász [LLL82] und des Resultats von Ajtai [Ajt98], welches besagt, dass die Berechnung eines kürzesten Vektors in einem Gitter unter randomisierten Polynomialzeitreduktionen NP-hart ist, finden Gitter wichtige Anwendungen: vor allem in algebraischer Zahlentheorie, ganzzahliger Approximierung, kombinatorischer Optimierung und in der Kryptographie [MG02, Reg04]. Die Untersuchungen in diesem Projekt haben die Zielsetzung, Ringe und diskrete Gitter bei der Bestimmung der Komplexität einiger wichtiger algebraischer Probleme anzuwenden. Insbesondere wollen wir das perfekte Matchingproblem, den Nulltest für symbolische Determinanten, die Derandomisierung des Isolationslemmas und diverse Faktorisierungsprobleme untersuchen.

• DFG Programme: Research Grants