A prova do teorema 1 de Ajtai em 'Gerando instâncias difíceis de problemas de treliça'

8

Minha pergunta diz respeito à prova do principal teorema de Ajtai em seu artigo inovador de 1996, Gerando instâncias rígidas de problemas de treliça , o que indica uma conexão entre os problemas de treliça de pior caso e de malha dura de caso médio. Esta prova é difícil para mim entender. Existe uma exposição clara dessa prova na literatura?

Krishnan Narayanan
fonte
5
Você pode tentar ler artigos mais recentes, como cims.nyu.edu/~regev/papers/average.pdf , ou as notas da aula de Oded Regev cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/… (você pode leia o curso inteiro).
Yuval Filmus

Respostas: