Meine Frage bezieht sich auf den Beweis von Ajtais Hauptsatz in seiner bahnbrechenden Arbeit von 1996, Generieren harter Fälle von Gitterproblemen , die einen Zusammenhang zwischen harten und durchschnittlichen harten Gitterproblemen im schlimmsten Fall anzeigt. Dieser Beweis ist für mich schwer zu verstehen. Gibt es eine klare Darstellung dieses Beweises in der Literatur?
integer-lattice
Krishnan Narayanan
quelle
quelle
Antworten:
Sie können versuchen, neuere Artikel wie Worst- Case- bis Average-Case-Reduktionen basierend auf Gaußschen Messungen von Miccancio und Regev oder Regevs Vorlesungsunterlagen zu diesem Thema zu lesen (möglicherweise möchten Sie den gesamten Kurs durchlesen ).
quelle