Ajtais Beweis von Satz 1 in 'Erzeugung harter Instanzen von Gitterproblemen'

8

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?

Krishnan Narayanan
quelle
5
Sie können versuchen, neuere Artikel wie cims.nyu.edu/~regev/papers/average.pdf oder Oded Regevs Vorlesungsunterlagen cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/… zu lesen (vielleicht möchten Sie den gesamten Kurs lesen).
Yuval Filmus

Antworten: